TheoremStatement: Literature-sourcedProof: 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.

Euler's criterion: if $n$ has a primitive root, $\gcd (a, n) = 1$ , and $m \geq 1$ , then $x^{m} \equiv a (m o d n)$ is solvable if and only if $a^{φ (n) / \gcd (φ (n), m)} \equiv 1 (m o d n)$

Statement

Let $n \geq 1$ admit a primitive root, let $\gcd (a, n) = 1$ , and let $m \geq 1$ . Put $d = \gcd (m, φ (n))$ . Then

$x^{m} \equiv a (m o d n)$

is solvable if and only if

$a^{φ (n) / d} \equiv 1 (m o d n) .$

Facts & Assumptions

Given: Integers $n \geq 1$ , $a$ , and $m \geq 1$ satisfying the stated hypotheses, and $d = \gcd (m, φ (n))$ .

[L1]

A primitive root has order $φ (n)$ (Primitive roots modulo $n$ ).

[L2]

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).

[L3]

Index calculus turns a power into scalar multiplication of its index (Index calculus: products become sums and powers become scalar multiples modulo $φ (n)$ ).

[L4]

The congruence $u y \equiv v (m o d f)$ is solvable exactly when $\gcd (u, f) ∣ v$ (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$ ).

[L5]

A greatest common divisor divides both of its arguments (Common divisor, and the greatest common divisor $\gcd (a, b)$ , with the convention $\gcd (0, 0) : = 0$ ).

[L6]

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.1L1L2L6choosealgebra

Choose a primitive root $g$ , put $f = φ (n)$ , and let $k = {ind}_{g} (a)$ . By [L6], $a$ is a unit. If $x^{m} = a$ , then $x (x^{m - 1} a^{- 1}) = 1$ , so every solution $x$ is also a unit.

1.2L1L3L5algebra

Again by [L1] and [L3], $a^{f / d} = 1$ exactly when $f ∣ k f / d$ . Since $d ∣ f$ by [L5], this is equivalent to $d ∣ k$ .

2.1step 1.1L2L3L4

By [L2] and [L3], writing a candidate unit as $x = g^{y}$ turns $x^{m} = a$ in the unit group into $m y \equiv k (m o d f)$ . By [L4], this is solvable exactly when $d ∣ k$ .

3.1step 2.1step 1.2∎

Steps 2.1 and 1.2 give the claimed biconditional. The argument also covers $n = 1$ and $m = 1$ , where $f = d = 1$ .

Depends on

Used by

A coprime exponent gives a unique nonzero k-th root modulo a prime Corollary
Fourth and eighth powers modulo 17 Example
Euler's criterion: (a/p)≡ a^(p-1)/2 (mod p) Theorem

Dependency tree · two levels

24 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)

Euler's criterion: if nn has a primitive root, gcd⁡(a,n)=1gcd(a,n)=1, and m≥1m≥1, then xm≡a(modn)xm≡a(modn) is solvable if and only if aφ(n)/gcd⁡(φ(n),m)≡1(modn)aφ(n)/gcd(φ(n),m)≡1(modn)