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

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).

• I think your proof is great. Using Wilson's Theorem would be what my old professor would call "killing a fly with a sledgehammer".
– user694818
Aug 23, 2019 at 16:27
• Aug 23, 2019 at 16:42
• Your hint is wrong, it says the opposite of what is true. I guess you added the "+1" by mistake, because the truth you're after is probably "For a composite $n>4, n$ divides $(n-1)!$". Aug 23, 2019 at 18:28

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, hence $$n=ab \mid (ab-1)!=(n-1)!.$$

• There's no need to analyze the case $n=p^k$ for $k\ge3$, because in this case $n=p\cdot p^{k-1}$ and $1<p<p^{k-1}<n$, so the last case applies. Aug 23, 2019 at 16:44

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$$.

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$$.