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.

✓ 11 results · all verified · 4 also independently AI-judged

Every result on this page is machine-checked by a proof checker and read in full and owner-audited; the judge is an additional, independent cross-model AI review of the proofs. The 7 not AI-judged were verified by owner audit (typically over a confirmed judge false positive), not failures.

Primitive Roots and Unit Groups Modulo N — Examples

1 · Prerequisites

2 · Summary

3 · Logical flowchart

4 · Definitions, theorems and proofs

None yet.

5 · Examples, counterexamples and false statements

ExampleConstruction: AI-adaptedVerification: AI-adaptedprecheck passaudited 2026-08-16Open item page →

The primitive roots modulo $17$ are $3, 5, 6, 7, 10, 11, 12, 14$

Example

The primitive roots modulo $17$ are

$3, 5, 6, 7, 10, 11, 12, 14.$

Facts & Assumptions

Given: The prime modulus $17$ .

[L1]

A unit is a primitive root modulo $n$ when its order is $φ (n)$ (Primitive roots modulo $n$ ).

[L2]

$φ (17) = 16$ ( $φ (1) = 1$ , and $φ (p) = p - 1$ for every prime $p$ ).

[L3]

If $g$ generates a cyclic group of order $m$ , its generators are $g^{a}$ for the exponent classes coprime to $m$ (The generators of a cyclic group of order $m$ are the $g^{a}$ with $\gcd (a, m) = 1$ , so there are $φ (m)$ of them).

Verification

technique · direct

1.1L1L2algebra

The successive powers of $3$ modulo $17$ for exponents $1$ through $16$ are $3, 9, 10, 13, 5, 15, 11, 16, 14, 8, 7, 4, 12, 2, 6, 1$ , with no earlier $1$ . Thus $3$ has order $16 = φ (17)$ and is primitive by [L1].

2.1step 1.1L3algebra∎

The exponent classes coprime to $16$ are $1, 3, 5, 7, 9, 11, 13, 15$ ; selecting these entries from step 1.1 gives $3, 10, 5, 11, 14, 7, 12, 6$ , which is the displayed set after sorting.

ExampleConstruction: AI-adaptedVerification: AI-adaptedprecheck passjudge pass (deepseek-v4-pro + gpt-5.6-terra)audited 2026-08-16Open item page →

An index table modulo $17$ turns multiplication into addition modulo $16$

Example

Relative to the primitive root $3$ modulo $17$ , the powers for exponents $0$ through $15$ are

$1, 3, 9, 10, 13, 5, 15, 11, 16, 14, 8, 7, 4, 12, 2, 6.$

Thus, for example, ${ind}_{3} (5) = 5$ , ${ind}_{3} (7) = 11$ , and ${ind}_{3} (6) = 15$ .

Facts & Assumptions

Given: The displayed power table modulo $17$ .

[L1]

The index is the unique exponent class relative to a primitive root (The index ${ind}_{g} (a)$ of a unit relative to a primitive root).

[L2]

Products add indices and powers multiply indices modulo $φ (n)$ (Index calculus: products become sums and powers become scalar multiples modulo $φ (n)$ ).

[L3]

A unit of order $φ (n)$ is a primitive root modulo $n$ (Primitive roots modulo $n$ ).

[L4]

$φ (17) = 16$ ( $φ (1) = 1$ , and $φ (p) = p - 1$ for every prime $p$ ).

Verification

technique · direct

1.1L3L4algebra

Multiplying each displayed residue by $3$ modulo $17$ gives the next one and returns $6$ to $1$ , so the table is correct and contains every nonzero class exactly once. In particular, $3$ has order $16 = φ (17)$ and is primitive by [L3].

2.1step 1.1L1L2L4algebra∎

Since $5 \cdot 7 \equiv 1 (m o d 17)$ , [L2] gives $5 + 11 \equiv 0 (m o d 16)$ for their indices; and $5^{3} \equiv 6 (m o d 17)$ gives $3 \cdot 5 \equiv 15 (m o d 16)$ . Both agree with the entries read using [L1].

ExampleConstruction: AI-adaptedVerification: AI-adaptedprecheck passaudited 2026-08-16Open item page →

$2$ is a primitive root modulo $13$ by testing the prime divisors of $12$

Example

The class of $2$ is a primitive root modulo $13$ .

Facts & Assumptions

Given: The prime modulus $13$ and the unit class of $2$ .

[L1]

A unit is a primitive root modulo $n$ when its order is $φ (n)$ (Primitive roots modulo $n$ ).

[L2]

$φ (13) = 12$ ( $φ (1) = 1$ , and $φ (p) = p - 1$ for every prime $p$ ).

[L3]

If an element has finite order $r$ , its powers equal the identity exactly at exponents divisible by $r$ (If $ord (g) = n$ then $g^{k} = e$ iff $k$ is an integer multiple of $n$ , the powers $g^{0}, \dots, g^{n - 1}$ are distinct, and $⟨ g ⟩$ has exactly $n$ elements; if $g$ has infinite order then $g^{j} = g^{k}$ only for $j = k$ ).

Verification

technique · direct

1.1algebra

Direct calculation gives $2^{4} \equiv 3 \equiv̸ 1$ and $2^{6} \equiv - 1 \equiv̸ 1 (m o d 13)$ ; in particular $2^{12} \equiv 1 (m o d 13)$ .

2.1step 1.1L1L2L3∎

By step 1.1 and [L3], the order divides $12$ . Every proper divisor of $12$ divides either $12 / 2 = 6$ or $12 / 3 = 4$ , so step 1.1 and [L3] exclude every proper divisor. The order is therefore $12 = φ (13)$ by [L2], and [L1] makes $2$ primitive.

ExampleConstruction: AI-adaptedVerification: AI-adaptedprecheck passaudited 2026-08-16Open item page →

$2$ is primitive modulo every power of $5$

Example

For every $k \geq 1$ , the class of $2$ is a primitive root modulo $5^{k}$ .

Facts & Assumptions

Given: The integer $2$ and powers of the odd prime $5$ .

[L1]

For an odd prime $p$ , an integer $u$ with $p ∤ u$ , and $k \geq 1$ , the class of $1 + p u$ has order $p^{k - 1}$ modulo $p^{k}$ (For odd prime $p$ , $p ∤ u$ , and $k \geq 1$ , the class of $1 + p u$ has order $p^{k - 1}$ modulo $p^{k}$ ).

[L2]

If an element has order $r$ , then its fourth power has order $r / \gcd (r, 4)$ (In a cyclic group of order $m$ , $g^{a}$ has order $m / \gcd (a, m)$ ).

[L3]

An element of order $r$ has its $t$ th power equal to the identity exactly when $r ∣ t$ (If $ord (g) = n$ then $g^{k} = e$ iff $k$ is an integer multiple of $n$ , the powers $g^{0}, \dots, g^{n - 1}$ are distinct, and $⟨ g ⟩$ has exactly $n$ elements; if $g$ has infinite order then $g^{j} = g^{k}$ only for $j = k$ ).

[L4]

$φ (5^{k}) = 4 \cdot 5^{k - 1}$ (For a prime $p$ and $k \geq 1$ , $φ (p^{k}) = p^{k} - p^{k - 1}$ ).

[L5]

A class modulo $n$ is a unit exactly when its representative is coprime to $n$ , and a primitive root is a unit of order $φ (n)$ (For $n \geq 1$ , $[a]_{n}$ is a unit if and only if $\gcd (a, n) = 1$ , Primitive roots modulo $n$ ).

Verification

technique · direct

1.1L3L4L5algebra

Modulo $5$ , $2^{1}, 2^{2}, 2^{3}, 2^{4}$ are $2, 4, 3, 1$ , so $2$ has order $4$ . This settles $k = 1$ .

1.2L1L2

Let $k \geq 2$ and let $r$ be the order of $2$ modulo $5^{k}$ . Since $2^{4} = 1 + 5 \cdot 3$ , [L1] says that $2^{4}$ has order $5^{k - 1}$ . Hence [L2] gives $r / \gcd (r, 4) = 5^{k - 1}$ .

2.1step 1.1step 1.2L3L4L5∎

Reduction modulo $5$ and step 1.1 show that $4 ∣ r$ by [L3]. Therefore $\gcd (r, 4) = 4$ , and step 1.2 yields $r = 4 \cdot 5^{k - 1} = φ (5^{k})$ by [L4]. Since $2$ is a unit by [L5], it is primitive by the definition in [L5].

ExampleConstruction: AI-generatedVerification: AI-generatedprecheck passaudited 2026-08-16Open item page →

The unit group modulo $240$ decomposes as $C_{2}^{2} \times C_{4}^{2}$

Example

The unit group modulo $240$ has the decomposition

$(Z / 240)^{\times} ≅ C_{2}^{2} \times C_{4}^{2} .$

Facts & Assumptions

Given: The factorisation $240 = 16 \cdot 3 \cdot 5$ .

[L1]

The unit-group structure theorem decomposes a modulus into its prime-power unit groups (The unit group modulo $n$ is the product of its odd-prime cyclic factors and its explicit $2$ -power factor).

[L2]

Euler's totient is multiplicative on coprime positive arguments (Euler's totient is multiplicative: $\gcd (m, n) = 1$ implies $φ (m n) = φ (m) φ (n)$ for positive $m, n$ ).

Verification

technique · direct

1.1L1algebra

By [L1], $U (16) ≅ C_{2} \times C_{4}$ , $U (3) ≅ C_{2}$ , and $U (5) ≅ C_{4}$ .

2.1step 1.1L2algebra∎

Their product is $C_{2}^{2} \times C_{4}^{2}$ . Its order is $2^{2} \cdot 4^{2} = 64$ , agreeing with $φ (240) = φ (16) φ (3) φ (5) = 8 \cdot 2 \cdot 4 = 64$ by [L2].

ExampleConstruction: AI-generatedVerification: AI-generatedprecheck passaudited 2026-08-16Open item page →

$λ (561) = 80$ and every integer coprime to $561$ has eightieth power congruent to one

Example

One has $λ (561) = 80$ and $φ (561) = 320$ . Consequently every $a$ coprime to $561$ satisfies $a^{80} \equiv 1 (m o d 561)$ .

Facts & Assumptions

Given: The factorisation $561 = 3 \cdot 11 \cdot 17$ .

[L1]

Carmichael's function is the least common multiple of its prime-power values (Carmichael's function on prime powers and its least-common-multiple formula).

[L2]

If $\gcd (a, n) = 1$ , then $a^{λ (n)} \equiv 1 (m o d n)$ (If $\gcd (a, n) = 1$ , then $a^{λ (n)} \equiv 1 (m o d n)$ ).

[L3]

Euler's totient is multiplicative on coprime arguments (Euler's totient is multiplicative: $\gcd (m, n) = 1$ implies $φ (m n) = φ (m) φ (n)$ for positive $m, n$ ).

Verification

technique · direct

1.1L1L3algebra

By [L1], $λ (561) = lcm (2, 10, 16) = 80$ , while [L3] gives $φ (561) = 2 \cdot 10 \cdot 16 = 320$ .

2.1step 1.1L2∎

Apply [L2] to the value in step 1.1 to obtain $a^{80} \equiv 1 (m o d 561)$ for every $a$ coprime to $561$ .

ExampleConstruction: AI-adaptedVerification: AI-adaptedprecheck passaudited 2026-08-16Open item page →

$λ (1729) = 36$ although $φ (1729) = 1296$

Example

The number $1729$ satisfies

$λ (1729) = 36 and φ (1729) = 1296.$

Facts & Assumptions

Given: The factorisation $1729 = 7 \cdot 13 \cdot 19$ .

[L1]

Carmichael's function is the least common multiple of its prime-power values (Carmichael's function on prime powers and its least-common-multiple formula).

[L2]

Euler's totient is multiplicative on coprime positive arguments (Euler's totient is multiplicative: $\gcd (m, n) = 1$ implies $φ (m n) = φ (m) φ (n)$ for positive $m, n$ ).

Verification

technique · direct

1.1L1algebra

By [L1], $λ (1729) = lcm (6, 12, 18) = 36$ .

2.1step 1.1L2algebra∎

By [L2], $φ (1729) = 6 \cdot 12 \cdot 18 = 1296$ , which is strictly larger than the value in step 1.1.

CounterexampleConstruction: AI-adaptedVerification: AI-adaptedprecheck passaudited 2026-08-16Open item page →

$(Z / 15 Z)^{\times}$ has order $8$ but is not cyclic

Statement refuted

The order of a unit group need not be the order of one of its elements: $(Z / 15)^{\times}$ has order $8$ but is not cyclic.

Facts & Assumptions

Given: The modulus $15 = 3 \cdot 5$ .

[L1]

The unit-group structure theorem gives the product of the prime-power factors (The unit group modulo $n$ is the product of its odd-prime cyclic factors and its explicit $2$ -power factor).

[L2]

An element of finite order $r$ has its $t$ th power equal to the identity exactly when $r ∣ t$ (If $ord (g) = n$ then $g^{k} = e$ iff $k$ is an integer multiple of $n$ , the powers $g^{0}, \dots, g^{n - 1}$ are distinct, and $⟨ g ⟩$ has exactly $n$ elements; if $g$ has infinite order then $g^{j} = g^{k}$ only for $j = k$ ).

Counterexample

technique · direct

1.1L1algebra

By [L1], $(Z / 15)^{\times} ≅ C_{2} \times C_{4}$ , which has $8$ elements.

2.1step 1.1L2algebra∎

For every pair $(x, y) \in C_{2} \times C_{4}$ , [L2] gives $x^{4} = 1$ and $y^{4} = 1$ , so $(x, y)^{4} = (1, 1)$ . Another application of [L2] shows its order divides $4$ . Thus no element has order $8$ and the group is not cyclic.

CounterexampleConstruction: AI-adaptedVerification: AI-adaptedprecheck passjudge pass (deepseek-v4-pro + gpt-5.6-terra)audited 2026-08-16Open item page →

$φ (8) = 4$ but every unit modulo $8$ has square one

Statement refuted

Euler's totient need not equal the exponent of the unit group: $φ (8) = 4$ , but $λ (8) = 2$ .

Facts & Assumptions

Given: The modulus $8$ .

[L1]

$λ (n)$ is the exponent of the unit group (Carmichael's function $λ (n)$ as the exponent of $(Z / n Z)^{\times}$ ).

[L2]

$(Z / 8)^{\times} ≅ C_{2} \times C_{2}$ (For $k \geq 3$ , $(Z / 2^{k} Z)^{\times} ≅ C_{2} \times C_{2^{k - 2}}$ , generated uniquely as $(- 1)^{ε} 5^{j}$ ).

Counterexample

technique · direct

1.1algebra

The four units are $1, 3, 5, 7$ , and each square is congruent to $1$ modulo $8$ .

2.1step 1.1L1L2∎

Thus their group has four elements but exponent $2$ by [L1]; this also agrees with [L2]. Hence $φ (8) = 4 \neq 2 = λ (8)$ .

ExampleConstruction: AI-adaptedVerification: AI-adaptedprecheck passjudge pass (deepseek-v4-pro + gpt-5.6-terra)audited 2026-08-16Open item page →

The four square roots of one modulo $128$ are $1, 63, 65, 127$

Example

The solutions of $x^{2} \equiv 1 (m o d 128)$ are

$x \equiv 1, 63, 65, 127 (m o d 128) .$

Facts & Assumptions

Given: The modulus $128 = 2^{7}$ .

[L1]

Every unit modulo $2^{7}$ has a unique form $(- 1)^{ε} 5^{j}$ with $ε \in {0, 1}$ and $j$ modulo $32$ (For $k \geq 3$ , $(Z / 2^{k} Z)^{\times} ≅ C_{2} \times C_{2^{k - 2}}$ , generated uniquely as $(- 1)^{ε} 5^{j}$ ).

Verification

technique · direct

1.1L1algebra

Any solution of $x^{2} = 1$ is a unit, with inverse $x$ . It therefore has the unique form in [L1]. Squaring that form gives $5^{2 j}$ , which is $1$ exactly when $32 ∣ 2 j$ , equivalently $j \equiv 0$ or $16 (m o d 32)$ .

1.2algebra

Repeated squaring gives $5^{16} \equiv 65 (m o d 128)$ .

2.1step 1.1step 1.2L1∎

Combining the two values of $j$ from step 1.1 with the two signs gives $1, - 1, 65, - 65$ , namely $1, 127, 65, 63$ modulo $128$ ; uniqueness in [L1] shows there are no others.

ExampleConstruction: AI-generatedVerification: AI-generatedprecheck passjudge pass (deepseek-v4-pro + gpt-5.6-terra)audited 2026-08-16Open item page →

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

The positive integers below $20$ that admit primitive roots are

$1, 2, 3, 4, 5, 6, 7, 9, 10, 11, 13, 14, 17, 18, 19.$

Facts & Assumptions

Given: The positive integers $n < 20$ .

[L1]

A modulus admits a primitive root exactly when it is $1$ , $2$ , $4$ , an odd prime power, or twice an odd prime power (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$ ).

Verification

technique · direct

1.1L1algebra

Below $20$ , the odd prime powers are $3, 5, 7, 9, 11, 13, 17, 19$ , and twice such a power gives $6, 10, 14, 18$ ; together with $1, 2, 4$ this is the displayed list.

2.1step 1.1L1algebra∎

The omitted positive integers are $8, 12, 15, 16$ : $8$ and $16$ are powers $2^{a}$ with $a \geq 3$ , $12 = 4 \cdot 3$ , and $15$ has two odd prime factors, so [L1] excludes each.

Primitive Roots and Unit Groups Modulo N — Examples

1 · Prerequisites

2 · Summary

3 · Logical flowchart

4 · Definitions, theorems and proofs

5 · Examples, counterexamples and false statements

The primitive roots modulo 1717 are 3,5,6,7,10,11,12,143,5,6,7,10,11,12,14

Example

Facts & Assumptions

Verification

An index table modulo 1717 turns multiplication into addition modulo 1616

Example

Facts & Assumptions

Verification

22 is a primitive root modulo 1313 by testing the prime divisors of 1212

Example

Facts & Assumptions

Verification

22 is primitive modulo every power of 55

Example

Facts & Assumptions

Verification

The unit group modulo 240240 decomposes as C22×C42C22​×C42​

Example

Facts & Assumptions

Verification

λ(561)=80λ(561)=80 and every integer coprime to 561561 has eightieth power congruent to one

Example

Facts & Assumptions

Verification

λ(1729)=36λ(1729)=36 although φ(1729)=1296φ(1729)=1296

Example

Facts & Assumptions

Verification

(Z/15Z)×(Z/15Z)× has order 88 but is not cyclic

Statement refuted

Facts & Assumptions

Counterexample

φ(8)=4φ(8)=4 but every unit modulo 88 has square one

Statement refuted

Facts & Assumptions

Counterexample

The four square roots of one modulo 128128 are 1,63,65,1271,63,65,127

Example

Facts & Assumptions

Verification

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

Example

Facts & Assumptions

Verification

Sources

The primitive roots modulo $17$ are $3, 5, 6, 7, 10, 11, 12, 14$

An index table modulo $17$ turns multiplication into addition modulo $16$

$2$ is a primitive root modulo $13$ by testing the prime divisors of $12$

$2$ is primitive modulo every power of $5$

The unit group modulo $240$ decomposes as $C_{2}^{2} \times C_{4}^{2}$

$λ (561) = 80$ and every integer coprime to $561$ has eightieth power congruent to one

$λ (1729) = 36$ although $φ (1729) = 1296$

$(Z / 15 Z)^{\times}$ has order $8$ but is not cyclic

$φ (8) = 4$ but every unit modulo $8$ has square one

The four square roots of one modulo $128$ are $1, 63, 65, 127$

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