TheoremStatement: AI-adaptedProof: AI-adaptedprecheck passaudited 2026-08-16

How statement and proof provenance work

The first chip identifies the source of the statement or construction; the second identifies the source of its local proof or verification.

Literature-sourced: the exact statement appears in a cited source; only wording and notation differ.
AI-adapted: a semantically identical restatement of literature-sourced material, modulo indexing, notation, and boundary cases adopted by the library.
AI-generated: a genuinely novel statement formulated by AI, with no source for the claim itself.

These labels describe origin, not correctness: citations and verification chips remain separate evidence.

A positive integer admits a primitive root exactly when it is $1$ , $2$ , $4$ , $p^{k}$ , or $2 p^{k}$ for an odd prime $p$

Statement

A positive integer $n$ admits a primitive root if and only if

$n \in {1, 2, 4, p^{k}, 2 p^{k}},$

where $p$ is an odd prime and $k \geq 1$ .

Facts & Assumptions

Given: A positive integer $n$ .

[L1]

A primitive root exists exactly when the unit group is cyclic (A unit is a primitive root modulo $n$ if and only if it generates $(Z / n Z)^{\times}$ ).

[L2]

The unit group has the prime-power product decomposition of The unit group modulo $n$ is the product of its odd-prime cyclic factors and its explicit $2$ -power factor.

[L3]

A product of finite cyclic groups is cyclic exactly when the factor orders are pairwise coprime, by repeated use of A direct product of two finite cyclic groups is cyclic if and only if their orders are coprime.

[L4]

Primitive-root existence is equivalent for odd $n$ and $2 n$ (For odd $n$ , primitive-root existence is equivalent for $n$ and $2 n$ ).

Proof

technique · direct

1.1L2L4

The unit groups for $1$ and $2$ are trivial, that for $4$ is $C_{2}$ , and [L2] makes the unit group for every odd prime power cyclic. By [L4], every twice-odd-prime-power also has a cyclic unit group.

1.2L2L3

Conversely, write $n = 2^{a} \prod p_{i}^{k_{i}}$ . If $a \geq 3$ , [L2] contains cyclic factors of orders $2$ and $2^{a - 2}$ , which are not coprime, so [L3] makes the unit group noncyclic. If $a = 2$ and an odd factor is present, the factor $C_{2}$ and the even-order odd-prime factor are likewise not coprime.

1.3L2L3

If two distinct odd-prime factors are present, both cyclic factor orders are even, so [L3] again makes the product noncyclic. Thus cyclicity leaves only $1, 2, 4, p^{k}$ , and $2 p^{k}$ .

2.1step 1.1L1

By [L1], all moduli in the displayed list admit primitive roots.

3.1step 2.1step 1.2step 1.3L1∎

Combining steps 2.1 and 1.3 with [L1] proves both directions, including the convention at $n = 1$ .

Depends on

Used by

The positive moduli below 20 admitting primitive roots are 1,2,3,4,5,6,7,9,10,11,13,14,17,18,19 Example

Dependency tree · two levels

19 results within two dependency steps of this one, each drawn at its shortest distance from it. An arrow runs from a result to what uses it, so the chart reads left to right and ends at this result, which carries a heavier outline. Every node is a link to that result. Click elsewhere on the chart to enlarge it.

Sources

Peter Hackman, Elementary Number Theory, Theorem C.IV.10 (standard reference, not scraped)

A positive integer admits a primitive root exactly when it is 11, 22, 44, pkpk, or 2pk2pk for an odd prime pp