Proof of Fermat's Little Theorem using Primitive Roots

Question

I just learned about primitive roots today, and then I thought of this proof of Fermat's Little Theorem. Seeing that most proofs of this theorem aren't simple, I think I'm either completely wrong in my application of primitive roots (must have missed something fundamental, having just learned about them), or primitive roots are extremely powerful. Which one is it?

Proof: We want to prove that if $\gcd(a,p)=1$, with $p$ a prime, then $a^{p-1}\equiv 1\pmod p$. Since $p$ is prime there exists a primitive root $\operatorname{mod}\, p$, say $j$. It is well known that we can write every least residue $\operatorname{mod}\, p$ as a power of $j$, so e.g. we can write $a\equiv j^k$. Thus, it suffices to prove that $a^{p-1}\equiv j^{k(p-1)}\equiv 1\pmod p$. But this is obvious because $j^{k(p-1)}\equiv (j^{p-1})^k\equiv (1)^k\equiv 1\pmod p$ since $\operatorname{ord}_p(j)=p-1$ by definition.

QED

Thanks for your help guys!

Answer 1

A proof from scratch is simple.

There are obviously $p-1$ possible non-zero remainders if you divide a number relatively prime to $p$ by $p$, namely $1,2,\dots,p-1$. Now consider the remainders of $a,2a,3a,\dots,(p-1)a$. They must all be different, because if any two were the same then $p$ would divide their difference. That is impossible since $\gcd(a,p)=1$.

So they must be some arrangement of $1+k_1p,2+k_2p,\dots,p-1+k_{p-1}p$ for some integers $k_i$. Multiplying them all together we get $1\times2\times3\dots\times(p-1)=a^{p-1}\times1\times2\dots\times(p-1)\bmod p$. We can divide by $(p-1)!$ since it is not a multiple of $p$, to get $a^{p-1}=1\bmod p$.

Answer 2

You have given a correct proof of Fermat's Little Theorem.

The reason you have not seen this proof before is twofold:

1. Other proofs of Fermat's Little Theorem naturally generalize to proofs of Euler's Theorem. Euler's Theorem cannot be proven using primitive roots, since there are not primitive roots in general. Further, from the perspective of abstract algebra, both Euler's Theorem and Fermat's Little Theorem are manifestations of an extremely basic theorem of group theory: Lagrange's Theorem.
2. The existence of a primitive root is a very non-trivial fact. (But it is independent of Fermat's Little Theorem, I believe.) Looking again from the perspective of abstract algebra, the existence of primitive roots for certain groups $U_n$ amount to completely understanding the structure of these groups and showing they are cyclic. This is not so easy.