Conditions for Integer to have Primitive Root

This page has been identified as a candidate for refactoring of basic complexity. In particular: Restructure the page so as to bring it in line with the usual house style structure Until this has been finished, please leave {{Refactor}} in the code. New contributors: Refactoring is a task which is expected to be undertaken by experienced editors only. Because of the underlying complexity of the work needed, it is recommended that you do not embark on a refactoring task until you have become familiar with the structural nature of pages of $\mathsf{Pr} \infty \mathsf{fWiki}$. To discuss this page in more detail, feel free to use the talk page. When this work has been completed, you may remove this instance of {{Refactor}} from the code.

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:

$\map \phi 4 = 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:

$\map \phi {2^k} = 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 $\map P k$ be the proposition:

$a^{2^{k - 2} } \equiv 1 \pmod {2^k}$

Basis for the Induction

$\map 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:

\(\ds 1^2\)

\(=\)

\(\ds 1\)

\(\ds \equiv 1 \pmod 8\)

as $1 = 0 \times 8 + 1$

\(\ds 3^2\)

\(=\)

\(\ds 9\)

\(\ds \equiv 1 \pmod 8\)

as $9 = 1 \times 8 + 1$

\(\ds 5^2\)

\(=\)

\(\ds 25\)

\(\ds \equiv 1 \pmod 8\)

as $25 = 3 \times 8 + 1$

\(\ds 7^2\)

\(=\)

\(\ds 49\)

\(\ds \equiv 1 \pmod 8\)

as $49 = 6 \times 8 + 1$

Thus $\map P 3$ holds.

This is our basis for the induction.

Induction Hypothesis

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

So this is our induction hypothesis:

$a^{2^{h - 2} } \equiv 1 \pmod {2^h}$

Then we need to show:

$a^{2^{h - 1} } \equiv 1 \pmod {2^{h + 1} }$

Induction Step

We can write our induction hypothesis more conveniently as:

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

Hence:

\(\ds \paren {a^{2^{h - 2} } }^2\)

\(=\)

\(\ds \paren {1 + m 2^h}^2\)

squaring both sides

\(\ds \)

\(=\)

\(\ds 1 + 2 \paren {m 2^h} + \paren {m 2^h}^2\)

\(\ds \)

\(=\)

\(\ds 1 + 2^{h + 1} \paren {m + m^2 2^{h - 1} }\)

\(\ds \)

\(\equiv\)

\(\ds 1\)

\(\ds \pmod {2^{h + 1} }\)

But:

\(\ds \paren {a^{2^{h - 2} } }^2\)

\(=\)

\(\ds a^{2^{h - 2} } a^{2^{h - 2} }\)

\(\ds \)

\(=\)

\(\ds a^{2^{h - 2} + 2^{h - 2} }\)

\(\ds \)

\(=\)

\(\ds a^{2 \paren {2^{h - 2} } }\)

\(\ds \)

\(=\)

\(\ds a^{2^{h - 1} }\)

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

Therefore:

$\forall k \ge 3: a^{2^{k - 2} } \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, $\map \phi r$ and $\map \phi s$ are both even.

So $\dfrac {\map \phi r} 2$ and $\dfrac {\map \phi s} 2$ are both integers.

Hence $\dfrac {\map \phi {r s} } 2$ is an integer.

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

So from Euler's Theorem (Number Theory):

$a^{\map \phi r} \equiv 1 \pmod r$

So putting $k = \dfrac {\map \phi {r s} } 2$:

\(\ds a^k\)

\(=\)

\(\ds a^{\frac {\map \phi r \map \phi s} 2}\)

\(\ds \)

\(=\)

\(\ds \paren {a^{\map \phi r} }^{\frac {\map \phi s} 2}\)

\(\ds \)

\(\equiv\)

\(\ds 1^{\frac {\map \phi s} 2}\)

\(\ds \pmod r\)

\(\ds \)

\(\equiv\)

\(\ds 1\)

\(\ds \pmod r\)

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 {\map \phi n} 2 < \map \phi n$

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.

This theorem requires a proof. You can help $\mathsf{Pr} \infty \mathsf{fWiki}$ by crafting such a proof. To discuss this page in more detail, feel free to use the talk page. When this work has been completed, you may remove this instance of {{ProofWanted}} from the code. If you would welcome a second opinion as to whether your work is correct, add a call to {{Proofread}} the page.

Historical Note

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