TheoremStatement: Literature-sourcedProof: AI-adaptedprecheck passverified 2026-08-03 (gpt-5.6-sol-codex-subscription)

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 theorem: if $n \geq 1$ and $\gcd (a, n) = 1$ , then $a^{φ (n)} \equiv 1 (m o d n)$

Statement

Let $n \geq 1$ be an integer and let $a \in Z$ . If $\gcd (a, n) = 1$ , then

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

Facts & Assumptions

Given: A positive integer $n$ and an integer $a$ with $\gcd (a, n) = 1$ .

[F1]

The unit group $(Z / n)^{\times}$ is finite of order $φ (n)$ and has identity $[1]_{n}$ (The unit group $(Z / n)^{\times}$ and Euler's totient $φ (n) = ∣ (Z / n)^{\times} ∣$ for $n \geq 1$ ).

[L1]

The class $[a]_{n}$ is a unit if and only if $\gcd (a, n) = 1$ (For $n \geq 1$ , $[a]_{n}$ is a unit if and only if $\gcd (a, n) = 1$ ).

[L2]

Every element $u$ of a finite group satisfies $u^{∣ G ∣} = e$ ( $g^{∣ G ∣} = e$ for every element $g$ of a finite group $G$ , Powers $g^{n}$ : natural exponents in a monoid and integer exponents in a group, with $g^{0} = e$ ).

[F2]

Multiplication of residue classes satisfies $[x]_{n} [y]_{n} = [x y]_{n}$ , so natural powers satisfy $[a]_{n}^{k} = [a^{k}]_{n}$ ; and $[x]_{n} = [y]_{n}$ exactly when $x \equiv y (m o d n)$ (Addition and multiplication on $Z / n$ by $[a]_{n} + [b]_{n} = [a + b]_{n}$ and $[a]_{n} [b]_{n} = [a b]_{n}$ , The congruence class $[a]_{n}$ and the quotient set $Z / n$ , Congruence modulo an integer: $a \equiv b (m o d n)$ when $n ∣ (a - b)$ , including the moduli $0$ and $1$ , Congruent integers may be added, subtracted and multiplied: representative changes preserve both arithmetic operations).

Proof

technique · direct

1.1

By [L1], $[a]_{n} \in (Z / n)^{\times}$ . Applying [L2] in that group gives $[a]_{n}^{φ (n)} = [1]_{n}$ .

givenF1L1L2

2.1

By [F2], the equality is $[a^{φ (n)}]_{n} = [1]_{n}$ , which is equivalent to $a^{φ (n)} \equiv 1 (m o d n)$ .

step 1.1F2∎

Depends on

Used by

Fermat's little theorem: for prime p, p∤ a implies aᵖ⁻¹≡1 (mod p), and always aᵖ≡ a (mod p) Theorem

Dependency tree · two levels

41 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

Thomas W. Judson, Abstract Algebra: Theory and Applications, Lagrange's Theorem (standard reference, not scraped)
Thomas W. Judson, Abstract Algebra: Theory and Applications, §6.3: Fermat's and Euler's Theorems (standard reference, not scraped)

Euler's theorem: if n≥1n≥1 and gcd⁡(a,n)=1gcd(a,n)=1, then aφ(n)≡1(modn)aφ(n)≡1(modn)