0
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ Wilson's theorem will get you most of the way $\endgroup$ – Henry Mar 8 at 10:32
  • 1
    $\begingroup$ 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! $\endgroup$ – AlessioDV Mar 8 at 10:58
  • $\begingroup$ it also reduces to $(p-2)!\equiv 1 \bmod p^2$ $\endgroup$ – Roddy MacPhee Mar 10 at 13:26
3
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – ABCDEFG user157844 Mar 8 at 11:10
  • $\begingroup$ 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)$. $\endgroup$ – TheSilverDoe Mar 8 at 11:12
  • $\begingroup$ Can we avoid to using Chinese remainder theorem by this principle? $\endgroup$ – ABCDEFG user157844 Mar 8 at 11:15
  • 1
    $\begingroup$ 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. $\endgroup$ – TheSilverDoe Mar 8 at 11:22
1
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.