LemmaStatement: AI-adaptedProof: AI-adaptedprecheck passjudge pass (deepseek-v4-pro + gpt-5.6-terra)audited 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.

For odd $n$ , primitive-root existence is equivalent for $n$ and $2 n$

Statement

If $n \geq 1$ is odd, then $n$ admits a primitive root if and only if $2 n$ admits a primitive root.

Facts & Assumptions

Given: An odd positive integer $n$ .

[L1]

CRT restricts to an isomorphism of unit groups for coprime positive moduli (For pairwise coprime positive moduli, the Chinese remainder bijection restricts to an isomorphism of unit groups).

[L2]

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

[L3]

For a prime $p$ , $φ (p) = p - 1$ ; in particular $φ (2) = 1$ ( $φ (1) = 1$ , and $φ (p) = p - 1$ for every prime $p$ ).

[L4]

The totient is the cardinality of the unit group: $φ (n) = ∣ (Z / n)^{\times} ∣$ (The unit group $(Z / n)^{\times}$ and Euler's totient $φ (n) = ∣ (Z / n)^{\times} ∣$ for $n \geq 1$ ).

Proof

technique · direct

1.1L1

Since $n$ is odd, [L1] gives $(Z / 2 n)^{\times} ≅ (Z / 2)^{\times} \times (Z / n)^{\times}$ .

1.2L3L4algebra

By [L3], $φ (2) = 1$ , and by [L4] that number is $∣ (Z / 2)^{\times} ∣$ , so the first factor is trivial and the right-hand side is isomorphic to $(Z / n)^{\times}$ .

2.1step 1.1step 1.2L2∎

Therefore the two unit groups are cyclic simultaneously, and [L2] converts this into the asserted equivalence of primitive-root existence.

Depends on

Used by

A positive integer admits a primitive root exactly when it is 1, 2, 4, pᵏ, or 2pᵏ for an odd prime p Theorem

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, Lemma C.I.6 (standard reference, not scraped)

For odd nn, primitive-root existence is equivalent for nn and 2n2n