## Factorial and power

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

[SOLVED]

#### 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}$$,

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

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: