Euler's theorem in number theory

Mathematical statement

Enumerate the complete reduced residue system and check multiplication by a permutes it, or compute a^phi(n) modulo n exactly. Normalize a negative base first. Nonunits cannot use this theorem, and one passing congruence has no primality converse; Fermat is the prime-modulus special case.

Representative formula (exact TeX)

E(a,n)=1

Assumptions

• n is an integer at least2 and gcd(a,n)=1.
• phi(n) and modular powers use exact integer arithmetic.

Symbol scope

• phi — Euler totient
• a — unit residue

Intuition, definition, and misconceptions

The unit hypothesis cannot be omitted.

Multiplication by a permutes the reduced residue system.

A single passing congruence does not prove the modulus prime.

Do not apply Euler to gcd(a,n)>1 or infer primality from its modular result.

Adopted derivation guide

The original MKO is retained. The guide has its own append-only revision and verification boundaries, not a new Lean proof.

Prerequisites

• Euler totient function — The exponent and reduced residues are specified.
• Greatest common divisor and coprimality — The unit hypothesis is essential.
• Natural-number congruence modulo a positive modulus — The conclusion is modulo n.
• Natural-number powers and principal square roots — The exponentiation is integral.

Verification boundary

An Euler congruence is not a primality test; every residue equality here has the declared modulo-n scope.

not_formalized

This does not mean the content is false; it means no replayable computational or formal evidence is registered yet.

Next obligation

Add multiplicative order and Euler criterion.

Same-source structured data

This page and the interactive view use the same object and existing language edition; this adds no proof or human review.