Integers with Primitive Roots

From ProofWiki
Jump to: navigation, search

Theorem

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

Then $n$ has a primitive root if and only if one of the following holds:

$n = 2$
$n = 4$
$n = p^k$
$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 \pmod 4$


Power of $2$ greater than $4$: No primitive root

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

From Euler Phi Function of Prime Power: Corollary:

$\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$.

It is to be shown that for any odd integer $a$ there exists a positive integer $r < 2^{k-1}$ such that $a \equiv 1 \pmod {2^k}$.

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


For all $k \in \N_{>0}$, let $P \left({k}\right)$ be the proposition:

$a^{\left({2^{k - 2} }\right)} \equiv 1 \pmod {2^k}$


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 1^2\) \(=\) \(\displaystyle 1\) \(\displaystyle \equiv 1 \pmod 8\) $\quad$ as $1 = 0 \times 8 + 1$ $\quad$
\(\displaystyle 3^2\) \(=\) \(\displaystyle 9\) \(\displaystyle \equiv 1 \pmod 8\) $\quad$ as $9 = 1 \times 8 + 1$ $\quad$
\(\displaystyle 5^2\) \(=\) \(\displaystyle 25\) \(\displaystyle \equiv 1 \pmod 8\) $\quad$ as $25 = 3 \times 8 + 1$ $\quad$
\(\displaystyle 7^2\) \(=\) \(\displaystyle 49\) \(\displaystyle \equiv 1 \pmod 8\) $\quad$ as $49 = 6 \times 8 + 1$ $\quad$

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 \pmod {2^h}$


Then we need to show:

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


Induction Step

We can write our induction hypothesis more conveniently as:

$\exists m \in \Z: a^{\left({2^{h - 2} }\right)} = 1 + m 2^h$

Hence:

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

But:

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


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 \pmod {2^k}$


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 is Even for Argument greater than 2, $\phi \left({r}\right)$ and $\phi \left({s}\right)$ are both even.

So $\dfrac {\phi \left({r}\right)} 2$ and $\dfrac {\phi \left({s}\right)} 2$ are both integers.

Hence $\dfrac {\phi \left({r s}\right)} 2$ is an integer.

As $a \perp r s$ we have that $a \perp r$

So from Euler's Theorem:

$a^{\phi \left({r}\right)} \equiv 1 \pmod r$

So putting $k = \dfrac {\phi \left({r s}\right)} 2$:

\(\displaystyle a^k\) \(=\) \(\displaystyle a^{\frac {\phi \left({r}\right) \phi \left({s}\right)} 2}\) $\quad$ $\quad$
\(\displaystyle \) \(=\) \(\displaystyle \left({a^{\phi \left({r}\right)} }\right)^{\frac {\phi \left({s}\right)} 2}\) $\quad$ $\quad$
\(\displaystyle \) \(\equiv\) \(\displaystyle \left({1}\right)^{\frac {\phi \left({s}\right)} 2}\) \(\displaystyle \pmod r\) $\quad$ $\quad$
\(\displaystyle \) \(\equiv\) \(\displaystyle 1\) \(\displaystyle \pmod r\) $\quad$ $\quad$

Interchanging the roles of $r$ and $s$ shows also that:

$a^k \equiv 1 \pmod s$

So we see that:

$a^k \equiv 1 \pmod {r s}$

Thus for any $a$, we have:

$a^k \equiv 1 \pmod n$

where:

$k = \dfrac {\phi \left({n}\right)} 2 < \phi \left({n}\right)$

Hence $n$ has no primitive root.

$\Box$


Hence we see that in order for $n$ to have a primitive root, it is necessary that one of the following hold:

$n = 2$
$n = 4$
$n = p^k$
$n = 2 p^k$

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


Proof of Sufficiency

It remains to cover the cases where $n = 2$ and $n = 4$.

This it is to be shown that if either of the following hold:

$n = p^k$
$n = 2 p^k$

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



Historical Note

This was first proved by Carl Friedrich Gauss in $1801$.