5
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Bill Dubuque Jul 6 '16 at 4:14
  • $\begingroup$ 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$$ $\endgroup$ – Piquito Jul 6 '16 at 16:52
6
$\begingroup$

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$

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – TheMathNoob Jul 6 '16 at 1:49
  • $\begingroup$ @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$. $\endgroup$ – Stefan4024 Jul 6 '16 at 1:52
  • $\begingroup$ ok and how does that show that we can always find a multiplicative inverse less than p? $\endgroup$ – TheMathNoob Jul 6 '16 at 1:54
  • $\begingroup$ @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. $\endgroup$ – Stefan4024 Jul 6 '16 at 1:55
  • $\begingroup$ does bezout's Lemma tell us $1 \leq x \leq p-1$?. Sorry yes, $gcd(x,p)=1$ $\endgroup$ – TheMathNoob Jul 6 '16 at 2:00
1
$\begingroup$

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.

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