Alphabeta MathHow 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 unit is a primitive root modulo if and only if it generates
Statement
Let and . Then is a primitive root modulo if and only if
Facts & Assumptions
Given: A positive integer and a unit modulo .
A primitive root modulo is a unit whose order is (Primitive roots modulo ).
If has finite order , then has exactly elements (If then iff is an integer multiple of , the powers are distinct, and has exactly elements; if has infinite order then only for ).
The subgroup is the smallest subgroup containing (The subgroup generated by a subset, the cyclic subgroup , and cyclic groups).
The unit group modulo has exactly elements (The unit group and Euler's totient for ).
Proof
The unit group has elements by [L4], while [L2] gives .
If is primitive, [L1] and step 1.1 give ; since [L3] makes a subgroup of the finite unit group, the two sets are equal.
Conversely, if , step 1.1 gives , so is primitive by [L1].
Depends on
- Primitive roots modulo $n$
- If $\operatorname{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 $\langle g \rangle$ has exactly $n$ elements; if $g$ has infinite order then $g^{j} = g^{k}$ only for $j = k$
- The subgroup $\langle S \rangle$ generated by a subset, the cyclic subgroup $\langle g \rangle$, and cyclic groups
- The unit group $(\mathbb{Z}/n)^\times$ and Euler's totient $\varphi(n)=\lvert(\mathbb{Z}/n)^\times\rvert$ for $n\ge1$
Used by
- A modulus with primitive roots has exactly φ(φ(n)) primitive roots Corollary
- An odd prime power pᵏ has exactly φ(φ(pᵏ)) primitive roots Corollary
- Every prime modulus admits a primitive root Corollary
- The index ind_g(a) of a unit relative to a primitive root Definition
- For odd n, primitive-root existence is equivalent for n and 2n Lemma
- 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 · next 3 levels
Direct dependencies and their dependencies through the next three levels: 70 results over 18 levels. An arrow runs from a result to what uses it, and this result sits at the bottom with a heavier outline. Click the chart to enlarge it.
Sources
- Peter Hackman, Elementary Number Theory, §C.I (standard reference, not scraped)