Originally Posted by

**Deadstar** As I was typing this out I realized I had more questions than I thought...

Theorem

Let $\displaystyle n > 1$, and suppose that for every prime factor $\displaystyle q$ of $\displaystyle n-1$ there is an integer $\displaystyle a$ such that,

$\displaystyle a^{n-1} \equiv 1 (\textrm{mod } n)

$

but,

$\displaystyle a^{\tfrac{n-1}{q}} \not\equiv 1 (\textrm{mod } n)$

Then $\displaystyle n$ is prime.

**Proof**

We want to show that $\displaystyle \varphi(n)$ = $\displaystyle n-1$ which implies that $\displaystyle n$ is prime.

Consider the group $\displaystyle \mathbf{Z}_n^X = \big{\{}a:1 \leq a < n, \, \gcd(a,n) = 1 \big{\}}$ where $\displaystyle \#\mathbf{Z}_n^X= \varphi(n)$.

We look at the subgroup $\displaystyle H$ of $\displaystyle \mathbf{Z}_n^X$ generated by all $\displaystyle a_q$'s. *(Does this simply mean all the $\displaystyle q$ values that divide $\displaystyle n-1$)*

As $\displaystyle a_q^{n-1} = \varphi(n)$ *(My notes are unclear here so correct me if that part is wrong, I suspect it is)*, the exponent of $\displaystyle H$ divides $\displaystyle n-1$ *(What exponent?)*.

But the exponent can't be a proper factor of $\displaystyle n-1$ as,

$\displaystyle a^{\tfrac{n-1}{q}} \not\equiv 1 (\textrm{mod } H)$ *(Should $\displaystyle H$** be there? I don't fully understand that conclusion)*.

So the exponent = $\displaystyle n-1$.

But then exponent|#H and $\displaystyle \#H|\#Z = \varphi(n)$ so $\displaystyle n-1|\varphi(n)$.

As $\displaystyle \varphi(n) \leq n-1$, $\displaystyle \varphi(n) = n-1$. Q.E.D.

Lines 4-7 of the proof is what I'm not sure about.