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.
The index of a unit relative to a primitive root
Definition
Let and let be a primitive root modulo . For every , the index of relative to is the unique residue class
such that whenever the class is represented by .
Existence follows from A unit is a primitive root modulo if and only if it generates , since every unit is a power of . If , then , and If then iff is an integer multiple of , the powers are distinct, and has exactly elements; if has infinite order then only for with gives ; hence the residue class is well-defined and unique.
Depends on
- A unit is a primitive root modulo $n$ if and only if it generates $(\mathbb Z/n\mathbb Z)^\times$
- 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$
Used by
- If n has a primitive root, gcd(a,n)=1, m≥1, and xᵐ≡ a pmod n is solvable, then it has exactly gcd(φ(n),m) solution classes modulo n Corollary
- An index table modulo 17 turns multiplication into addition modulo 16 Example
- Index calculus: products become sums and powers become scalar multiples modulo φ(n) Proposition
- Euler's criterion: if n has a primitive root, gcd(a,n)=1, and m≥1, then xᵐ≡ a pmod n is solvable if and only if a^φ(n)/gcd(φ(n),m)≡1 pmod n Theorem
Dependency tree · next 3 levels
Direct dependencies and their dependencies through the next three levels: 68 results over 19 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)