Fermat's little theorem and the hidden symmetry of remainders

From the group structure of (Z/pZ)* we derive Fermat's little theorem, explain why the set {a, 2a, ..., (p-1)a} is a permutation of {1, 2, ..., p-1}, show that a^{p-2} is the modular inverse, and generalize to Euler's theorem.

Folio Official

March 1, 2026

Fermat's little theorem is one of the most frequently invoked results in number theory. The statement – if $p$ is prime and $g cd (a, p) = 1$ , then $a^{p - 1} \equiv 1 (mod p)$ – is concise, but behind it lies a beautiful symmetry in the world of remainders.

1 The statement

Theorem 1 (Fermat's little theorem).

Let

p

be a prime and let

a

be an integer not divisible by

p

. Then

a^{p - 1} \equiv 1 (mod p) .

Remark 2.

An equivalent formulation: for any integer

a

a^{p} \equiv a (mod p)

. When

g cd (a, p) = 1

, divide both sides by

a

to recover the first form; when

p ∣ a

, both sides are congruent to

0

2 The permutation argument: the heart of the proof

Proof.

Consider the set

S = {1, 2, 3, \dots, p - 1}

. We claim that when

g cd (a, p) = 1

, the set

a S = {a \cdot 1, a \cdot 2, \dots, a \cdot (p - 1)} (mod p)

is a permutation of

S

– the same set of elements, merely rearranged.

Step 1: No element of

a S

0 (mod p)

. Indeed,

p ∣ ai

would require

p ∣ a

p ∣ i

(by Euclid's lemma), but

g cd (a, p) = 1

and

1 \leq i \leq p - 1

, so neither holds.

Step 2: The elements of

a S

are pairwise distinct modulo

p

. If

ai \equiv aj (mod p)

with

i \neq = j

, then

a (i - j) \equiv 0 (mod p)

. Since

g cd (a, p) = 1

, we get

p ∣ (i - j)

, which is impossible for

∣ i - j ∣ < p

Therefore

a S = S

as sets modulo

p

. Multiplying all elements on each side:

i = 1 \prod p - 1 (ai) \equiv i = 1 \prod p - 1 i (mod p) .

The left side is

a^{p - 1} \cdot (p - 1)!

and the right side is

(p - 1)!

. Since

g cd ((p - 1)!, p) = 1

, we may cancel

(p - 1)!

to obtain

a^{p - 1} \equiv 1 (mod p) .

□

Remark 3 (Intuition).

Multiplication by

a

shuffles the elements of

{1, 2, \dots, p - 1}

, but the set as a whole is unchanged. The total product – obtained by multiplying all elements together – is therefore an invariant, and from that invariant the congruence

a^{p - 1} \equiv 1

drops out.

3 The group $(Z / p Z)^{*}$

Fermat's little theorem admits a clean algebraic interpretation.

Definition 4 (

(Z / p Z)^{*}

For a prime

p

, the set

(Z / p Z)^{*} = {1, 2, \dots, p - 1}

equipped with multiplication modulo

p

forms a group– the multiplicative group of integers modulo

p

Remark 5.

Let us verify the group axioms:

Closure: $g cd (a, p) = 1$ and $g cd (b, p) = 1$ imply $g cd (ab, p) = 1$ .
Associativity: inherited from integer multiplication.
Identity: $1$ .
Inverses: computed via the extended Euclidean algorithm (previous article).

Theorem 6 (Consequence of Lagrange's theorem).

The group

(Z / p Z)^{*}

has order

p - 1

. By Lagrange's theorem, the order of every element divides

p - 1

, so

a^{p - 1} = e = 1

Remark 7.

Fermat's little theorem is a special case of the general fact that in a finite group, the order of every element divides the order of the group. The elementary proof via the permutation argument is, at its core, the same reasoning that underlies the proof of Lagrange's theorem.

4 Why $a^{p - 2}$ is the modular inverse

Theorem 8.

Let

p

be prime and

g cd (a, p) = 1

. Then the modular inverse of

a

modulo

p

a^{p - 2}

Proof.

Fermat's little theorem gives

a^{p - 1} \equiv 1 (mod p)

. Rewriting this as

a \cdot a^{p - 2} \equiv 1 (mod p)

, we see that

a^{p - 2}

is the inverse of

a

. □

Example 9.

With

p = 7

and

a = 3

3^{- 1} \equiv 3^{5} = 243 \equiv 243 - 34 \times 7 = 243 - 238 = 5 (mod 7)

. Check:

3 \times 5 = 15 \equiv 1 (mod 7)

5 Modular inverses in competitive programming

Remark 10 (Two methods compared).

There are two standard ways to compute the modular inverse modulo

p

Fermat's little theorem: compute $a^{p - 2} mod p$ by repeated squaring in $O (lo g p)$ .
Extended Euclidean algorithm: also $O (lo g p)$ , with a smaller constant.

When

p

is prime, either method works. When the modulus

n

is not prime, only the extended Euclidean algorithm applies (provided

g cd (a, n) = 1

Example 11 (Binomial coefficients modulo

p

A classic problem asks for

(k n) mod p

. Since

(k n) = \frac{n !}{k ! ( n - k )!}

, we need the modular inverses of

k!

and

(n - k)!

. With

n! mod p

precomputed, both inverses can be obtained via Fermat's little theorem in

O (lo g p)

6 Generalization: Euler's theorem

Definition 12 (Euler's totient function).

φ (n)

is the number of integers in

{1, 2, \dots, n}

that are coprime to

n

Theorem 13 (Euler's theorem).

g cd (a, n) = 1

, then

a^{φ (n)} \equiv 1 (mod n)

Remark 14.

When

n = p

is prime,

φ (p) = p - 1

and Euler's theorem reduces to Fermat's little theorem. Euler's theorem is the natural generalization: the group

(Z / n Z)^{*}

has order

φ (n)

, and the result follows from Lagrange's theorem applied to this group.

7 Takeaway

Fermat's little theorem: if $p$ is prime and $g cd (a, p) = 1$ , then $a^{p - 1} \equiv 1 (mod p)$ .
The proof rests on the observation that multiplication by $a$ permutes the set ${1, \dots, p - 1}$ .
In the language of algebra, this is Lagrange's theorem applied to $(Z / p Z)^{*}$ .
The identity $a \cdot a^{p - 2} \equiv 1$ is a direct consequence, giving the modular inverse.
The generalization is Euler's theorem, which provides the theoretical foundation for RSA encryption.

In the next article, we explore the "merging" of simultaneous congruences – the Chinese Remainder Theorem.

Number Theory Mathematics Between the Lines

Folio Official

Mathematics "between the lines" — exploring the intuition textbooks leave out, written in LaTeX on Folio.

1 followers·107 articles

Fermat's little theorem and the hidden symmetry of remainders

Folio Official

March 1, 2026

1 The statement

Theorem 1 (Fermat's little theorem).

Let

p

be a prime and let

a

be an integer not divisible by

p

. Then

a^{p - 1} \equiv 1 (mod p) .

Remark 2.

An equivalent formulation: for any integer

a

a^{p} \equiv a (mod p)

. When

g cd (a, p) = 1

, divide both sides by

a

to recover the first form; when

p ∣ a

, both sides are congruent to

0

2 The permutation argument: the heart of the proof

Proof.

Consider the set

S = {1, 2, 3, \dots, p - 1}

. We claim that when

g cd (a, p) = 1

, the set

a S = {a \cdot 1, a \cdot 2, \dots, a \cdot (p - 1)} (mod p)

is a permutation of

S

– the same set of elements, merely rearranged.

Step 1: No element of

a S

0 (mod p)

. Indeed,

p ∣ ai

would require

p ∣ a

p ∣ i

(by Euclid's lemma), but

g cd (a, p) = 1

and

1 \leq i \leq p - 1

, so neither holds.

Step 2: The elements of

a S

are pairwise distinct modulo

p

. If

ai \equiv aj (mod p)

with

i \neq = j

, then

a (i - j) \equiv 0 (mod p)

. Since

g cd (a, p) = 1

, we get

p ∣ (i - j)

, which is impossible for

∣ i - j ∣ < p

Therefore

a S = S

as sets modulo

p

. Multiplying all elements on each side:

i = 1 \prod p - 1 (ai) \equiv i = 1 \prod p - 1 i (mod p) .

The left side is

a^{p - 1} \cdot (p - 1)!

and the right side is

(p - 1)!

. Since

g cd ((p - 1)!, p) = 1

, we may cancel

(p - 1)!

to obtain

a^{p - 1} \equiv 1 (mod p) .

□

Remark 3 (Intuition).

Multiplication by

a

shuffles the elements of

{1, 2, \dots, p - 1}

, but the set as a whole is unchanged. The total product – obtained by multiplying all elements together – is therefore an invariant, and from that invariant the congruence

a^{p - 1} \equiv 1

drops out.

3 The group $(Z / p Z)^{*}$

Fermat's little theorem admits a clean algebraic interpretation.

Definition 4 (

(Z / p Z)^{*}

For a prime

p

, the set

(Z / p Z)^{*} = {1, 2, \dots, p - 1}

equipped with multiplication modulo

p

forms a group– the multiplicative group of integers modulo

p

Remark 5.

Let us verify the group axioms:

Closure: $g cd (a, p) = 1$ and $g cd (b, p) = 1$ imply $g cd (ab, p) = 1$ .
Associativity: inherited from integer multiplication.
Identity: $1$ .
Inverses: computed via the extended Euclidean algorithm (previous article).

Theorem 6 (Consequence of Lagrange's theorem).

The group

(Z / p Z)^{*}

has order

p - 1

. By Lagrange's theorem, the order of every element divides

p - 1

, so

a^{p - 1} = e = 1

Remark 7.

4 Why $a^{p - 2}$ is the modular inverse

Theorem 8.

Let

p

be prime and

g cd (a, p) = 1

. Then the modular inverse of

a

modulo

p

a^{p - 2}

Proof.

Fermat's little theorem gives

a^{p - 1} \equiv 1 (mod p)

. Rewriting this as

a \cdot a^{p - 2} \equiv 1 (mod p)

, we see that

a^{p - 2}

is the inverse of

a

. □

Example 9.

With

p = 7

and

a = 3

3^{- 1} \equiv 3^{5} = 243 \equiv 243 - 34 \times 7 = 243 - 238 = 5 (mod 7)

. Check:

3 \times 5 = 15 \equiv 1 (mod 7)

5 Modular inverses in competitive programming

Remark 10 (Two methods compared).

There are two standard ways to compute the modular inverse modulo

p

Fermat's little theorem: compute $a^{p - 2} mod p$ by repeated squaring in $O (lo g p)$ .
Extended Euclidean algorithm: also $O (lo g p)$ , with a smaller constant.

When

p

is prime, either method works. When the modulus

n

is not prime, only the extended Euclidean algorithm applies (provided

g cd (a, n) = 1

Example 11 (Binomial coefficients modulo

p

A classic problem asks for

(k n) mod p

. Since

(k n) = \frac{n !}{k ! ( n - k )!}

, we need the modular inverses of

k!

and

(n - k)!

. With

n! mod p

precomputed, both inverses can be obtained via Fermat's little theorem in

O (lo g p)

6 Generalization: Euler's theorem

Definition 12 (Euler's totient function).

φ (n)

is the number of integers in

{1, 2, \dots, n}

that are coprime to

n

Theorem 13 (Euler's theorem).

g cd (a, n) = 1

, then

a^{φ (n)} \equiv 1 (mod n)

Remark 14.

When

n = p

is prime,

φ (p) = p - 1

and Euler's theorem reduces to Fermat's little theorem. Euler's theorem is the natural generalization: the group

(Z / n Z)^{*}

has order

φ (n)

, and the result follows from Lagrange's theorem applied to this group.

7 Takeaway

Fermat's little theorem: if $p$ is prime and $g cd (a, p) = 1$ , then $a^{p - 1} \equiv 1 (mod p)$ .
The proof rests on the observation that multiplication by $a$ permutes the set ${1, \dots, p - 1}$ .
In the language of algebra, this is Lagrange's theorem applied to $(Z / p Z)^{*}$ .
The identity $a \cdot a^{p - 2} \equiv 1$ is a direct consequence, giving the modular inverse.
The generalization is Euler's theorem, which provides the theoretical foundation for RSA encryption.

In the next article, we explore the "merging" of simultaneous congruences – the Chinese Remainder Theorem.

Number Theory Mathematics Between the Lines

Folio Official

Mathematics "between the lines" — exploring the intuition textbooks leave out, written in LaTeX on Folio.

1 followers·107 articles

Fermat's little theorem and the hidden symmetry of remainders

1 The statement

2 The permutation argument: the heart of the proof

3 The group $(Z / p Z)^{*}$

4 Why $a^{p - 2}$ is the modular inverse

5 Modular inverses in competitive programming

6 Generalization: Euler's theorem

7 Takeaway

Share your expertise with the world

More from Folio Official

Why primes are the atoms of the integers: what the Fundamental Theorem of Arithmetic really says

The Chinese Remainder Theorem: why simultaneous congruences can be merged

What does it mean to "divide evenly"? Why number theory begins with mod

Why the Euclidean algorithm finds the greatest common divisor: from subtraction to division

Fermat's little theorem and the hidden symmetry of remainders

1 The statement

2 The permutation argument: the heart of the proof

3 The group $(Z / p Z)^{*}$

4 Why $a^{p - 2}$ is the modular inverse

5 Modular inverses in competitive programming

6 Generalization: Euler's theorem

7 Takeaway

Share your expertise with the world

More from Folio Official

Why primes are the atoms of the integers: what the Fundamental Theorem of Arithmetic really says

The Chinese Remainder Theorem: why simultaneous congruences can be merged

What does it mean to "divide evenly"? Why number theory begins with mod

Why the Euclidean algorithm finds the greatest common divisor: from subtraction to division

1 The statement

2 The permutation argument: the heart of the proof

3 The group(Z/pZ)∗

4 Whyap−2is the modular inverse

5 Modular inverses in competitive programming

6 Generalization: Euler's theorem

7 Takeaway

Share your expertise with the world

More from Folio Official

Why primes are the atoms of the integers: what the Fundamental Theorem of Arithmetic really says

The Chinese Remainder Theorem: why simultaneous congruences can be merged

What does it mean to "divide evenly"? Why number theory begins with mod

Why the Euclidean algorithm finds the greatest common divisor: from subtraction to division

1 The statement

2 The permutation argument: the heart of the proof

3 The group(Z/pZ)∗

4 Whyap−2is the modular inverse

5 Modular inverses in competitive programming

6 Generalization: Euler's theorem

7 Takeaway

Share your expertise with the world

More from Folio Official

Why primes are the atoms of the integers: what the Fundamental Theorem of Arithmetic really says

The Chinese Remainder Theorem: why simultaneous congruences can be merged

What does it mean to "divide evenly"? Why number theory begins with mod

Why the Euclidean algorithm finds the greatest common divisor: from subtraction to division

3 The group $(Z / p Z)^{*}$

4 Why $a^{p - 2}$ is the modular inverse

3 The group $(Z / p Z)^{*}$

4 Why $a^{p - 2}$ is the modular inverse