In first proof of Wilson's theorem on wikipedia. It is written that "So for each of these integers a there is another b such that ab ≡ 1 (mod p).
" (Here 'a' and 'b' are from {2,..,p-2} and p is prime). It doesn't seems that obvious to me, is there any explanation for this?
Proof of Wilson's Theorem
3 Answers
It's because every residue in ${1, 2, \ldots, p-2, p-1}$ has an inverse mod $p$. (This follows from the Euclidean algorithm, since ${1, 2, \ldots, p-1}$ are all relatively prime to $p$.) $ 1^{-1} = 1 \text{ and } (-1)^{-1} = -1 $ but these are the only numbers which are their own inverses, and all the other residues pair up as required.
We know that if a
relatively prime to p
and $b,c\in \mathbb{Z}\space\&\space b,c \neq 0\space \&\space a.b\equiv a.c \bmod{p} \Rightarrow b\equiv c \bmod{p}$ form this lemma and Pigeonhole Principle we have: $if \space\forall b \in {1,..p-1} \space a.b\not\equiv 1 \bmod{p} \Rightarrow \exists c,d \space such\space that\space c \neq d\space\&\space c\equiv d \bmod{p} $and we know c,d
are between 1,p-1
and from above we have that c = d
so this is a contradicting the fact $c\neq d$.
The possible residues for prime p are 1, 2, 3, ..., p-1. Any of these residues can occur when any integer (how huge or small that may be) is divided into p. Keep aside first and last residues (1 & p-1). We are left with 2,3,4,....,p-2. The number of residues (CRS) for p = p-1 which is even because p is odd. Leaving 1 & p-1 from the set again provides even number of residues. We can pair these residues to form (p-3)/2 pairs in such a way that the product of each when divided by p leaves residue 1. Thus if all pairs are multiplied together, the residue of final product will be 1 because 1 multiplied to any number of times will be 1. Now these pairs and the product reflect product of residues: 2.3.4.5....p-2. This equals to (p-2)!. The result is (p-2)! ≡ 1 (mod p). Now we multiply this with product of two left residues : 1(p-1). We get: (p-2)! (p-1) ≡ 1(p-1) ; (p-1)! ≡ -1 (mod p); The last equation is Wilson's theorem. Implications: If p is prime then (p-1)! divided by p leaves residue = (p-1). This residue so needs +1 to become divisible by p. Hence the equation: (p-1)!≡ -1 (mod p). Again (p-2)! - 1 is divisible by p.
-
0What is CRS abbreviated for? – 2018-09-14