TheoremStatement: Literature-sourcedProof: AI-adaptedSession-authored (Fable 5 assisted)precheck 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\ge1$ and $\gcd(a,n)=1$ , then $a^{\varphi(n)}\equiv1\pmod n$

Statement

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

$a^{\varphi(n)}\equiv1\pmod n.$

Facts & Assumptions

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

[F1]

The unit group $(\mathbb Z/n)^\times$ is finite of order $\varphi(n)$ and has identity $[1]_n$ (The unit group $(\mathbb{Z}/n)^\times$ and Euler's totient $\varphi(n)=\lvert(\mathbb{Z}/n)^\times\rvert$ for $n\ge1$ ).

[L1]

The class $[a]_n$ is a unit if and only if $\gcd(a,n)=1$ (For $n\ge1$ , $[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=[xy]_n$ , so natural powers satisfy $[a]_n^k=[a^k]_n$ ; and $[x]_n=[y]_n$ exactly when $x\equiv y\pmod n$ (Addition and multiplication on $\mathbb{Z}/n$ by $[a]_n+[b]_n=[a+b]_n$ and $[a]_n[b]_n=[ab]_n$ , The congruence class $[a]_n$ and the quotient set $\mathbb{Z}/n$ , Congruence modulo an integer: $a\equiv b\pmod n$ when $n\mid(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(\mathbb Z/n)^\times$ . Applying [L2] in that group gives $[a]_n^{\varphi(n)}=[1]_n$ .

givenF1L1L2

2.1

By [F2], the equality is $[a^{\varphi(n)}]_n=[1]_n$ , which is equivalent to $a^{\varphi(n)}\equiv1\pmod n$ .

step 1.1F2∎

Depends on

Used by

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

Dependency tree · next 3 levels

Direct dependencies and their dependencies through the next three levels: 95 results over 27 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

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\ge1n≥1 and gcd⁡(a,n)=1\gcd(a,n)=1gcd(a,n)=1, then aφ(n)≡1(modn)a^{\varphi(n)}\equiv1\pmod naφ(n)≡1(modn)