Converse Fermat's Little Theorem Proof

Prove that if $n > 1$ is a prime if for some a,

$$a^{n - 1} \equiv 1 \pmod{n}$$

while $a^q \not\equiv 1 \pmod{n}$ for each divisor of $n - 1$.

Proof

Before attempt the proof we will prove these two claims.

Claim 1

If $a \equiv b \pmod{n}, then (a, n) = (b, n)$ 

Proof

Since $a \equiv b \pmod{n}$, we have $a - b = n.k \Leftrightarrow b = a - n.q = a + n.k$ for some integers q, k. 

So, proving $(a, n) = (b, n) \Leftrightarrow (a, n) = (a + n.k, n)$

Let $e = (a, n)$, then $e|a, e|n \implies e|(a + n.k) \implies e|(a + k.n, n) *$

Next, let $ f = (a + n.k, n)$, similarly we have $f|a, f|(a + n.k) \implies f|(a + n.k - n.k ) = a \implies f|(a, n) **$

From * and **,

$\therefore e = f \Leftrightarrow (a, n) = (b, n)$, as was to be shown.

Claim 2

If $a^{n - 1} \equiv 1 \pmod{n}$, then $(a, n) = 1$

Proof

Since $a|a^{n - 1} \implies (a, n)|(a^{n - 1}, n)$

where $(a^{n - 1}, n) = (n, 1) = 1$ by Claim 1.

Hence, $(a, n)|1 \implies (a, n) = 1$, as was to be shown.

Now we're ready!

We have $a^{n - 1} \equiv 1 \pmod{n}$, so by Claim 2, $(a, n) = 1$.

Using Euler's theorem, we have $a^{\phi(n)} \equiv 1 \pmod{n}$.

Since $\phi(n) > 0$, by Well-Ordering principle, there exists the least positive

integer $x$ such that $a^{x} \equiv 1 \pmod{n}$.

Next, we will show that if there exists an integer $m, m > x$, and $a^{m} \equiv 1 \pmod{n}$, then $x|m$.

If $x|m$, we're done. Otherwise if $x\not|m$, then

By division algorithm, we have:

$$m = x.q + r \text{ for some integers } q, \text{ where } 0 \leq r < x$$

$\longrightarrow a^{x.q + r} \equiv {a^{x}}^q \cdot a^{r} \equiv a^r \pmod{n}$

Hence, $a^m \equiv a^r \equiv 1 \pmod{n}$

But $x$ is the smallest integer in the set, and $r < x$, therefore $r = 0$.

$\therefore x|m$, as was to be shown.

Now, consider $a^{n - 1} \equiv 1 \pmod{n}$, we see that there exists an $x$ such that $x|(n - 1)$,

And this implies $x$ must be a divisor of $n - 1$, i.e $x = q$, 

Nonetheless, $x^q \not\equiv 1 \pmod{n} \forall$ divisors of $n - 1$.

Hence, $x = n - 1$, and this implies that $n - 1$ is the smallest positive integer such that

$$a^{n - 1} \equiv 1 \pmod{n}$$

By Euler's theorem, we have $a^{\phi(n)} \equiv 1 \pmod{n} \implies (n - 1) \leq \phi(n)$

But from the definition of $\phi(n)$, we know that $\phi(n) \leq (n - 1)$.

So,

$$(n - 1) \leq \phi(n) $$

$$\phi(n) \leq (n - 1) $$

which implies $n - 1 = \phi(n) \implies$ n is prime, as was to be shown.