How do you prove an arbitrary number $n$ has no primitive roots without finding all numbers less than $n$ which are also coprime to $n$ and exhausting that none of the order of these numbers modulo $n$ are equal to $\phi(n)$?
Asked
Active
Viewed 5,139 times
2 Answers
4
There is a known result about this. It's not especially easy to prove.
Theorem. An integer $n\ge2$ has a primitive root if and only if it is one of the following: $2$, $4$, $p^\alpha$, $2p^\alpha$, where $p$ is prime, $p\ne2$, and $\alpha\ge1$.
So for example $47$ has primitive roots, $48$ doesn't, $49$ does, $50$ does, $51$ doesn't.
David
- 82,662
-
Do you think you can provide a proof of this theorem? I understand that if a number is not of this form that it does not have a primitive root, but I do not understand why that is so. – ddresner8 Nov 20 '14 at 05:10
-
If you Google "primitive roots theorem" you will find a proof. The first one I looked at was nine pages long, so it's a bit lengthy to give here. – David Nov 20 '14 at 05:13
-
Pretty much any intro number theory textbook should have a proof, as well. – Gerry Myerson Nov 20 '14 at 06:25
-
@ddresner8 This article by Amin Witno was my first encounter with a proof of the entire theorem, I can recommend it: http://www.philadelphia.edu.jo/math/witno/notes/won5.pdf – Bart Michels Nov 20 '14 at 19:41
2
The key observation, which leads to half of the main theorem, is that
If $n=ab$, where $a,b >1$ are odd and coprime, then $n$ does not have a primitive root because for $m=lcm(\phi(a),\phi(b))$ we have $x^m \equiv 1 \bmod n$ for all $x$ coprime with $n$. Note that $m < \phi(n)$ because $\phi(a)$ and $\phi(b)$ are both even.
The harder part of the main theorem is the existence of primitive roots for primes and powers of primes.
lhf
- 216,483