Ground Plan – Forward direction – Wilson’s Theorem – p is prime $\iff (p-1)!\equiv-1(mod\ p) $.

Question

Lemma 5.3 - I omit proof here - Let p be prime. Then $x^2 \equiv 1 \, (mod p) \iff x \equiv \pm 1 \; (mod p)$

First we establish the result for the first two primes 2, 3. Then prove the result for the remaining primes. for $p=2$, $(2-1)!\equiv 1\equiv-1$ (mod2) $p=3$, $(3-1)! \equiv 2\equiv-1$ (mod3)

Now let the prime $p\geq 5$ and consider the least non-negative residues modulo $p$: $ 1,\ 2,\ 3,\ 4,\ \cdots\ ,\ p-1 $

(1) Why consider $p = 2,3$ separately? http://www.millersville.edu/~bikenaga/number-theory/wilson-fermat/wilson-fermat.html starts with all primes?

By the above Lemma (5.3) we know that the first and last numbers in this list, 1 and $p-1$, is its own inverse. The inverse of the remaining residues 2, 3, 4, $\cdots,\ p-2$ is another number (and not itself) in this list. $\color{magenta}{Why? \quad (♯)}$

(2) Can someone please amplify $\color{magenta}{Why?}$

Consider the linear congruence $ax\equiv 1 \; (mod\ p)$ where $a=2,3,4,\ \cdots,\ p-2$

(3) How can you preconceive to consider this linear congruence? Why?

Since $gcd(a,\ p)=1$, so by the Linear Congruence Theorem, $ax\equiv 1 \; (mod\ p)$ has a unique solution $x\equiv b \; (mod\ p)$, where $b\not\equiv a \; (mod\ p)$ because (♯) means each of the $a=2,3,4,\ \cdots,\ p-2$ is not its own inverse.

This means that residues $a$ and $b$ can be paired up amongst the list $2,\ 3,\ 4,\ \cdots,\ p-2$ such that $ab\equiv 1(mod\ p)$ . I exclude the rest of the proof.

Origin – this better than Jones, p71 Theorem 4.6

Answer 1

(1) Actually, the same proof also works for $2$ and $3$, but -- at least for the case of $2$ -- it should deserve some additional note anyway. For the cases $p=2$ and $p=3$ there are no other terms which should be paired up, that might be the reason to handle them separately.

(2) This $\sharp$ is just lemma 5.3.

(3) Now it seems they go into details to show that inverses exist. Solving $ax\equiv 1\pmod p$ means to find the multiplicative inverse of $a$, which is different from $a$ if $a\not\equiv \pm1$ by lemma 5.3., so all these can be paired up.

Answer 2

For your first question, it is convenient to consider $2$ and $3$ separately from the other primes since the proof flows better when $1$ and $p-1$ are distinct from the other residues.

To answer your second question, consider $(p-a)^2 = 1$. Expanding, we get $p^2 - 2ap + a^2 = 1$, and then once we mod out by $p$, we get $a^2 \equiv 1 \pmod{p}$. Thus, $a \equiv -1$ or $1 \pmod{p}$. We can conclude no other residues except $1$ and $p-1$ can be their own inverse.

For the third, the motivation is that we are simply trying to establish that each residue other than $(p-1)$ and $1$ can be paired with a unique multiplicative inverse. I.e. some residue $a$ cannot be the inverse of both $b$ and $c$. Hence, when we compute $(p-1)!$, each inverse pair multiplied together will give $1$, and only $(p-1)$ will remain. Of course, $p-1 \equiv -1 \pmod{p}$.