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.

  • 4
    $\begingroup$ I think your proof is great. Using Wilson's Theorem would be what my old professor would call "killing a fly with a sledgehammer". $\endgroup$
    – user694818
    Aug 23, 2019 at 16:27
  • 1
    $\begingroup$ Related; math.stackexchange.com/questions/805068/… $\endgroup$
    – Servaes
    Aug 23, 2019 at 16:42
  • $\begingroup$ 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)!$". $\endgroup$
    – Ingix
    Aug 23, 2019 at 18:28

3 Answers 3


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

  • 3
    $\begingroup$ 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. $\endgroup$
    – egreg
    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$.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .