Integers with Primitive Roots

Theorem

Let $n \in \Z: n > 1$.

Then $n$ has a primitive root iff:

• $n = 2$
• $n = 4$
• $n = p^k$, or
• $n = 2 p^k$

where $p > 2$ is prime and $k \ge 1$.

Proof of Necessity

This proof comes in several sections, so as to be able to cover all cases.

The cases where n = 2 and n = 4

• $1$ is trivially a primitive root of $2$.

• $3$ is a primitive root of $4$, as $\phi \left({4}\right) = 2$ and $3^2 = 9 \equiv 1\left({\bmod\, 4}\right)$.

Power of 2 greater than 4: No primitive root

Let $n = 2^k$ where $k \ge 3$.

From Euler Phi Function of a Prime, $\phi \left({2^k}\right) = 2^{k-1}$.

The $2^{k-1}$ least positive residues prime to $2^k$ are the odd integers up to $2^k - 1$.

What we need to show is that for any odd integer $a$ there exists a positive integer $r < 2^{k-1}$ such that $a \equiv 1 \left({\bmod\, 2^k}\right)$.

We assert that $r = 2^{k-2}$ has exactly this property, which we prove by induction.

For all $k \in \N^*$, let $P \left({k}\right)$ be the proposition $a^{\left({2^{k-2}}\right)} \equiv 1 \left({\bmod\, 2^k}\right)$.

Basis for the Induction

• $P(3)$ is true, as follows:

$k = 3 \implies 2^k = 8, 2^{k-2} = 2^1 = 2$.

The odd integers less than $8$ are $1, 3, 5, 7$. So:

	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle 1^2\)	\(=\)	\(\displaystyle 1\)	\(\displaystyle \)	\(\displaystyle \equiv 1 \left({\bmod\, 8}\right)\)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle 3^2\)	\(=\)	\(\displaystyle 9\)	\(\displaystyle \)	\(\displaystyle \equiv 1 \left({\bmod\, 8}\right)\)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle 5^2\)	\(=\)	\(\displaystyle 25\)	\(\displaystyle \)	\(\displaystyle \equiv 1 \left({\bmod\, 8}\right)\)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle 7^2\)	\(=\)	\(\displaystyle 49\)	\(\displaystyle \)	\(\displaystyle \equiv 1 \left({\bmod\, 8}\right)\)	\(\displaystyle \)

Thus $P(3)$ holds.

This is our basis for the induction.

Induction Hypothesis

• Now we need to show that, if $P \left({h}\right)$ is true, where $h \ge 3$, then it logically follows that $P \left({h+1}\right)$ is true.

So this is our induction hypothesis:

$a^{\left({2^{h-2}}\right)} \equiv 1 \left({\bmod\, 2^h}\right)$.

Then we need to show:

$a^{\left({2^{h-1}}\right)} \equiv 1 \left({\bmod\, 2^{h+1}}\right)$.

Induction Step

We can write our induction hypothesis more conveniently as $a^{\left({2^{h-2}}\right)} = 1 + m 2^h$ for some $m \in \Z$.

Hence:

	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \left({a^{\left({2^{h-2} }\right)} }\right)^2\)	\(=\)	\(\displaystyle \left({1 + m 2^h}\right)^2\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	squaring both sides
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(=\)	\(\displaystyle 1 + 2 \left({m 2^h}\right) + \left({m 2^h}\right)^2\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(=\)	\(\displaystyle 1 + 2^{h+1} \left({m + m^2 2^{h-1} }\right)\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\equiv\)	\(\displaystyle 1\)	\(\displaystyle \)	\(\displaystyle \left({\bmod\, 2^{h+1} }\right)\)	\(\displaystyle \)

But $\left({a^{\left({2^{h-2}}\right)}}\right)^2 = a^{\left({2^{h-2}}\right)} a^{\left({2^{h-2}}\right)} = a^{\left({2^{h-2} + 2^{h-2}}\right)} = a^{2 \left({2^{h-2}}\right)} = a^{\left({2^{h-1}}\right)}$.

So $P \left({h}\right) \implies P \left({h+1}\right)$ and the result follows by the Principle of Mathematical Induction.

Therefore $\forall k \ge 3: a^{\left({2^{k-2}}\right)} \equiv 1 \left({\bmod\, 2^k}\right)$.

Two Coprime Divisors Greater than 2: No Primitive Root

Let us take $n = r s$ where $r > 2, s > 2, r \perp s$.

Let $a \perp r s$.

From Euler Phi Function Even for Argument Greater than 2, $\phi \left({r}\right)$ and $\phi \left({s}\right)$ are both even.

So $\displaystyle \frac {\phi \left({r}\right)} 2$ and $\displaystyle \frac {\phi \left({s}\right)} 2$ are both integers, and hence so is $\displaystyle \frac {\phi \left({r s}\right)} 2$.

As $a \perp r s$ we have that $a \perp r$ which gives $a^{\phi \left({r}\right)} \equiv 1 \left({\bmod\, r}\right)$ from Euler's Theorem.

So putting $\displaystyle k = \frac {\phi \left({r s}\right)} 2$, we have:

	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle a^k\)	\(=\)	\(\displaystyle a^{\frac {\phi \left({r}\right) \phi \left({s}\right)} 2}\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(=\)	\(\displaystyle \left({a^{\phi \left({r}\right)} }\right)^{\frac {\phi \left({s}\right)} 2}\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\equiv\)	\(\displaystyle \left({1}\right)^{\frac {\phi \left({s}\right)} 2}\)	\(\displaystyle \)	\(\displaystyle \left({\bmod\, r}\right)\)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\equiv\)	\(\displaystyle 1\)	\(\displaystyle \)	\(\displaystyle \left({\bmod\, r}\right)\)	\(\displaystyle \)

Interchanging the roles of $r$ and $s$ shows that $a^k \equiv 1 \left({\bmod\, s}\right)$ as well.

So we see that $a^k \equiv 1 \left({\bmod\, r s}\right)$.

Thus for any $a$, we have $a^k \equiv 1 \left({\bmod\, n}\right)$ where $\displaystyle k = \frac {\phi \left({n}\right)} 2 < \phi \left({n}\right)$.

Hence $n$ has no primitive root.

$\blacksquare$

Hence we see that in order for $n$ to have a primitive root, it is necessary that:

• $n = 2$
• $n = 4$
• $n = p^k$, or
• $n = 2 p^k$

where $p > 2$ is prime and $k \ge 1$.

Proof of Sufficiency

We have covered the cases where $n = 2$ and $n = 4$.

Now we need to show that if:

• $n = p^k$, or
• $n = 2 p^k$

where $p > 2$ is prime and $k \ge 1$, then $n$ has a primitive root.

Notes

This was first proved by Gauss in 1801.