# Proving Wilson's theorem

Wilson's theorem: if $p$ is prime then $(p-1)! \equiv -1(mod$ $p)$

Approach: $$(p-1)!=1*2*3*....*p-1$$

My teacher said in class that the gcd of every integer less than p and p is 1, so every integer has a multiplicative inverse $(mod$ $p)$. He also said that the multiplicative inverses of each integer less than p is in the same set of integers less than p (This idea seems to be right, but does it have to be proven?). the multiplicative inverses of 1 and p-1 are self inverses (Drawing different mod grids, it looks like it's right, but again how is that true?). He concluded the following:

$$1*(p-1)*(a_1a_1^{-1}*.....*a_{{p-3}/2}*{a_{{p-3}/2}}^{-1}) \equiv -1(mod\text{ } p)$$

So he is grouping all the elements with distinct multiplicative inverse. This makes sense because there are p-3 elements with distinct multiplicative inverses and p-3 is even, so we can group them in pairs. How do we know that one multiplicative inverse corresponds to just one number, so we can group them in such an easy way?.

• The last question is a subtlety often overlooked. Show the relation $\,x\sim y\,$ if $\, x=y\,$ or $\,x = y^{-1}$ is an equivalence relation, hence it partitions the nonzero residues (into equivalence classes of size $1$ or $\,2\,)$. If you are familiar with permutations then the classes are the cycles of the permutation $\,x\mapsto x^{-1},\,$ i.e. the orbits of this inversion map. Jul 6 '16 at 4:14
• In $\mathbb F_p$ you have $a^{p-1}$ for all $a\ne 0$ so you have $a^{p-2}$ is the (unique) inverse of $a$. Hence $$1\cdot(2\cdot 2^{p-2})\cdot(3\cdot 3^{p-2})\cdot .....(\frac{p-1}{2})\cdot (\frac{p-1}{2})^{p-2}\cdot (p-1)=(p-1)!=1\cdot(p-1)=-1$$ Jul 6 '16 at 16:52

Note that if $x$ is a multiplicative inverse of $a$ modulo $p$ it's a solution to the follwoing linear diophantine equation: $xa + py = 1$. Adding and subtracting $ap$ we have: $a(x-p) + p(y+a) = 1$. So all solutions for $x$ are equivalent to each other modulo $p$, so therefore we can pick one from the residue class modulo $p$ (the set of non-negative integers less than $p$).

For the other part to see why only $1$ and $p-1$ are self-inverses, note that such a number must satisfy $x^2 \equiv 1 \pmod p \implies p \mid (x-1)(x+1)$. So we have that $x \equiv \pm 1 \pmod p \implies x=1 \text{ or } x=p-1$

• I was able to follow your first claim until the expression $a(x-p)+p(y+a)=1$. What do you mean with all solutions for x are equivalent to each other mod p? Jul 6 '16 at 1:49
• @TheMathNoob Maybe an example will make things clearer. Let $p=11$, then the modular inverse of $3$ is $4$, as $3\cdot 4 \equiv 1 \pmod{11}$. But also note that $3 \cdot 15 \equiv 1 \pmod{11}$. So we can say that both $4$ and $15$ are inverses of $3$ modulo $11$. But note that $4 \equiv 15 \pmod{11}$. So all inverses are equivalent to each other modulo $p$. Jul 6 '16 at 1:52
• ok and how does that show that we can always find a multiplicative inverse less than p? Jul 6 '16 at 1:54
• @TheMathNoob Bezout's Lemma tells us that a the equation $xa + py = 1$ has a solution iff $gcd(x,p) = 1$, but as $1\le x \le p-1$ this is always true, so hence every element of the residue class modulo $p$ has an inverse. Jul 6 '16 at 1:55
• does bezout's Lemma tell us $1 \leq x \leq p-1$?. Sorry yes, $gcd(x,p)=1$ Jul 6 '16 at 2:00

One has indeed an equivalence $$p\text{ is prime }\iff(p-1)!\equiv -1\pmod p$$ (1)$\space p\text{ is prime }\Rightarrow(p-1)!\equiv -1\pmod p$

By Fermat's little theorem and because each of $1,2,3,...(p-2),(p-1)$ is coprime with $p$ we have $(p-2)!\equiv((p-2)!)^{ p-1}\equiv 1 \pmod p\Rightarrow (p-1)!\equiv (p-1)\cdot 1\equiv -1\pmod p$.

(2)$\space (p-1)!\equiv -1\pmod p\Rightarrow p\text{ is prime }$.

Suppose $p$ is composed then its (positive) divisors are in $\{1,2,3,...,(p-2),(p-1)\}$. This implies that $\ g.c.d((p-1)!,p)\gt 1$. Now if $\space (p-1)!\equiv -1\pmod p$ then dividing by a (proper) divisor $d$ of $p$ and of $(p-1)!$ the equality $(p-1)!=-1+pm$ (equivalent to the congruence) one has $d$ must divide $-1$, absurde.Thus $p$ is not composed.