Fermat's little theorem

Mathematical statement

The theorem modulus is an explicit prime p≥2. The coprime form requires p not dividing a; the all-integer form also handles p dividing a without canceling a. Exact modular powers normalize negative bases. Composite examples such as561 show that passing a Fermat test does not prove primality. All residue equalities here have the declared modulo-p scope.

Representative formula (exact TeX)

a^p\equiv a\pmod{p}

Assumptions

• The theorem-exercise modulus passes exact primality checking.
• Modular powers use integer square-and-multiply, not expanded floating-point powers.

Symbol scope

• p — prime modulus
• a — integer base

Intuition, definition, and misconceptions

The coprime and all-integer forms have different hypotheses.

Do not cancel a noninvertible residue.

Passing one Fermat test does not prove the modulus prime.

Notation candidate: the difference a^p−a is divisible by the prime p. This is congruence modulo p,not integer equality; multiples of p are included without an unnecessary coprimality restriction. Passing composite examples do not establish primality.

a^(n−1) congruent to1 does not prove n prime, and a base divisible by the modulus cannot use the coprime form.

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

• Prime natural number — Primality is a theorem hypothesis.
• Natural-number congruence modulo a positive modulus — The conclusion is a residue-class equality.
• Natural-number powers and principal square roots — The formulas use integer powers.

Verification boundary

Only Fermat congruences are checked, not a deterministic primality test. The shared representative equation needs its modulo-p context and is not an unrestricted integer equality; final formula/symbol alignment remains under review.

not_formalized

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

Next obligation

Add Euler theorem, the Carmichael function and Miller-Rabin.

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.