What are the possible positive integer values of \(n\) such that \((n - 1)! + 1\) is a power of \(n\)?

[SOLVED]

2 comments

Rino Raj solved this puzzle:

If \(n \in \{2, 3, 5\}\), \(n\) is a solution. Let \(n \gt 5\) be an integer which solves \((n - 1)! + 1 = n^k\) for some \(k \in \mathbb{N}\). Then, we need to have \((n - 1)! = n^k - 1\). For even \(n\), LHS is even while RHS is odd, so a solution is not possible. For odd \(n\), \(n - 1 \gt 4\) is even and hence is the product of \(2\) and an integer \(m\) in the open interval \((2, n - 2)\). In \((n - 2)!\), both \(2\) and \(m\) appear as separate factors because \((n - 2)!\) is the product of all integers between \(1\) and \((n - 2)\). Hence \((n - 1) = 2m\) must divide \((n - 2)!\). Hence \((n - 1) \mid (n - 2)!\). Therefore, \((n - 1)^2 \mid (n - 1)!\). Thus,

\begin{align} (n - 1)^2 \mid (n^k - 1) & \implies (n - 1) \mid \frac{n^k - 1}{n - 1} \notag \\ & \implies (n - 1) \mid \sum_{r=0}^{k - 1} n^r \label{eq1}. \end{align}

Since \(n \equiv 1 \pmod{n - 1}\),

\begin{equation} \label{eq2} \sum_{r=0}^{k - 1} n^r \equiv k \pmod{n - 1}. \end{equation}

From \eqref{eq1} and \eqref{eq2}, we get \((n - 1) \mid k\). Therefore, \((n - 1) \le k\).

Now, \((n - 1)! \lt n^{n - 1} - 1\). This can be shown by the principle of mathematical induction, as follows.

Theorem. \(S(n)\): \((n - 1)! \lt n^{n - 1} - 1\) when \(n \gt 2\).

Proof. \(S(3)\) is true because \(2! = 2 \lt 8 = 3^2 - 1\). Now if \(S(n)\) holds true, \(S(n + 1)\) also holds true as shown below. \begin{align*} (n + 1)^n - 1 & \gt n^n - 1 = n \cdot n^{n - 1} - 1 \\ & \gt n (n^{n - 1} - 1) \\ & \gt n(n - 1)! = n!. \end{align*}

Thus \(S(n)\) holds for \(n \gt 2\), so \((n - 1)! \lt n^{n - 1} - 1 \leq n^k - 1\), hence there are no solutions with \(n \gt 5\).

quasi solved this puzzle:

By inspection, \(n \in \{2, 3, 5\}\) works. Now we claim that these are the only values of \(n\) which work.

Lemma 1. If \(n\) is composite and \(n \gt 4\), then \((n - 1)!\) is a multiple of \(n\).

Proof. Let \(a\) be the least prime factor of \(n\). Since \(n\) is composite, \(n \geq a^2\).

Case 1: \(n \gt a^2\). Let \(b = \frac{n}{a}\). Then \(n = ab\) and \(1 \lt a \lt b \lt n\), so \(ab\) divides \((n - 1)!\). Thus \(n\) divides \((n - 1)!\).

Case 2: \(n = a^2\). Since \(n\) is composite and \(n \gt 4\), we have \(a \gt 2\). Then \(1 \lt a \lt 2a \lt a^2 = n\). Then \(a \cdot 2a\) divides \((n - 1)!\), so \(a^2\) divides \((n -1)!\). Thus \(n\) divides \((n - 1)!\).

Lemma 2. If \(n\) and \(k\) are positive integers such that \(n \gt 1\), then \(\frac{n^k - 1}{n - 1} \equiv k \pmod{n - 1}\).

Proof. \begin{align*} \frac{n^k - 1}{n - 1} & = 1 + n + n^2 + \dots + n^{k - 1} \\ & \equiv 1 + 1 + 1 + \dots + 1 \pmod{n - 1} \\ & \equiv k \pmod{n - 1}. \end{align*}

Suppose \((n - 1)! + 1 = n^k\) where \(n\) and \(k\) are positive integers and \(n \notin \{2, 3, 5\}\).

By inspection, \(n = 1\) or \(n = 4\) is not a solution, so we can assume \(n \gt 5\). If \(n\) is composite, then by lemma (1), \((n - 1)! + 1 \equiv 1 \pmod{n}\). This is a contradiction, since any power of \(n\) must be congruent to \(0 \pmod{n}\). Hence n is prime.

Then since \(n\) is prime and \(n \gt 5\), \(n - 1\) is composite and \(n - 1 \gt 4\), hence by lemma (1), \((n - 1)\) divides \((n - 2)!\), and consequently, \((n - 1)^2\) divides \((n - 1)!\).

By lemma (2),

\begin{equation*} \frac{n^k - 1}{n - 1} \equiv k\pmod{n - 1} \implies n^k - 1 \equiv k(n - 1) \pmod{(n - 1)^2}. \end{equation*}

Then \((n - 1)! = n^k - 1\) and \((n - 1)! \equiv 0 \pmod{(n - 1)^2}\), hence

\begin{align*} k(n - 1) \equiv 0 \pmod{(n - 1)^2} & \implies k \equiv 0 \pmod{n - 1} \\ & \implies k \geq n - 1. \end{align*}

Then

\begin{align*} \frac{n^k}{(n - 1)! + 1} \geq \frac{n^{n - 1}}{n!} = \prod_{r = 2}^n \frac{n}{r} \gt 1. \end{align*}

This is a contradiction, thus establishing the claim.

Credit

This puzzle is based on:

Further reading

The following is a list of resources on related topics:

Post a comment

RSS