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.
