Fermat's Little Theorem¶

For prime p, every integer a satisfies a^p ≡ a modulo p; nonzero residues satisfy a^(p−1) ≡ 1.

Version: v1 · 2026-10-03 · History
Domain-specific #: 13225
Domain group: Formal Sciences
Origin domain: Mathematics
Subdomains: Elementary Number Theory, Modular Arithmetic → Mathematics
Aliases: Fermats Little Theorem, Fermat Theorem Mod P

Core Idea¶

Fermat's little theorem says that if p is prime, then every integer a satisfies a^p ≡ a (mod p). Equivalently, when p does not divide a, the nonzero residue satisfies a^(p−1) ≡ 1 (mod p). The second statement follows by cancelling a, which is legal because every nonzero residue modulo a prime has a multiplicative inverse. If p divides a, the first statement still holds as 0 ≡ 0, but the second says 0 ≡ 1 and is false. These hypotheses are the theorem's identity, not small-print exceptions.^[1]^[2]

One structural explanation is that the nonzero residues modulo a prime form a multiplicative group with p−1 elements. Every element's multiplicative order divides that group size, so raising any nonzero residue to p−1 returns one. Poritz presents this as the prime case of Euler's theorem; the MIT lecture also derives the prime statement from a reduced residue system. The theorem is therefore a prime-forced power congruence, not simply a pattern noticed in a few numerical examples.^[1]^[2]

The theorem has useful consequences but a sharply one-way testing implication. If a candidate number n were prime, every coprime base would pass the a^(n−1) ≡ 1 check. Thus a violating base proves n composite. A passing base does not prove n prime: some composites are pseudoprimes for selected bases, and Carmichael numbers such as 561 pass every coprime-base version of this basic check. This is a limit of reversing the theorem, not an exception to the theorem's prime-modulus claim.^[3]

Structural Signature¶

Sig role-phrases: prime modulus → typed base/unit condition → finite multiplicative power structure → forced congruence → conditional corollary or one-way test.

Prime modulus. The hypothesis fixes a prime p. It makes every nonzero residue invertible and gives the unit set p−1 members. Replacing p with an arbitrary composite n does not preserve the universal theorem, even when some bases happen to pass a similar check.^[1]^[2]
Typed base and unit condition. a may be any integer in a^p ≡ a. The p−1 form applies only to a with p∤a, equivalently gcd(a,p)=1. This distinction determines whether cancellation, exponent reduction or inversion is valid.^[1]
Finite multiplicative power structure. The nonzero residue classes form a group of order p−1; the order of each member divides p−1. This relation explains the exponent in the theorem rather than treating it as an arbitrary mnemonic.^[1]
Prime-forced congruence. The conclusion compares residue classes, not ordinary integer equality. a^p and a may differ as integers but their difference is divisible by p.^[2]
Conditional corollary and one-way test. With known prime p and unit a, the theorem permits modular inverses and exponent reduction. With an unproved candidate n, a failed congruence supplies a compositeness witness, while success is inconclusive.^[1]^[3]

What It Is Not¶

Not the claim that a^(p−1) ≡ 1 for every integer. Multiples of p are zero modulo p; only the a^p ≡ a form includes them.^[1]
Not a sufficient primality criterion. The converse “passed, therefore prime” fails for base-dependent pseudoprimes and for Carmichael numbers that pass all coprime bases.^[3]
Not the Fermat primality test itself. That test applies the theorem's necessary condition to an unproved candidate. The theorem is the proved forward implication under a prime hypothesis.
Not Euler's theorem in full. Euler's statement uses the totient φ(n) for units modulo any eligible n; Fermat's p−1 is its prime-modulus specialization.^[1]
Not Fermat's last theorem or a Fermat number. The shared name does not supply the same variables, quantifiers, exponent claim or object.

Scope of Application¶

In elementary number theory, the theorem controls powers of nonzero residues modulo a known prime. It can simplify congruence calculations and help establish impossibility results when a proposed residue violates a necessary power condition. The prime premise must already be justified; using the formula cannot bootstrap itself into a proof of that premise.^[1]^[2]

In prime-field arithmetic, it yields the inverse formula a^(p−2) (mod p) for a not divisible by p: multiplying by a gives a^(p−1) ≡ 1. It also lets positive powers of such a unit be reduced modulo p−1. Neither move is valid for zero as though zero had a multiplicative inverse. The computational method used to obtain an inverse may differ, but the theorem explains this one valid expression.^[1]^[2]

In primality screening, the theorem supplies a necessary condition. For a candidate n and base a coprime to n, a non-one value of a^(n−1) (mod n) proves compositeness. A value of one leaves the question open. MIT's notes explicitly give 561 as a composite that passes every coprime base of this basic test; stronger tests inspect additional structure rather than declaring a Fermat pass conclusive.^[3]

Clarity¶

The crucial logical distinction is between a theorem about primes and a test of an unknown candidate. The theorem states prime p ⇒ congruence. Its contrapositive states failed congruence ⇒ not prime. It does not state congruence ⇒ prime. A test interface that reports “prime” for a pass can obscure that asymmetry; the mathematically warranted output is “not ruled out by this base.”^[3]

The two congruence forms also have different domains. If p=5 and a=5, then 5^5 ≡ 5 ≡ 0 (mod 5), so the all-integer form works. Yet 5^4 ≡ 0, not one. The missing premise in the latter form is p∤a. Explicitly naming the base and the modulus prevents a zero residue, a unit, and an unproved candidate modulus from being conflated.^[1]

Manages Complexity¶

Without the theorem, each modular power might seem to require a separate expansion. Once the prime and unit hypotheses are known, the group-size relation compresses infinitely many powers into residues of exponents modulo p−1. For example, knowledge that a^(p−1) ≡ 1 replaces a long power calculation by a shorter exponent class. The same compression gives an algebraic inverse expression.^[1]

That compression becomes harmful when the hypotheses disappear from memory. A fast check of a^(n−1) for an unknown n cannot import all the conclusions that hold under an established prime modulus. Carmichael numbers make this failure visible even if many bases are tried. Good reasoning preserves a small type annotation—known prime versus candidate, unit versus zero—beside the compact formula.^[3]

Abstract Reasoning¶

For a known prime p, first reduce the base modulo p. If it is zero, apply a^p ≡ a but do not cancel. If it is nonzero, place it in the p−1-element unit group, infer a^(p−1) ≡ 1, and derive only congruences compatible with multiplying or dividing by that unit. This supports inverse computation and exponent simplification without assuming a particular prime-field application.^[1]^[2]

For an unknown n, reverse only by valid contrapositive reasoning. If a coprime base fails the congruence, n cannot have been prime. If it passes, ask what additional evidence would distinguish a prime from a pseudoprime. A passing computation is a property of the particular pair (a,n); the theorem's universal assertion is a property of every a under the prime premise. Confusing those quantifiers is the precise error behind a false primality certificate.^[3]

Knowledge Transfer¶

The theorem transfers literally across prime-modulus calculations: a proof about powers, a modular inverse and a primality-screening rejection all reuse the same congruence under carefully typed premises. The use changes, but the prime–base–exponent relation does not. Euler's theorem gives a related unit-group pattern for broader moduli with exponent φ(n); it is a different theorem, not permission to replace p by n while keeping p−1.^[1]

The portable abstraction outside number theory is not Fermat's little theorem itself. One may analogize its one-way-test lesson to any necessary-condition screen, but modular powers, prime residue fields and coprimality do not travel to an unrelated domain. Live Modular arithmetic supplies its literal prerequisite; a cross-domain “necessary but not sufficient” reasoning pattern would need a separately evidenced identity.

Examples¶

Canonical: a unit modulo seven¶

Take the known prime p=7 and base a=3. The unit group has six nonzero residue classes. The theorem gives 3^6 ≡ 1 (mod 7). Consequently, 3^5 ≡ 5 (mod 7) is an inverse of 3 because 3·5 ≡ 1. This is a theorem instance and a derived inverse, not a test claiming that seven is prime because the computation happened to pass.^[1]^[2]

Mapped back: prime modulus = known 7; typed base and unit condition = 3 is coprime to 7; finite multiplicative power structure = six nonzero unit classes; prime-forced congruence = 3^6 ≡ 1 (mod 7); conditional corollary and one-way test = 3^5 ≡ 5 gives a valid inverse in the known prime field.

Applied: the zero class modulo five¶

Take the known prime p=5 and base a=5. Its residue class is zero, so the all-integer statement gives 5^5 ≡ 5 ≡ 0 (mod 5). The alternative p−1 statement is inapplicable: 5^4 ≡ 0, not one. This small case checks that the two forms are related by a unit condition rather than being interchangeable strings.^[1]

Mapped back: prime modulus = known 5; typed base and unit condition = 5 is divisible by 5, so it is not a unit; finite multiplicative power structure = the unit-group argument does not apply to zero; prime-forced congruence = 5^5 ≡ 5 (mod 5); conditional corollary and one-way test = no inverse or p−1-form inference is made.

Negative boundary: The composite 561 satisfies a^560 ≡ 1 (mod 561) for every base coprime to it. Those passes do not make it an instance with a prime modulus or prove it prime; they demonstrate the failure of the proposed converse test.^[3]

Structural Tensions¶

Universal theorem versus conditional test. A known prime premise yields an exact congruence; an observed congruence for unknown n does not establish that premise. Using a failure as a compositeness witness is rigorous, while reporting a pass as a proof loses the logical direction. Ignoring the test altogether would forgo a useful rejection screen. Diagnostic: is primality a proven premise here or the claim under investigation?^[3]

All-base statement versus cancellable unit statement. a^p ≡ a covers zero and nonzero residues; a^(p−1) ≡ 1 enables stronger deductions but only for units. Forcing the second over every base makes a false claim; never using it leaves inverse and exponent reasoning unavailable. Diagnostic: is cancellation by this base legitimate modulo the prime?^[1]

Compact exponent rule versus structural typing. Remembering p−1 makes calculations short, but detached from the p−1-element unit group it invites application to arbitrary composites. Requiring full proof at every calculation is wasteful; retaining the prime/unit type information preserves the theorem's speed without the misapplication. Diagnostic: which residue group and order relation justify this exponent reduction?^[1]^[3]

Structural–Framed Character¶

Evaluative weight: The theorem asserts a mathematical necessity, not which computation or cryptographic design should be trusted. Choosing a primality-testing threshold or implementation goal adds human evaluation outside the theorem.

Human-practice dependence: The congruence is formal once integers, primality and modular equivalence are fixed; it does not depend on a laboratory instrument or social convention for its truth. Proof and application are human practices, but not constituents of the result.^[1]^[2]

Institutional origin: The name and standard presentation belong to number-theory history and teaching. They do not cause the prime-modulus relation to hold. Institutional conventions do matter when software labels a passing test “prime,” so careful presentation preserves the logical boundary.^[3]

Vocabulary travel: “Prime,” “base,” “power” and “congruence” have precise mathematical meanings here. A metaphorical “prime signal” or “power cycle” elsewhere does not instantiate this theorem.

Import versus recognition: Recognize the theorem when a genuine prime modulus and integer base support one of its precisely quantified congruences. Importing its label onto a successful composite-modulus check confuses a necessary-condition observation with the theorem's hypothesis.

Its character: a highly structural theorem inside arithmetic but domain-specific as an encyclopedia identity. Its quantified relation is independent of a particular application, yet its prime residue system and exponent conditions do not travel intact outside mathematics.

Structural Core vs. Domain Accent¶

Skeletal relation: A finite invertible system can constrain repeated operations by group order, and a proved condition yields a one-way necessary test. Within the live catalog, Modular arithmetic supplies the literal congruence setting. Any broader cross-domain necessary-condition lesson is only an analogy or future-prime question, not an asserted identity of this theorem.^[1]

Domain-bound mechanism: The theorem specifically concerns integer powers modulo prime p, with a unit group of size p−1, and a zero-class exception to cancellation. Change the carrier to arbitrary entities or use ordinary equality instead of congruence and the result is not Fermat's little theorem.^[1]^[2]

Why not prime: The result can be used in many areas of mathematics and computing, but those uses transport the same number-theoretic theorem, not a substrate-independent abstraction with independently established examples across domains. The general group/order reasoning and one-way-test lesson do not make the named theorem itself prime.

This entry presupposes Modular arithmetic.

The proposed workspace DAG uses Modular arithmetic as a presupposed parent, not a genus: congruence classes and modular multiplication must be meaningful before the theorem can be stated. Coprime integers describes the condition needed for the p−1 version but cannot parent the all-integer version. Euler's totient function helps express the broader Euler theorem, whereas Miller–Rabin primality test is a stronger sibling testing method. Carmichael number names a composite class that defeats a converse Fermat test; Fermat number merely shares a surname.

Relationships to Other Abstractions¶

Current abstraction Fermat's Little Theorem Domain-specific

Parents (1) — more general patterns this builds on

Fermat's Little Theorem presupposes Modular arithmetic Domain-specific

A prime-modulus power congruence presupposes modular arithmetic and adds the theorem's prime and base conditions.

Hierarchy path (1) — routes to 1 parentless root

Fermat's Little Theorem → Modular arithmetic → Cycle → Network → Reservoir-Flux Network → Conservation Laws → Invariance

Neighborhood in Abstraction Space¶

Fermat's Little Theorem sits in a moderately populated region (48^th percentile for distinctiveness): it has near-neighbors but no dense thicket of look-alikes.

Family — Number-Theoretic Properties & Tests (20 abstractions)

Nearest neighbors

Computed from structural-signature embeddings · 2026-10-08

Not to Be Confused With¶

Fermat probable-prime test: This asks about unknown n using selected bases. A failure can certify compositeness; a pass remains inconclusive.^[3]

Carmichael number: A composite such as 561 can satisfy the coprime-base Fermat congruence for every base. It refutes the test's converse, not the theorem for primes.^[3]

Euler's theorem: This uses φ(n) for units under more general modulus n. When n=p is prime, φ(p)=p−1, yielding Fermat's unit form.^[1]

Fermat's last theorem and Fermat number: These are separate named mathematical claims and objects. Neither is the quantified prime-modulus power congruence here.

References¶

[1] Jonathan A. Poritz, Yet Another Introductory Number Theory Textbook, §3.3 “Multiplicative Order and Applications”, original authored open textbook rendered by Mathematics LibreTexts; multiplicative-order theorem, Euler theorem, Fermat corollary and alternative all-integer form directly inspected. registry ↩a ↩b ↩c ↩d ↩e ↩f ↩g ↩h ↩i ↩j ↩k ↩l ↩m ↩n ↩o ↩p ↩q ↩r ↩s ↩t ↩u ↩v

[2] Abhinav Kumar, MIT 18.781 Theory of Numbers, Lecture 4, pp. 1–2; reduced-residue argument, Fermat corollary and modular inverses. registry ↩a ↩b ↩c ↩d ↩e ↩f ↩g ↩h ↩i ↩j

[3] Abhinav Kumar, MIT 18.781 Theory of Numbers, Lecture 6, p. 1; primality-screening logic and Carmichael-number limitation. registry ↩a ↩b ↩c ↩d ↩e ↩f ↩g ↩h ↩i ↩j ↩k ↩l ↩m