18.12 Euler's Theorem and Fermat's Little Theorem

Many algorithms require computing enormous powers modulo an integer. At first glance, expressions such as:

7^1000000 mod 13

appear computationally impossible. However, modular arithmetic contains deep structural properties that allow such expressions to be simplified dramatically.

Two of the most important results are Fermat's Little Theorem and Euler's Theorem. These theorems explain how powers behave in modular systems and provide the theoretical foundation for modular inverses, RSA cryptography, primality testing, finite fields, and many advanced number-theoretic algorithms.

This section develops both theorems, explores their proofs and applications, and shows how they lead to efficient computation of large modular powers.

Problem

Given:

a
n

compute:

a^k mod n

for potentially enormous values of:

k

without performing all multiplications explicitly.

For example:

3^1000 mod 7

or:

5^1000000 mod 13

The key is discovering repeating patterns in modular powers.

Fermat's Little Theorem

Let:

p

be a prime number.

If:

p ∤ a

then:

a^(p−1) ≡ 1 (mod p)

This is known as entity["scientific_concept","Fermat's Little Theorem","number theory theorem"].

An equivalent form is:

a^p ≡ a (mod p)

for all integers a.

Example

Take:

a = 2
p = 7

Compute:

2^6 = 64

Since:

64 mod 7 = 1

we obtain:

2^6 ≡ 1 (mod 7)

exactly as predicted.

Another example:

3^10 mod 11

Since:

3^10 = 59049

and:

59049 mod 11 = 1

the theorem holds.

Why Fermat's Theorem Works

Consider the numbers:

1, 2, 3, ..., p−1

Multiplying each by:

a

modulo p produces:

a, 2a, 3a, ..., (p−1)a

Because:

gcd(a,p)=1

multiplication by a simply permutes the nonzero residues modulo p.

Therefore:

1·2·3·...·(p−1)

and:

(a)(2a)(3a)...((p−1)a)

contain exactly the same residues.

Thus:

(p−1)!
≡
a^(p−1)(p−1)!
(mod p)

Since:

(p−1)!

is not divisible by p, it can be canceled.

The result is:

a^(p−1) ≡ 1 (mod p)

Computing Large Powers

Suppose:

3^1000 mod 7

Fermat gives:

3^6 ≡ 1 (mod 7)

Now:

1000 = 6×166 + 4

Therefore:

3^1000
=
(3^6)^166 × 3^4

Modulo 7:

3^1000
≡
1^166 × 3^4

≡ 81

≡ 4 (mod 7)

A huge exponent reduces to a tiny one.

Modular Inverses via Fermat

Recall that:

a × a⁻¹ ≡ 1 (mod p)

Fermat gives:

a^(p−1) ≡ 1 (mod p)

Therefore:

a × a^(p−2)
≡ 1 (mod p)

Hence:

a⁻¹
≡
a^(p−2)
(mod p)

This yields a practical inverse algorithm.

def mod_inverse_prime(a, p):
    return pow(a, p - 2, p)

Example:

print(mod_inverse_prime(3, 11))

Output:

4

because:

3 × 4 ≡ 1 (mod 11)

Limitation of Fermat's Theorem

The theorem requires:

p

to be prime.

Example:

a = 2
n = 8

Then:

2^7 = 128

and:

128 mod 8 = 0

not:

1

The theorem fails because:

8

is not prime.

We need a more general result.

Euler's Theorem

Let:

gcd(a,n)=1

Then:

a^φ(n) ≡ 1 (mod n)

This is Euler's theorem.

Notice the similarity to Fermat:

Prime modulus:
a^(p−1) ≡ 1

General modulus:
a^φ(n) ≡ 1

Fermat's theorem is simply the special case:

φ(p)=p−1

for a prime p.

Example

Take:

n = 10

Since:

φ(10)=4

Euler predicts:

3^4 ≡ 1 (mod 10)

Check:

3^4 = 81

and:

81 mod 10 = 1

Correct.

Another example:

n = 15

Since:

φ(15)=8

Euler predicts:

2^8 ≡ 1 (mod 15)

Check:

256 mod 15 = 1

Correct.

Why Euler's Theorem Works

Consider the reduced residue system modulo n:

r₁, r₂, ..., rφ(n)

Each residue is coprime to n.

Multiplying each residue by:

a

permutes the reduced residue system because:

gcd(a,n)=1

Therefore:

r₁r₂...rφ(n)

and:

(ar₁)(ar₂)...(arφ(n))

represent the same product modulo n.

Expanding:

r₁r₂...rφ(n)
≡
a^φ(n)r₁r₂...rφ(n)
(mod n)

Cancelling the common product gives:

a^φ(n)
≡
1
(mod n)

which proves Euler's theorem.

Exponent Reduction

Euler's theorem implies:

a^k
≡
a^(k mod φ(n))

up to an appropriate adjustment when:

gcd(a,n)=1

This can dramatically reduce large exponents.

Example:

7^1000 mod 15

Since:

φ(15)=8

and:

1000 mod 8 = 0

we obtain:

7^1000
≡
7^0
≡
1
(mod 15)

The exponent shrinks from 1000 to 0.

Carmichael Function

Euler's theorem is not always the strongest possible exponent reduction.

The Carmichael function:

λ(n)

gives the smallest exponent such that:

a^λ(n) ≡ 1 (mod n)

for all coprime a.

Example:

n = 15

Euler gives:

φ(15)=8

But:

λ(15)=4

since every coprime residue already satisfies:

a^4 ≡ 1 (mod 15)

The Carmichael function is important in advanced cryptographic analysis.

RSA and Euler's Theorem

RSA depends directly on Euler's theorem.

Given:

n = pq

where:

p
q

are primes.

Compute:

φ(n)
=
(p−1)(q−1)

Choose:

e
d

such that:

ed ≡ 1 (mod φ(n))

Encryption:

c = m^e mod n

Decryption:

m = c^d mod n

works because Euler's theorem guarantees:

m^(ed)
≡
m
(mod n)

under appropriate conditions.

The entire RSA system rests on this relationship.

Fast Exponent Reduction

When:

gcd(a,n)=1

we can reduce exponents before exponentiation.

def power_mod_euler(a, k, n):
    phi_n = phi(n)

    k %= phi_n

    return pow(a, k, n)

For extremely large exponents this can produce substantial savings.

However, computing:

φ(n)

may itself require factorization, which is not always cheap.

Applications

Modular Inverses

Prime modulus:

a⁻¹ ≡ a^(p−2)

General modulus:

a⁻¹ ≡ a^(φ(n)−1)

when:

gcd(a,n)=1

Primality Testing

Fermat tests rely directly on:

a^(p−1) ≡ 1

Cryptography

RSA and many related systems use Euler's theorem.

Finite Fields

Field arithmetic depends heavily on Fermat's theorem.

Combinatorics

Exponent reduction frequently appears in counting problems.

Number-Theoretic Algorithms

Many algorithms simplify powers through Euler or Fermat identities.

Common Mistakes

Forgetting Coprimality

Euler's theorem requires:

gcd(a,n)=1

Example:

2^φ(8)

does not equal:

1 mod 8

because:

gcd(2,8) ≠ 1

Applying Fermat to Composite Moduli

Fermat's theorem applies only when the modulus is prime.

Confusing φ(n) and n−1

Only for prime moduli do we have:

φ(p)=p−1

For composite numbers these values differ.

Reducing Exponents Incorrectly

Exponent reduction must be justified by Euler's theorem or related results.

It is not generally valid for arbitrary bases and moduli.

Testing

def test_euler():
    assert pow(3, phi(10), 10) == 1
    assert pow(2, phi(15), 15) == 1
    assert pow(7, phi(20), 20) == 1

For Fermat:

def test_fermat():
    assert pow(2, 6, 7) == 1
    assert pow(3, 10, 11) == 1
    assert pow(5, 12, 13) == 1

These tests validate the theoretical identities directly.

Takeaway

Fermat's Little Theorem states that for a prime modulus p, every nonzero residue satisfies a^(p−1) ≡ 1 (mod p). Euler's theorem generalizes this result to arbitrary moduli using Euler's phi function: a^φ(n) ≡ 1 (mod n) whenever a and n are coprime. These theorems enable exponent reduction, modular inverse computation, primality testing, finite-field arithmetic, and public-key cryptography. Together they form one of the central pillars of computational number theory.