CorollaryStatement: AI-adaptedProof: AI-adaptedprecheck passaudited 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.

If $n$ has a primitive root, $\gcd (a, n) = 1$ , $m \geq 1$ , and $x^{m} \equiv a (m o d n)$ is solvable, then it has exactly $\gcd (φ (n), m)$ solution classes modulo $n$

Statement

Let $n \geq 1$ admit a primitive root, let $\gcd (a, n) = 1$ , and let $m \geq 1$ . If $x^{m} \equiv a (m o d n)$ is solvable, then it has exactly

$\gcd (φ (n), m)$

solution classes modulo $n$ .

Facts & Assumptions

Given: The stated hypotheses and the solvability of $x^{m} \equiv a (m o d n)$ .

[L1]

Relative to a primitive root $g$ , every unit has a unique index modulo $φ (n)$ (The index ${ind}_{g} (a)$ of a unit relative to a primitive root).

[L2]

The index of $x^{m}$ is congruent to $m {ind}_{g} (x)$ modulo $φ (n)$ (Index calculus: products become sums and powers become scalar multiples modulo $φ (n)$ ).

[L3]

For $u, v \in Z$ and $f \geq 1$ , the congruence $u y \equiv v (m o d f)$ is solvable exactly when $\gcd (u, f) ∣ v$ , and when solvable it has exactly $\gcd (u, f)$ solution classes in $Z / f$ (For $n \geq 1$ , $a x \equiv b (m o d n)$ is solvable exactly when $\gcd (a, n) ∣ b$ , and then has exactly $\gcd (a, n)$ solution classes modulo $n$ ).

[L4]

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

Proof

technique · direct

1.1L1choose

Choose a primitive root $g$ , put $f = φ (n)$ , and let $r = {ind}_{g} (a)$ .

1.2L4givenalgebra

By [L4], $a$ is a unit. If $x^{m} = a$ , then $x (x^{m - 1} a^{- 1}) = 1$ , so every solution $x$ is a unit.

2.1step 1.1step 1.2L1L2

By [L1], exponent classes $y$ modulo $f$ parametrise unit classes bijectively as $x = g^{y}$ , and by [L2] the solutions correspond exactly to the classes satisfying $m y \equiv r (m o d f)$ .

3.1step 2.1L3∎

Here $f = φ (n) \geq 1$ , so [L3] applies; the latter congruence is solvable by the Given, so [L3] gives exactly $\gcd (m, f) = \gcd (φ (n), m)$ classes; the bijection in step 2.1 preserves this count, including when $n = 1$ or $m = 1$ .

Depends on

Used by

Dependency tree · two levels

16 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, Theorem C.III.1 (standard reference, not scraped)

If nn has a primitive root, gcd⁡(a,n)=1gcd(a,n)=1, m≥1m≥1, and xm≡a(modn)xm≡a(modn) is solvable, then it has exactly gcd⁡(φ(n),m)gcd(φ(n),m) solution classes modulo nn