Skip to main content

Section 7.1 Primitive Roots

Definition 7.1.1.

If \(\gcd(a, n) = 1\) and \(a\) has order \(\varphi(n)\) modulo \(n,\) then \(a\) is a primitive root of the integer \(n.\)

\(2\) is a primitive root of \(13.\)

If \(n\gt 1\) and \(F_n = 2^{2^{n}}+1\) is a prime, then \(2\) is not a primitive root of \(F_n.\) (Clearly \(2\) is a primitive root of \(F_1 = 5.\)) Note that

\begin{equation*} 2^{2^{n+1}}-1=(2^{2^n}+1)(2^{2^n}-1), \end{equation*}

so that

\begin{equation*} 2^{2^{n+1}}\equiv 1\pmod{F_n} \end{equation*}

which implies that the order of \(2\) modulo \(F_n\) does not exceed \(2^{n+1}.\) But if \(F_n\) is assumed to be prime, then

\begin{equation*} \varphi(F_n) = F_n-1 = 2^{2^n}. \end{equation*}

Since \(n\gt 1,\) it is clear that \(2^{2^n}\gt 2^{n+1},\) so that \(2\) cannot be a primitive root of \(F_n.\)

Let \(\gcd(a, n) = 1\) and suppose \(a\) is a primitive root of \(n.\) Clearly \(\gcd(a^i,n)=1\) for all \(i,\) so that \(a_i\in U_n\) for all \(i = 1, 2,..., \varphi(n).\) Also the set

\begin{equation*} \{a, a^2, a^3,..., a^{\varphi(n)}\} \end{equation*}

consists of \(\varphi(n)\) incongruent elements. Thus \(U_n = \{a, a^2, a^3,..., a^{\varphi(n)}\}.\)

Suppose that \(n\) has a primitive root \(a.\) Then there are \(\varphi(\varphi(n))\) elements \(a^h\) with

\begin{equation*} a^h\in Un = \{a, a^2, a^3,..., a^{\varphi(n)}\} \end{equation*}

where \(\gcd(h, \varphi(n)) = 1.\) By Theorem 7.1.4, these are all of the primitive roots of \(n.\)

Since \(d\vert p-1\) we have \(p-1 = dk\) for some \(k.\) Thus

\begin{equation*} x^{p-1}- 1 = (x^d-1)(x^{d(k-1)} + x^{d(k-2)}+\cdots +x^{d}+1)=(x^d-1)f(x). \end{equation*}

Now \(f(x)\) has degree \(d(k-1) = p-1-d,\) so by a previous theorem, we have that

\begin{equation*} f(x) \equiv 0\pmod{p} \end{equation*}

has at most \(p-1-d\) solutions. Now by Fermat's Little Theorem we know that

\begin{equation*} x^{p-1}\equiv 1\pmod{p} \end{equation*}

has exactly \(\varphi(p) = p-1\) solutions, precisely \(x = 1, 2, 3,..., p-1.\)

Any solution of \(x^{p-1}\equiv 1\pmod{p}\) is that is not a solution of \(f(x)\equiv 0\pmod{p},\) must satisfy \(x^d-1 \equiv 0\pmod{p}.\) Since \(x^{p-1}-1 \equiv 0\pmod{p}\) has \(p-1\) solutions and \(f(x)\equiv 0\pmod{p}\) has at most \(p-1-d\) solutions, there are at least

\begin{equation*} p-1-(p-1-d) = d \end{equation*}

solutions to \(x^d-1\equiv 0\pmod{p}.\) Again since \(x^d-1 \equiv 0\pmod{p}\) has at most \(d\) solutions, we have that the congruence \(x^d-1 \equiv 0\pmod{p}\) has exactly \(d\) solutions.

Let \(d\vert p-1\) and \(f(d)\) denote the number of integers \(k, 1\leq k\leq p-1,\) that have order \(d\) modulo \(p.\) Because each integer between \(1\) and \(p-1\) has order \(d\) for some \(d\vert p- 1,\)

\begin{equation*} p-1 = \sum_{d\vert p-1} f(d). \end{equation*}

Recall that also we have

\begin{equation*} p-1 = \sum_{d\vert p-1} \varphi(d), \end{equation*}

so that

\begin{equation*} \sum_{d\vert p-1}\varphi(d)=\sum_{d\vert p-1}f(d). \end{equation*}

To show that \(f(d) = \varphi(d)\) for each divisor \(d\) of \(p -1,\) it is enough to show that \(f(d)\geq \varphi(d).\)

To this end, let \(d\) be a divisor of \(p-1.\) If \(f(d) = 0,\) then we are done, so suppose that \(f(d)\gt 0;\) that is, there is an integer \(a\) with order \(d\) modulo \(p.\) Then the \(d\) integers

\begin{equation*} a, a^2,..., a^d \end{equation*}

are incongruent modulo \(p\) and each of them satisfies the polynomial congruence

\begin{equation*} x^d-1\equiv 0 \pmod{p}. \end{equation*}

Since there can be only \(d\) solutions, we have found all of them. It follows that any integer \(a\) having order \(d\) modulo \(p\) is congruent to one of \(a, a^2,..., a^d.\) But only \(\varphi(d)\) of these powers have order \(d\) modulo \(p,\) namely those \(a^k\) where \(\gcd(k, d) = 1.\) Thus \(f(d) = \varphi(d).\)