Skip to main content

Section 7.2 Applications of Primitive Roots

Remark 7.2.1.

If \(p\) is a prime of the form \(4k + 1,\) then \(x^2 \equiv -1\pmod{p}\) has a solution.

Because \(4\vert p-1,\) there is an \(a\) having order \(4\) modulo \(p,\) so that

\begin{equation*} a^4\equiv 1\pmod{p}. \end{equation*}

So

\begin{equation*} a^4-1\equiv (a^2-1)(a^2 + 1) \equiv 0\pmod{p}. \end{equation*}

This means that either

\begin{equation*} a^2-1\equiv 0\pmod{p} \hspace{5mm} \mathrm{or} \hspace{5mm} a^2 + 1\equiv 0\pmod{p}. \end{equation*}

If \(a^2-1\equiv 0\pmod{p},\) then \(a\) has order \(2\) modulo \(p,\) a contradiction. Thus \(a^2+1\equiv 0\pmod{p},\) and so for this \(a,\) we have \(a^2\equiv -1\pmod{p}.\)

As an application of this (along with one of your homework problems), we can prove a nice result of Fermat.

Section 7.2.1 Fermat's Christmas Theorem

As seen above, Fermat was very interested in squares, and powers in general (as in Fermat's Last Theorem). In 1640, Fermat made a very interesting observation. But first a definiton.

Definition 7.2.1. Gaussian integers.

The Gaussian Integers is the set \(\mathbb{Z}[i].\)

If \(p\) is of the form \(4m + 1,\) then there is an integer \(x\) such that \(x^2\equiv -1\pmod{p}.\) Since \(p\vert x^2+1\) we have that

\begin{equation*} p\vert (x-i)(x+i). \end{equation*}

Since \(p\) does not divide either factor, there exist two complex factors \(a + ib\) and \(c + id\) of \(p\) different from both \(\pm 1\) and \(\pm i\) such that \(a + ib\vert x + i\) and \(c + id\vert x-i\) in \(\mathbb{Z}[i].\) So we have that \(p = (a + ib)(c + id).\) Note that since \(p\) is real we have that \(\overline{p} = p\) and so

\begin{equation*} p = \overline{p} = \overline{(a + ib)(c + id)} = \overline{(a + ib)}\hspace{2mm}\overline{(c + id)} = (a-ib)(c-id). \end{equation*}

Thus

\begin{equation*} p^2 = p\cdot \overline{p} = (a + ib)(c + id)(a - ib)(c - id) = (a^2 + b^2)(c^2 + d^2). \end{equation*}

Since both \(a^2 + b^2, c^2 + d^2\gt 1\) and are integers we have that

\begin{equation*} p = a^2 + b^2 = c^2 + d^2. \end{equation*}

This theorem is known as Fermat's Christmas Theorem since it was announced in a letter to Mersenne dated December 25, 1640. It was not proven by Fermat; it was proven first by Euler many years later.

This proof was taken from the notes of Jànos Bolyai, one of Hungary's most famous mathematicians. Though Bolyai made many investigations in number theory, he known for his discovery of non-Euclidean geometry (specifically, absolute geometry) and his contribution to the theory of complex integers \(\mathbb{Z}[i],\) where

\begin{equation*} \mathbb{Z}[i]=\{x+yi:x,y\in\mathbb{Z}, i^2=-1\}. \end{equation*}

Section 7.2.2 Primitive roots of composite numbers

We now consider composite numbers for a moment.

Consider an integer \(a\) for which \(\gcd(a, mn) = 1.\) Then \(\gcd(a, m) = 1\) and \(\gcd(a, n) = 1.\) Set \(h = \mathrm{lcm}(\varphi(n), \varphi(m))\) and \(d = \gcd(\varphi(n), \varphi(m)).\) Since \(\varphi(n)\) and \(\varphi(m)\) are both even, we have \(d\geq 2.\) So

\begin{equation*} h =\frac{\varphi(n)\varphi(m)}{d}\leq\frac{\varphi(mn)}{2}. \end{equation*}

Now

\begin{equation*} a^h = (a^{\varphi(m)})^{\varphi(n)/d} \equiv 1^{\varphi(n)/d}\equiv 1\pmod{m} \end{equation*}

and similarly \(a^h \equiv 1\pmod{n}.\) Since \(\gcd(m, n) = 1\) we have

\begin{equation*} a^h\equiv 1\pmod{mn} \end{equation*}

so that since \(h\lt \varphi(mn), a\) is not a primitive root of \(mn.\)

Admittedly, results for prime powers are more interesting.

Since \(r\) is a primitive root of \(p,\) we know that the order of \(r\) modulo \(p\) is \(\varphi(p) = p-1.\) Now let \(n\) be the order of \(r\) modulo \(p^2.\) Since any congruence modulo \(p^2\) certainly holds modulo \(p,\) we have that also,

\begin{equation*} r^n\equiv 1\pmod{p}. \end{equation*}

Since \(p-1\) is the order of \(r\) modulo \(p,\) we have that \(p-1\vert n.\) But also, we have \(n\vert \phi(p^2),\) so \(n\vert p(p-1).\) Thus either \(n = p-1\) or \(n = p(p-1).\)

If \(n = p(p-1)\) we are done, so suppose that \(n = p-1\) and consider \(r + p.\) Since \(r\equiv r + p \pmod{p}, r + p\) is also a primitive root of \(p.\) So as above we have that the order \(m\) of \(r + p\) modulo \(p^2\) is either \(p-1\) or \(p(p-1).\) Again, if \(m = p(p-1)\) we are done, so suppose that \(m = p-1.\) Then, using the binomial theorem, we have

\begin{align*} (r + p)^{p-1} \amp = r^{p-1} + (p-1)r^{p-2}p +\binom{p-1}{2}r^{p-3}p^2+\cdots p^{p-1}\\ \amp = r^{p-1} + (p-1)pr^{p-2} \pmod{p^2}\\ \amp = 1+(p-1)pr^{p-2} \pmod{p^2}\\ \amp = 1-pr^{p-2} \pmod{p^2}. \end{align*}

Now if \((r + p)^{p-1}\) is \(1\) modulo \(p^2,\) then \(p^2\vert pr^{p-2}\) and so \(p\vert r^{p-2},\) which is impossible since \(p\) does not divide \(r.\) This contradiction proves the theorem.

We know from the previous lemma that there is a primitive root \(r\) of p that is also a primitive root of \(p^2\) such that

\begin{equation*} r^{p-1}\not\equiv 1\pmod{p^2}. \end{equation*}

We show by induction that for this primitive root and for \(k\geq 2\) that

\begin{equation*} r^{p^{k-2}(p-1)}\not\equiv 1\pmod{p^k}. \end{equation*}

The base case follows from the previous lemma. Now suppose there is some \(k\geq 2\) such that

\begin{equation*} r^{p^{k-2}k(p-1)}\not\equiv 1\pmod{p^k}. \end{equation*}

Since \(\gcd(r, p) = 1,\) we have that \(\gcd(r, p^{k-1}) = 1\) and so using Euler's generalisation of Fermat's little theorem, we have that

\begin{equation*} r^{p^{k-2}(p-1)}\equiv r^{\phi(p^{k-1})} \equiv 1\pmod{p^{k-1}}. \end{equation*}

Thus there is a \(d\) such that \(r^{p^{k-2}(p-1)}=1+dp^{k-1},\) where \(p\) does not divide \(d\) due to the induction hypothesis. As before we use the binomial theorem to give

\begin{equation*} r^{p^{k-1}(p-1)}=(1+dp^{k-1})^p\equiv 1+dp^k \pmod{p^{k+1}}. \end{equation*}

Since \(p\) does not divide \(d,\) this gives the desired non-congruence.

With this result in hand, the result is quite straightforward. Given a primitive root \(r\) of \(p^2\) as above, let \(n\) be the order of \(r\) modulo \(p^k.\) So \(n\vert \phi(p^k),\) which means that \(n\vert p^{k-1}(p-1).\) But also, since \(r^n\equiv 1\pmod{p^k}\) also \(r^n\equiv 1\pmod{p},\) so, like before, \(p-1\vert n.\) Thus \(n = p^t(p-1)\) for some \(t\) in \(\{0,...,k-1\}.\) If \(t\leq k-2,\) then

\begin{equation*} r^{p^{k-2}(p-1)}=(r^{p^{t}(p-1)})^{p^{k-2-t}}\equiv 1\pmod{p^{k}}, \end{equation*}

which contradicts our non-congruence proved above. Thus \(t = k-1\) and \(r\) is a primitive root of \(p^k.\)