5.3: The Existence of Primitive Roots
 Page ID
 8847
\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)
\( \newcommand{\vecd}[1]{\overset{\!\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)
In this section, we demonstrate which integers have primitive roots. We start by showing that every power of an odd prime has a primitive root and to do this we start by showing that every square of an odd prime has a primitive root.
If \(p\) is an odd prime with primitive root \(r\), then one can have either \(r\) or \(r+p\) as a primitive root modulo \(p^2\).
Notice that since \(r\) is a primitive root modulo \(p\), then \[ord_pr=\phi(p)=p1.\] Let \(m=ord_{p^2}r\), then \[r^m\equiv 1(mod \ p^2).\] Thus \[r^m\equiv 1(mod \ p).\] By Theorem 54, we have \[p1\mid m.\] By Exercise 7 of section 6.1, we also have that \[m\mid \phi(p^2).\] Also, \(\phi(p^2)=p(p1)\) and thus \(m\) either divides \(p\) or \(p1\). And since \(p1\mid m\) then we have \[m=p1 \ \ \mbox{or} \ \ m=p(p1).\] If \(m=p(p1)\) and \(ord_{p^2}r=\phi(p^2)\) then \(r\) is a primitive root modulo \(p^2\). Otherwise, we have \(m=p1\) and thus \[r^{p1}\equiv 1(mod \ p^2).\] Let \(s=r+p\). Then \(s\) is also a primitive root modulo \(p\). Hence, \(ord_{p^2}s\) equals either \(p1\) or \(p(p1)\). We will show that \(ord_{p^2}s\neq p1\) so that \(ord_{p^2}s=p(p1)\). Note that \[\begin{aligned} s^{p1}=(r+p)^{p1}&=&r^{p1}+(p1)r^{p2}p+...+p^{p1}\\&=& r^{p1}+(p1)p.r^{p2}(mod \ p^2).\end{aligned}\] Hence \[p^2\mid s^{p1}(1pr^{p2}.\] Note also that if \[p^2 \mid (s^{p1}1),\] then \[p^2\mid pr^{p2}.\] Thus we have \[p\mid r^{p2}\] which is impossible because \(p\nmid r\). Because \(ord_{p^2}s\neq p1\), we can conclude that \[ord_{p^2}s=p(p1)=\phi(p^2).\] Thus, \(s=r+p\) is a primitive root of \(p^2\).
Notice that 7 has 3 as a primitive root. Either \(ord_{49}3=6\) or \(ord_{49}3=42\). But since \(3^6\not\equiv 1(mod \ 49)\). Hence \(ord_{49}3=42\). Hence 3 is a primitive root of 49.
We now show that any power of an odd prime has a primitive root.
Let \(p\) be an odd prime. Then any power of \(p\) is a primitive root. Moreover, if \(r\) is a primitive root modulo \(p^2\), then \(r\) is a primitive root modulo \(p^m\) for all positive integers \(m\).
By Theorem 62, we know that any prime \(p\) has a primitive root \(r\) which is also a primitive root modulo \(p^2\), thus \[\label{1} p^2\nmid (r^{p1}1).\] We will prove by induction that \[\label{2} p^m\nmid (r^{p^{m2}(p1)}1)\] for all integers \(m\geq 2\). Once we prove the above congruence, we show that \(r\) is also a primitive root modulo \(p^m\). Let \(n=ord_{p^m}r\). By Theorem 54, we know that \(n\mid \phi(p^m)\). Also, we know that \(\phi(p^m)=p^m(p1)\). Hence \(n\mid p^m(p1)\). On the other hand, because \[p^m\mid (r^n 1),\] we also know that \[p\mid (r^n1).\] Since \(\phi(p)=p1\), we see that by Theorem 54, we have \(n=l(p1)\). also \(n\mid p^{m1}(p1)\), we have that \(n=p^s(p1)\), where \(0 \leq s\leq m1\). If \(n=p^s(p1)\) with \(s\leq m2\), then \[p^k\mid r^{p^{m2}(p1)}1,\] which is a contradiction. Hence \[ord_{p^m}r=\phi(p^m).\]
We prove now ([2]) by induction. Assume that our assertion is true for all \(m\geq 2\). Then \[p^m\nmid (r^{p^{m2}(p1)}1).\] Because \((r,p)=1\), we see that \((r,p^{m1})=1\). We also know from Euler’s theorem that \[p^{m1}\mid (r^{p^{m2}(p1)}1).\] Thus there exists an integer \(k\) such that \[r^{p^{m2}(p1)}=1+kp^{m1}.\] where \(p\nmid k\) because \(r^{p^{m2}(p1)}\not\equiv 1(mod \ p^m)\). Thus we have now \[\begin{aligned} r^{p^{m1}(p1)}&=&(1+kp^{m1})^p\\ &\equiv&1+kp^m(mod \ p^{m+1})\end{aligned}\] Because \(p\nmid k\), we have \[p^{m+1}\nmid (r^{p^{m1}(p1)}1).\]
Since 3 is a primitive root of 7, then 3 is a primitive root for \(7^k\) for all positive integers \(k\).
In the following theorem, we prove that no power of 2, other than 2 or 4, has a primitive root and that is because when \(m\) is an odd integer, \(ord_2^km\neq \phi(2^k)\) and this is because \(2^k\mid (a^{\phi(2^k)/2}1)\).
If \(m\) is an odd integer, and if \(k\geq 3\) is an integer, then \[m^{2^{k2}}\equiv 1(mod \ 2^k).\]
We prove the result by induction. If \(m\) is an odd integer, then \(m=2n+1\) for some integer \(n\). Hence, \[m^2=4n^2+4n+1=4n(n+1)+1.\] It follows that \(8\mid (m^21)\).
Assume now that \[2^k\mid (m^{2^{k2}}1).\] Then there is an integer \(q\) such that \[m^{2^{k2}}=1+q.2^{k}.\] Thus squaring both sides, we get \[m^{2^{k1}}=1+q.2^{k+1}+q^22^{2k}.\] Thus \[2^{k+1}\mid (m^{2^{k1}}1).\]
Note now that 2 and 4 have primitive roots 1 and 3 respectively.
We now list the set of integers that do not have primitive roots.
If \(m\) is not \(p^a\) or \(2p^a\), then \(m\) does not have a primitive root.
Let \(m=p_1^{s_1}p_2^{s_2}...p_i^{s_i}\). If \(m\) has a primitive root \(r\) then \(r\) and \(m\) are relatively prime and \(ord_mr=\phi(m)\). We also have, we have \((r,p^s)=1\) where \(p^s\) is of the primes in the factorization of \(m\). By Euler’s theorem, we have \[p^s\mid (r^{\phi(p^s)}1).\] Now let \[L=[\phi(p_1^{s_1}), \phi(p_2^{s_2}),...,\phi(p_i^{s_i})].\] We know that \[r^L\equiv 1(mod \ p_k^{s_k})\] for all \(1\leq k\leq m\). Thus using the Chinese Remainder Theorem, we get \[m\mid (r^L1),\] which leads to \(ord_mr=\phi(m)\leq L\). Now because \[\phi(m)=\phi(p_1^{s_1})\phi(p_2^{s_2})...\phi(p_n^{s_n})\leq [\phi(p_1^{s_1}),\phi(p_2^{s_2}),...,\phi(p_n^{s_n})].\] Now the inequality above holds only if \[\phi(p_1^{s_1}),\phi(p_2^{s_2}),...,\phi(p_n^{s_n})\] are relatively prime. Notice now that by Theorem 41, \[\phi(p_1^{s_1}),\phi(p_2^{s_2}),...,\phi(p_n^{s_n})\] are not relatively prime unless \(m=p^s\) or \(m=2p^s\) where \(p\) is an odd prime and \(t\) is any positive integer.
We now show that all integers of the form \(m=2p^s\) have primitive roots.
Consider a prime \(p\neq 2\) and let \(s\) is a positive integer, then \(2p^s\) has a primitive root. In fact, if \(r\) is an odd primitive root modulo \(p^s\), then it is also a primitive root modulo \(2p^s\) but if \(r\) is even, \(r+p^s\) is a primitive root modulo \(2p^s\).
If \(r\) is a primitive root modulo \(p^s\), then \[p^s\mid (r^{\phi(p^s)}1)\] and no positive exponent smaller than \(\phi(p^s)\) has this property. Note also that \[\phi(2p^s)=\phi(p^s),\] so that \[p^s\mid (r^{\phi(2p^s)}1).\]
If \(r\) is odd, then \[2\mid (r^{\phi(2p^s)}1).\] Thus by Theorem 56, we get \[2p^s\mid (r^{\phi(2p^s)}1).\] It is important to note that no smaller power of \(r\) is congruent to 1 modulo \(2p^s\). This power as well would also be congruent to 1 modulo \(p^s\) contradicting that \(r\) is a primitive root of \(p^s\). It follows that \(r\) is a primitive root modulo \(2p^s\).
While, if \(r\) is even, then \(r+p^s\) is odd. Hence \[2\mid ((r+p^s)^{\phi(2p^s)}1).\]
Because \(p^s\mid (r+p^sr)\), we see that \[p^s\mid ((r+p^s)^{\phi(2p^s)}1).\] As a result, we see that \(2p^s\mid ((r+p^s)^{\phi(2p^s)}1)\) and since for no smaller power of \(r+p^s\) is congruent to 1 modulo \(2p^s\), we see that \(r+p^s\) is a primitive root modulo \(2p^s\).
As a result, by Theorem 63, Theorem 65 and Theorem 66, we see that
The positive integer \(m\) has a primitive root if and only if \(n=2,4, p^s\) or \(2p^s\)
for prime \(p\neq 2\) and \(s\) is a positive integer.
Exercises

Which of the following integers 4, 12, 28, 36, 125 have a primitive root.

Find a primitive root of 4, 25, 18.

Find all primitive roots modulo 22.

Show that there are the same number of primitive roots modulo \(2p ^s\) as there are modulo \(p^s\), where \(p\) is an odd prime and \(s\) is a positive integer.

Find all primitive roots modulo 25.

Show that the integer \(n\) has a primitive root if and only if the only solutions of the congruence \(x^2\equiv 1(mod n)\) are \(x\equiv \pm1 (mod \ n)\).
Contributors
Dr. Wissam Raji, Ph.D., of the American University in Beirut. His work was selected by the Saylor Foundation’s Open Textbook Challenge for public release under a Creative Commons Attribution (CC BY) license.