Mathlib theorem · Existing formal mathematics
ProofAtlas

Existing in Mathlib · Number Theory

Euler's Totient Theorem

Whenever x and n are coprime natural numbers, x raised to Euler's totient φ(n) is congruent to 1 modulo n.

Exact theorem

Exact Mathlib statement

theorem Nat.ModEq.pow_totient {x n : ℕ} (h : Nat.Coprime x n) : x ^ φ n ≡ 1 [MOD n]

The theorem at a glance

Euler's totient theorem at a glance

A visual guide to the theorem's hypotheses, structure, and conclusion; the exact statement gives the formal detail.

For positive n, coprimality places x in a unit group of cardinality φ(n), while the checked source closes n = 0 separately before returning to natural-number congruence. Explanatory diagram.
Detailed visual description

The poster leads with Nat.Coprime x n and the exact conclusion x ^ φ n ≡ 1 [MOD n]. A composite-modulus example n = 10 highlights the four invertible residues and the multiplication-by-3 cycle 1 → 3 → 9 → 7 → 1. Four source-faithful route lines pass from coprimality to a ZMod unit, scope the unit-group-cardinality identity to n > 0, apply the finite-group cardinality power law there, and coerce the result back to natural-number congruence; the footer notes the separate n = 0 branch. It explicitly rejects a prime-modulus hypothesis, natural-number equality, and any least-exponent claim.

Statement structure

Statement and scope

Statement map for Euler's Totient TheoremIf x and n are coprime natural numbers, then x raised to Euler's totient φ(n) is congruent to 1 modulo n. Claim boundary: This page indexes Mathlib's natural-number congruence form of the Fermat–Euler totient theorem: if Nat.Coprime x n, then x ^ φ n ≡ 1 [MOD n]. The selected declaration has no prime-modulus or positivity hypothesis, concludes congruence rather than equality in ℕ, and does not say that φ n is the multiplicative order of x or the least exponent that returns x to 1. The pinned upstream declaration is Nat.ModEq.pow_totient. The complete formal statement is available in the Exact Mathlib statement section.Mathematical readingIf x and n are coprimenatural numbers, then xraised to Euler'stotient φ(n) iscongruent to 1 modulo n.Claim boundaryThis page indexesMathlib's natural-numbercongruence form of theFermat–Euler totienttheorem: if Nat.Coprimex n, then x ^ φ n ≡ 1[MOD n]. The selecteddeclaration has noprime-modulus orpositivity hypothesis,concludes congruencerather than equality inℕ, and does not say thatφ n is themultiplicative order ofx or the least exponentthat returns x to 1.Pinned declarationmathlib ·Nat.ModEq.pow_totientStatement map for Euler's Totient TheoremIf x and n are coprime natural numbers, then x raised to Euler's totient φ(n) is congruent to 1 modulo n. Claim boundary: This page indexes Mathlib's natural-number congruence form of the Fermat–Euler totient theorem: if Nat.Coprime x n, then x ^ φ n ≡ 1 [MOD n]. The selected declaration has no prime-modulus or positivity hypothesis, concludes congruence rather than equality in ℕ, and does not say that φ n is the multiplicative order of x or the least exponent that returns x to 1. The pinned upstream declaration is Nat.ModEq.pow_totient. The complete formal statement is available in the Exact Mathlib statement section.Mathematical readingIf x and n are coprimenatural numbers, then xraised to Euler'stotient φ(n) iscongruent to 1 modulo n.Claim boundaryThis page indexesMathlib's natural-numbercongruence form of theFermat–Euler totienttheorem: if Nat.Coprimex n, then x ^ φ n ≡ 1[MOD n]. The selecteddeclaration has noprime-modulus orpositivity hypothesis,concludes congruencerather than equality inℕ, and does not say thatφ n is themultiplicative order ofx or the least exponentthat returns x to 1.Pinned declarationmathlib ·Nat.ModEq.pow_totient

Read the exact Mathlib declaration

This map summarizes the statement's structure; the exact Mathlib declaration remains authoritative.

A ten-position composite-modulus example highlights four unit positions and carries those four positions through a closed multiplication orbit. Explanatory scientific diagram.
Detailed visual description

Exactly ten large medallions form one decagon perimeter at left. Four positions have emerald centers with double outlines, while six have ivory centers with single charcoal outlines. There is no center medallion, spoke, radius, or chord. At right, exactly four emerald double-ring medallions form a separate clockwise cycle with exactly four curved arrows. The pixels present one positive composite-modulus example only; they do not state positivity as a theorem hypothesis, identify a prime modulus, or claim a least order.

Why it matters

A mathematical landmark

Euler's totient theorem is a foundational bridge between elementary modular arithmetic and finite group structure. Mathlib's compact proof makes that bridge explicit by converting coprimality into a unit of ZMod n, identifying the unit-group cardinality with φ(n), and transporting the resulting unit equality back to a natural-number congruence.

ProofAtlas record

What has been checked

Upstream indexedPinned source bytes verified locally
Locally reproducedExact upstream declaration replayed
Reviewed pageCurrent public presentation reviewed
Accepted Atlas resultNot recorded for the preferred artifact

Mathlib is the source of the theorem; the local Lean replay and page review are separate.

Claim boundary

No new theorem is claimed

This page indexes Mathlib's natural-number congruence form of the Fermat–Euler totient theorem: if Nat.Coprime x n, then x ^ φ n ≡ 1 [MOD n]. The selected declaration has no prime-modulus or positivity hypothesis, concludes congruence rather than equality in ℕ, and does not say that φ n is the multiplicative order of x or the least exponent that returns x to 1.

Source and local evidence

Where the theorem comes from

Existing declaration
Nat.ModEq.pow_totient in mathlib
Relationship
The checked artifact is the upstream declaration itself
Local Lean evidence
artifact.library.mathlib.euler-totient-theorem.v001
Source
Open the pinned upstream reference