Euclidean Algorithm and Wilson Theorem

Goal

• We seek to prove the famous Wilson Theorem:

        $(p-1)! \equiv (-1) \pmod{p}$ for odd prime $p$

• The easy way to prove this Theorem is to use the Bezout Lemma.
• And to prove the Bezout Lemma, we would need to investigate the Euclidean Algorithm!
• But if someone asks, just tell them these theorems are important in and of themselves.

Euclidean Algorithm: Frenzied Subtraction

Euclidean Algorithm by Java.

This algorithm is a simple Ancient method to find the greatest common factor of any two positive integers. 

Think about a number $k=xy$ as $x$ groups, each containing $y$ elements.

So $24=12.2$ will be two dozens of eggs

So $(a,b)=m$ means that if we can divide $a$ eggs evenly into $m$ boxes and $b$ eggs evenly into $m$ boxes. Furthermore, $m$ will be the largest possible number for this common number of boxes.

Now pretend that we already know $m$, we will arrange $a,b$ in $m$ groups, and subtract $b$ from $a$. The goal is to force $m$ to reveal itself. We will constantly reduce $a$ by $b$ until we cannot reduce $a$ further. In essence, we find the remainder of $a$ when divided by $b$. 

If it's not obvious, try to find the remainder when $14$ is divided $3$. We'll find very quickly that $14=3.4+1$ so the remainder is $1$. The way we do it is to call the remainder $r$, so $12=3.k+r$ or $12-3.k=r$. We increase $k$ until $r$ becomes very small that if we increase $k$ more, $r$ will become negative. $12-3.5=-3$. 

We notice that when we subtract $b$ from $a$, we're still holding the information about $m$. In other words, we just reduce the number of eggs in each box, but the number of boxes, $m$, stay the same.

Remainder when 9 is divided by 3

The information about the the number of boxes is also contained in the remainder. Formally, $(a,b)=m$ implies that $m|r$, and more powerfully, $(a,b)=(b,r)$.

$r$ is very small compared to the original $a$ and is smaller than $b$. Now we can ignore $a$, and work with $b,r$ in the same manner. We find the remainder when $b$ is divided by $r$ by constantly reducing $b$. 

Note that every stage of the process involves reducing a number. Because we start with $a,b$, two finite numbers, this process must eventually end. Otherwise, we will get negative numbers. 

The process ends when we have no remainder. 

Example: Find (72, 20).

72 = 20.3 + 12

20 = 12.1 +  8

12 = 8.1   +  4

8   = 4.2   +  0

Now we don't have any remainder and $(72,20)=(20,12)=(12,8)=(8,4)=(4,0)=4$

Bezout Lemma

If $(a,b)=d$, then there exist integers $x,y$ (not necessarily positive) such that $ax+by=d$

This follows immediately from Extended Euclidean Algorithm (Wiki).

Wilson's Theorem

Now we define the multiplicative inverse of $a$ as $a^{-1}$ such that $aa^{-1}\equiv 1 \pmod{m} (*)$. We claim that it's always possible to find the multiplicative inverse of $a$ provided that $(a,m)=1$. We reduce the congruence relation $(*)$ to $aa^{-1}-1=ym$ or $aa^{-1}-ym=1$. This is a straight-forward application of the Bezout's Lemma. 

Now we're ready to prove the Wilson theorem. Note that every member excluding $0$ of the residue class of $p$ is coprime to $p$ (since $p$ is prime). Then there always exist inverses for those numbers.

We easily prove that the inverses are unique. Or if $b,c$ are both inverses of $a$ then $ ab \equiv 1 \equiv ac \pmod{p}$. Cancel $a$ as usual and deduce that $b,c$ are not distinct.

Since $p$ is defined to be odd, $p-1$ will be even. In the multiplication $1.2.3...(p-1)!$, we pair each number with their multiplicative inverses like $aa^{-1}bb^{-1}...$. So wouldn't $(p-1)! \equiv 1.1.1... \equiv 1 \pmod{m}$.

Well, it would be true except there exist some numbers that are the multiplicative inverses of themselves, so you cannot really pair them with another number. That is $x^2 \equiv 1 \pmod{m}$. Or $x^2-1 \equiv (x-1)(x+1) \equiv 0 \pmod{p}$. Since $p$ is a prime $p|(x-1)$ or $p|(x+1)$. And since $x<p$, $x$'s that satisfy such congruences are $1$ and $-1$ or $p-1$. So now we have exactly two numbers that are exceptionally creepy and marry themselves. The rest $p-3$ numbers are totally normal, and we get $1$ when multiplying them. Therefore, $(p-1)! \equiv 1.(-1)aa^{-1}bb^{-1}... \equiv 1.(-1) \equiv (-1) \pmod{m}$.