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.
Index calculus: products become sums and powers become scalar multiples modulo
Statement
Let be a primitive root modulo . For units modulo and ,
in .
Facts & Assumptions
Given: A primitive root modulo , units , and an integer .
The index of a unit is its unique exponent class modulo relative to (The index of a unit relative to a primitive root).
Group powers satisfy and (Exponent laws in a group: and for all , and when and commute).
For an element of order , if and only if (If then iff is an integer multiple of , the powers are distinct, and has exactly elements; if has infinite order then only for ).
Proof
Choose integers representing and , so and .
By [L2], and .
Applying the uniqueness in [L1], equivalently [L3], to step 2.1 gives the two asserted congruences modulo .
Depends on
- The index $\operatorname{ind}_g(a)$ of a unit relative to a primitive root
- Exponent laws in a group: $g^{m+n} = g^{m}g^{n}$ and $(g^{m})^{n} = g^{mn}$ for all $m, n \in \mathbb{Z}$, and $(gh)^{n} = g^{n}h^{n}$ **when $g$ and $h$ commute**
- 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
- 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: 69 results over 22 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)