To prove that $(n-1)!+1$ is not a power of $n$.

Question

If $n$ is composite, prove that $(n-1)!+1$ is not a power of $n$.

Hint: We know that if $n$ is composite and $n>4$ then $(n-1)!$ is divisible by $n$.

My Solution:

Since $n=4$ is the first composite number. We have $(4-1)!+1=7$. Clearly 4 does not divide 7. Also we know that $(n-1)! \equiv 0$ (mod $n$) (for $ n>4$ and $ n$ composite). Also $1 \equiv 1$ (mod $n$). Adding both these equations we get :

$(n-1)!+1 \equiv 1$ $\pmod n.$ Hence it is clear that $(n-1)!+1$ is not a power of $n$.

Please correct me if there is any discrepancy in proof writing or the solution. Also it is highly appreciable if someone could provide with any other solution (Using modular-arithmetic or using Wilson's Theorem).

Thanks in advance.

Answer 1

Your solution is correct. Without Wilson's theorem, maybe you'd like to explain why $n\mid (n-1)!$ for all composite all $n$.

$\bullet$ If $n=p^2$, for some prime $p\ge 3$, then $$ n=p^2\mid p\cdot (2p)\mid (p^2-1)!=(n-1)!. $$ $\bullet$ If $n$ has at least two prime factors or $n=p^k$ for some prime $p$ and integer $k\ge 3$, then $n=ab$, for some $1<a<b<n$, hence $$ n=ab \mid (ab-1)!=(n-1)!. $$

Answer 2

Using Wilson's theorem, we see that if $n$ is composite, then $(n-1)!\not\equiv -1\mod{n}$, so that in fact $(n-1)!+1$ is not even divisible by $n$, much less a power of $n$.

Answer 3

1. There is a proof that holds true even if $n$ is prime and $n$ sufficiently large.

We may assume WLOG that $n$ is odd.

Note then that $n=a2^{\ell_0}+1$; $a$ odd and $\ell$ an integer, for some positive integer $\ell_0 < \log_2 n$. Furthermore, for all positive integers $r$ and all $q \le 2^r$, one can check the following: Write $n^q= a_q2^{\ell_q} +1$; $a_q$ an odd integer and $\ell_q$ a positive integer. Then $\ell_q$ satisfies $\ell_q \le r\ell_0$. [Indeed, write $q=\sum_i c_i2^i$ where each $c_i$ is either 0 or 1. Note that $n^{2^i}$ can be written $n^{2^i}=a_i2^{\ell_0+i} +1$; $a_i$ odd. So $\ell_q = \ell_0+j$ where $j$ is the smallest integer such that $c_j$ is 1. In particular, $\ell_q \le \ell_0+\log_2 q$

We use this to finish the proof. If $(n-1)!+1$ is a power of $n$, then $(n-1)!+1$ $=$ $n^q$ for some $q < n$. Thus on the one hand, from the above $n^q= a_q2^{\ell_q} +1$ where $a_q$ is odd and where $\ell_q$ satisfies $\ell_q \le \ell_0+\log_2 q$ $\le 2 \log _2 n$. However, on the other hand, note that $2^{\frac{n}{2}-1}|(n-1)!$ so $(n-1)!+1$ can be written $(n-1)!+1$ $=$ $a2^{\ell}+1$ for some $\ell \geq \frac{n}{2}-1$. Thus, on the other hand, $\ell_q$ must satisfy $\ell_q \geq \frac{n}{2}-1$. This is impossible for $n \geq 33$.