# How to prove that $p! \ \ (mod \ p^2) \ = p(p-1)$

While doing my Math homework about Modular arithmetic. I accidentally found this

$$p!\equiv p(p-1)\pmod{p^2}$$

It's help me save time to find $$\ 21! \ \ (mod \ 361) \$$ a lot.

The question is how can I prove an equation above . Thank you in advance.

• Wilson's theorem will get you most of the way – Henry Mar 8 at 10:32
• Also note that your formula can be simplified: $p(p-1)=p^2-p\equiv -p \pmod{p^2}$. But pay attention: the equation holds if and only if $p$ is a prime number! – AlessioDV Mar 8 at 10:58
• it also reduces to $(p-2)!\equiv 1 \bmod p^2$ – Roddy MacPhee Mar 10 at 13:26

Warning ! You statement is true only when $$n$$ is prime. For example for $$n=4$$, you don't have $$n! = n(n-1) \quad (\mathrm{mod} \text{ } n^2)$$. So I guess you can't use it with $$21$$ ("by hand", you can see that $$21!=323 \neq 21\times 20 \quad (\mathrm{mod} \text{ } 361)$$).

Proof when $$n$$ is prime :

By Wilson's theorem, $$(p-1)! = -1 \quad (\mathrm{mod} \text{ } p)$$

Multiplying by $$p$$, this implies $$p! = -p \quad (\mathrm{mod} \text{ } p^2)$$

i.e. $$p! = p^2-p = p(p-1) \quad (\mathrm{mod} \text{ } p^2)$$

• I never knew that we can multiply p throughout the whole equation including (mod p) , that's my truly open-eyed indeed. Wonderful! Thank you. – ABCDEFG user157844 Mar 8 at 11:10
• Well, $a=b \quad (\mathrm{mod} \text{ } p)$ means that there exists $n$ such that $a-b = pn$. So multiplying by any number $q$, you get $aq-bq=pqn$, so $aq=bq \quad (\mathrm{mod} \text{ } pq)$. – TheSilverDoe Mar 8 at 11:12
• Can we avoid to using Chinese remainder theorem by this principle? – ABCDEFG user157844 Mar 8 at 11:15
• No, I don't think so, Chinese remainder theorem helps to solve a system of congruence equations. It does not consist in just algebraic modifications of one equality. – TheSilverDoe Mar 8 at 11:22

Wilson's Theorem states that:

$$(p-1)! = -1 (mod p^{2})$$ ......(a)

and

$$p!=p(p-1)!$$, $$-1=p-1(mod p^{2})$$ .......(b)

applying (b) to (a), we have

$$p!=p(p-1)!=p*-1 (mod p^{2})$$

which implies that

$$p!=p(p-1) (mod p^{2})$$

Note that the $$p$$ above stands for prime numbers and $$21$$ is not a prime number since $$21=3*7$$. Therefore the above statements will not apply, but take for example, 5 is a prime number and

$$5!=5*4*3*2*1=120=5(5-1)=20 (mod 25)$$

$$p! \equiv p(p-1) \pmod{p^2} \Leftrightarrow p^2 \mid p!-p(p-1) \Leftrightarrow p \mid (p-1)!-(p-1) \Leftrightarrow (p-1)! \equiv -1 \pmod{p}$$ If $$p$$ is a prime, then except for the two solutions of $$x^2 \equiv 1 \pmod{p}$$ (which are equal $$\pmod{p}$$ for $$p=2$$), we can pair the numbers in $$2, ... (p-2)$$ in pairs $$(x,y)$$ with $$x \not\equiv y \pmod{p}$$ such that $$xy \equiv 1 \pmod{p}$$, so $$(p-2)! \equiv 1 \pmod{p}$$ and so $$(p-1)! \equiv (p-1)(p-2)! \equiv (p-1) \equiv -1 \pmod{p}$$.