The Engines of Encryption: Fermat’s Little Theorem & Euler’s Theorem

If you have been following our series on the mathematics of cryptography, we have explored the “atoms” (Prime Numbers) and the “tools” (Euclidean Algorithms). Now, we arrive at the “magic.”

In the world of standard arithmetic, calculating something like 7 to the power of 100 is a monumental task. The result has 85 digits. But in the world of cryptography, we work in Modular Arithmetic (clock math), where numbers wrap around.

It turns out that when you work with prime numbers in this modular world, incredible patterns emerge. These patterns allow us to perform “shortcuts” that seem impossible. These shortcuts—codified in Fermat’s Little Theorem and Euler’s Theorem—are the exact mechanisms that allow RSA encryption to secure the internet.

This article explores these two theorems, how they relate, and how they power modern cryptography.

1. Fermat’s Little Theorem (FLT)

Pierre de Fermat, a 17th-century lawyer and amateur mathematician, discovered a curious property of prime numbers. He found that if you take a number, raise it to a specific prime power, and divide by that prime, the remainder is predictable.

The Theorem Statement

If p is a prime number, and a is any integer not divisible by p, then:

$$ a^{p-1} \equiv 1 \pmod p $$

What this means: If you multiply a by itself p-1 times, and then divide by p, the remainder will always be 1.

Why is this useful? (Exponent Reduction)

In cryptography, we often deal with massive exponents (like x to the power of 65537). Fermat’s Little Theorem allows us to “shrink” these exponents drastically.

Example: Calculate the remainder of 3¹⁰⁰ divided by 7.

Step 1: Identify the variables.
Here, base a = 3 and modulus p = 7 (which is prime).
According to FLT, since 7 is prime:

$$ 3^{7-1} \equiv 1 \pmod 7 $$
$$ 3^6 \equiv 1 \pmod 7 $$

Step 2: Use this to simplify the massive exponent (100).
We know that every group of 6 in the exponent turns into a 1. We just need to find how many groups of 6 fit into 100.

$$ 100 = 16 \times 6 + 4 $$

Step 3: Rewrite the equation.
$$ 3^{100} = 3^{16 \times 6 + 4} $$
$$ 3^{100} = (3^6)^{16} \times 3^4 $$

Since 3⁶ is congruent to 1:

$$ 1^{16} \times 3^4 \equiv 3^4 \pmod 7 $$

Step 4: Solve the smaller problem.
Now we just need to calculate 3⁴ modulo 7.
$$ 3^4 = 81 $$
$$ 81 \div 7 = 11 \text{ remainder } 4 $$

Result:
$$ 3^{100} \equiv 4 \pmod 7 $$

Without Fermat’s theorem, computing 3¹⁰⁰ would have been a computational nightmare. With it, it took four lines of algebra.

2. Euler’s Totient Function

Fermat’s theorem is powerful, but it has a major limitation: it only works when the modulus p is a prime number.

In cryptography (specifically RSA), we use a modulus n which is a product of two primes (n = p × q). This is not a prime number. So, Fermat’s Little Theorem doesn’t apply directly.

Enter Leonhard Euler. He generalized Fermat’s work to apply to any integer. To do this, he invented the Totient Function, denoted as φ(n) (phi).

What is phi(n)?

The Totient function φ(n) counts how many integers between 1 and n are coprime to n. (Two numbers are coprime if their Greatest Common Divisor is 1).

How to Calculate It

Computing this by counting is slow. Luckily, there are formulas.

Case A: If p is Prime
If a number is prime, every number below it is coprime to it.

$$ \phi(p) = p – 1 $$

Case B: If n is the product of two primes (p and q)
This is the golden formula for RSA.

$$ \phi(n) = \phi(p) \times \phi(q) = (p-1)(q-1) $$

Example:
Calculate φ(15).
Since 15 = 3 × 5:

$$ \phi(15) = (3-1)(5-1) = 2 \times 4 = 8 $$

(Verification: The numbers coprime to 15 are 1, 2, 4, 7, 8, 11, 13, 14. There are exactly 8 of them.)

3. Euler’s Theorem

Now that we have the Totient function, Euler updated Fermat’s theorem. This is known as Euler’s Theorem (or the Fermat-Euler Theorem).

The Theorem Statement

For any two coprime integers a and n:

$$ a^{\phi(n)} \equiv 1 \pmod n $$

Notice the similarity? If n is prime, φ(n) = n-1, and we get Fermat’s Little Theorem back. Euler’s theorem is the “universal” version.

Example Calculation

Find the last digit of 7²²².

Finding the last digit is equivalent to finding the number modulo 10. So, we need 7²²² mod 10.

Step 1: Calculate φ(10).
$$ 10 = 2 \times 5 $$
$$ \phi(10) = (2-1)(5-1) = 1 \times 4 = 4 $$

This tells us that exponents repeat every 4 steps.

Step 2: Apply Euler’s Theorem.
We know that a to the power of φ(n) is 1, so:

$$ 7^4 \equiv 1 \pmod{10} $$

Step 3: Reduce the Exponent.
Divide 222 by 4.

$$ 222 = 55 \times 4 + 2 $$

So, we can rewrite the original term:

$$ 7^{222} = (7^4)^{55} \times 7^2 $$

Since 7⁴ is congruent to 1:

$$ 1^{55} \times 7^2 \equiv 49 \pmod{10} $$

Step 4: Finalize.
$$ 49 \equiv 9 \pmod{10} $$

Answer: The last digit is 9.

4. The “Magic” of RSA Encryption

This brings us to the most famous application of Number Theory in history: RSA.

RSA security relies on the fact that if you have a huge number n (which is p × q), it is incredibly hard to find p and q. Because you cannot find p and q, you cannot calculate φ(n).

Without φ(n), you cannot solve the Euler equation to unlock the message.

How Decryption Works

In RSA, encryption works by raising a message m to a public exponent e:

$$ c \equiv m^e \pmod n $$

To decrypt it, we raise the ciphertext c to a private exponent d:

$$ c^d \equiv (m^e)^d \equiv m^{ed} \pmod n $$

Why does this give us back the message m?
Because the private key d is mathematically chosen using the Extended Euclidean Algorithm so that:

$$ e \cdot d \equiv 1 \pmod{\phi(n)} $$

This means e × d = k × φ(n) + 1.
Using Euler’s Theorem, the math cancels out perfectly:

$$ m^{ed} = m^{k\phi(n) + 1} = (m^{\phi(n)})^k \cdot m^1 = (1)^k \cdot m = m $$

It is Euler’s Theorem that guarantees the original message comes back intact!

5. Detailed Practice Problems

To master cryptography, you must be comfortable with these reductions. Try these problems.

Problem Set 1: Fermat’s Little Theorem

Task: Compute 2³⁴ mod 11.

Click to view solution

1. Identify variables: a=2, p=11 (prime).
2. Apply FLT: $$ 2^{10} \equiv 1 \pmod{11} $$
3. Reduce Exponent: 34 = 3 × 10 + 4.
4. Rewrite: $$ 2^{34} = (2^{10})^3 \times 2^4 $$
5. Substitute: $$ 1^3 \times 2^4 = 16 $$
6. Final Modulo: 16 mod 11 = 5.

Answer: 5

Problem Set 2: Euler’s Totient Function

Task: Find φ(60).

Click to view solution

1. Prime Factorization: 60 = 2² × 3 × 5.
2. Apply Formula: Use the property that φ is multiplicative.
$$ \phi(60) = \phi(4) \times \phi(3) \times \phi(5) $$
Note: For prime power p^k, $$ \phi(p^k) = p^k – p^{k-1} $$
$$ \phi(4) = \phi(2^2) = 2^2 – 2^1 = 2 $$
$$ \phi(3) = 2 $$
$$ \phi(5) = 4 $$
3. Calculate: 2 × 2 × 4 = 16.

Answer: 16

Problem Set 3: Euler’s Theorem (Hard)

Task: Compute 13¹²² mod 15.

Click to view solution

1. Calculate φ(15): As found earlier, φ(15) = 8.
2. Apply Theorem: $$ 13^8 \equiv 1 \pmod{15} $$
3. Reduce Exponent: 122 = 15 × 8 + 2.
4. Rewrite: $$ 13^{122} \equiv 13^2 \pmod{15} $$
5. Solve: 13² = 169.
6. Final Modulo: 169 ÷ 15 = 11 remainder 4.

Answer: 4

6. Python Implementation

Calculating the Totient function for large numbers is complex, but here is a simple implementation for learning purposes.

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

def phi(n):
    result = 0
    for i in range(1, n + 1):
        if gcd(n, i) == 1:
            result += 1
    return result

# Proof of Euler's Theorem
n = 10
a = 7
print(f"Phi({n}) = {phi(n)}")  # Should be 4
print(f"{a}^{phi(n)} mod {n} = {pow(a, phi(n), n)}") # Should be 1

Conclusion

Fermat’s Little Theorem and Euler’s Theorem are the engines of number theory. They provide the “shortcuts” that allow legitimate users (who know the secret keys) to compute values instantly, while attackers (who must use brute force) would need millions of years to solve the same problem.

This concludes our core series on Number Theory. You now understand Primes, GCDs, Modular Inverses, and Modular Exponentiation. You technically possess all the mathematical knowledge required to build your own RSA cryptosystem from scratch!