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.


Thanks for your help guys!

  • 3
    $\begingroup$ This is correct, but not surprising. The existence of a primitive root modulo $p$ is stronger than Fermat's Little Theorem. In other words: yes, you can derive FLT from the existence primitive roots like this, but it is an overkill. $\endgroup$ – Dan Shved Sep 4 '14 at 15:10
  • 1
    $\begingroup$ Long story short: you are right, primitive roots are powerful. $\endgroup$ – Dan Shved Sep 4 '14 at 15:12
  • 3
    $\begingroup$ Primitive roots are powerful! However, I disagree with the assessment that “most proofs of [FLittleT] aren't simple” — see <en.wikipedia.org/wiki/…> for several elementary and fairly simple proofs (and note there are others). $\endgroup$ – Kieren MacMillan Sep 4 '14 at 15:24
  • $\begingroup$ Worth repeating: Primitive roots are most powerful! For example, once you know about primitive roots, RSA public/private key encryption is absolutely trivial!. $\endgroup$ – gnasher729 Jul 3 '15 at 14:32

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.

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$.

  • $\begingroup$ Read the question again: the user is asking for a proof verification. Although correct, the proof in your post does not answer the question. In case you were wondering about the downvotes. $\endgroup$ – punctured dusk Jan 15 '15 at 17:35
  • $\begingroup$ @barto Thanks. But I gave up on StackExchange math after discovering what it was like over a 2-3 week period. :) $\endgroup$ – almagest Jan 15 '15 at 18:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.