04c-euler-totient-fermats-theorem.ipynb

Kernel: SageMath 10.5

Euler's Totient and Fermat's Theorem

Module 04c | Number Theory and RSA

euler_phi(), power_mod(), and the theoretical backbone of RSA

Question: Compute $3^{1{,}000{,}000} \bmod 7$ without a computer. Sounds impossible? Fermat says you only need to know that $3^6 \equiv 1 \pmod{7}$. Then $3^{1{,}000{,}000} = 3^{6 \cdot 166666 + 4} = (3^6)^{166666} \cdot 3^4 \equiv 1^{166666} \cdot 81 \equiv 81 \bmod 7 \equiv 4$. That's the power of this notebook.

Objectives

By the end of this notebook you will be able to:

1. Define Euler's totient function $\varphi(n)$ and compute it for any $n$.

2. Derive the product formula $\varphi(pq) = (p-1)(q-1)$ that makes RSA work.

3. State and verify Fermat's Little Theorem and its generalization, Euler's theorem.

4. Connect $\varphi(n)$ to element orders and Lagrange's theorem from Module 01e.

5. Explain why Euler's theorem guarantees RSA decryption correctness.

Prerequisites

• Completion of 04a: Divisibility and GCD, you know what $\gcd(a, n)$ means.

• Completion of 04b: Extended Euclidean Algorithm, you know that $a$ has a modular inverse iff $\gcd(a, n) = 1$.

• From 01e: Subgroups and Lagrange, element orders must divide the group size.

From Inverses to Counting: What Is $\varphi(n)$?

In 04b, we discovered that $a$ has a multiplicative inverse modulo $n$ precisely when $\gcd(a, n) = 1$. The set of all such invertible elements forms the multiplicative group $(\mathbb{Z}/n\mathbb{Z})^*$.

A natural question: how big is this group? That is, how many integers in $\{1, 2, \ldots, n\}$ are coprime to $n$?

This count has a name: Euler's totient function, written $\varphi(n)$.

Euler's Totient Function: Definition

$$\varphi(n) = \#\{a \in \{1, 2, \ldots, n\} : \gcd(a, n) = 1\}$$

Let's compute it the hard way first, by listing and counting.

# Compute phi(n) by brute force: list all integers 1..n coprime to n
def phi_brute(n):
    """Count integers in {1, ..., n} coprime to n."""
    coprimes = [a for a in range(1, n + 1) if gcd(a, n) == 1]
    return coprimes, len(coprimes)

# Walk through small values of n
for n in range(2, 21):
    coprimes, count = phi_brute(n)
    print(f'  phi({n}) = {count}   coprimes: {coprimes}')

Common mistake: "$\varphi(n)$ counts numbers less than $n$." No! It counts numbers from 1 to $n$ that are coprime to $n$. For example, $\varphi(12) = 4$ (only $\{1, 5, 7, 11\}$ are coprime to 12), not 11.

Look at the table above. Notice anything about the prime values ($n = 2, 3, 5, 7, 11, 13, 17, 19$)?

Formulas for $\varphi(n)$

Rule 1: Primes

If $p$ is prime, then every integer from 1 to $p - 1$ is coprime to $p$ (nothing shares a factor with a prime except its own multiples). So:

$$\varphi(p) = p - 1$$

Rule 2: Prime powers

For $p^k$, the only integers in $\{1, \ldots, p^k\}$ that are not coprime to $p^k$ are the multiples of $p$: there are $p^{k-1}$ of them. So:

$$\varphi(p^k) = p^k - p^{k-1} = p^{k-1}(p - 1)$$

Rule 3: Multiplicativity

When $\gcd(m, n) = 1$:

$$\varphi(mn) = \varphi(m) \cdot \varphi(n)$$

This follows from the Chinese Remainder Theorem (coming up in 04d).

# Verify the formulas against brute force
print('Rule 1: phi(p) = p - 1 for primes\n')
for p in primes(2, 30):
    assert euler_phi(p) == p - 1
    print(f'  phi({p}) = {p - 1}  ✓')

print(f'\nRule 2: phi(p^k) = p^(k-1) * (p-1)\n')
for p in [2, 3, 5, 7]:
    for k in range(1, 5):
        pk = p^k
        formula = p^(k-1) * (p - 1)
        actual = euler_phi(pk)
        assert actual == formula
        print(f'  phi({p}^{k}) = phi({pk}) = {actual}  ✓')

print(f'\nRule 3: phi(mn) = phi(m) * phi(n) when gcd(m,n) = 1\n')
for m, n in [(3, 5), (4, 9), (7, 11), (8, 15), (3, 25)]:
    assert gcd(m, n) == 1
    product = euler_phi(m) * euler_phi(n)
    actual = euler_phi(m * n)
    assert actual == product
    print(f'  phi({m}*{n}) = phi({m*n}) = {actual}  =  phi({m})*phi({n}) = {euler_phi(m)}*{euler_phi(n)}  ✓')

Checkpoint: Before running the next cell, predict $\varphi(15)$.

$15 = 3 \times 5$ and $\gcd(3, 5) = 1$, so $\varphi(15) = \varphi(3) \cdot \varphi(5) = 2 \cdot 4 = \;$? Write your answer down, then verify.

# Verify your prediction
n = 15
coprimes, count = phi_brute(n)
print(f'phi({n}) = {count}')
print(f'Coprime elements: {coprimes}')
print(f'Formula: phi(3)*phi(5) = {euler_phi(3)}*{euler_phi(5)} = {euler_phi(3)*euler_phi(5)}')

The RSA Formula: $\varphi(pq) = (p-1)(q-1)$

This is the single most important application of $\varphi$. If $p$ and $q$ are distinct primes:

$$\varphi(pq) = \varphi(p) \cdot \varphi(q) = (p-1)(q-1)$$

This works because $\gcd(p, q) = 1$ (distinct primes are always coprime), so the multiplicativity rule applies.

Crypto foreshadowing: RSA key generation picks two large primes $p, q$ and computes $n = pq$. The "secret" that makes RSA work is knowledge of $\varphi(n) = (p-1)(q-1)$. Anyone who knows $n$ but doesn't know $p$ and $q$ cannot efficiently compute $\varphi(n)$, and without $\varphi(n)$, they cannot find the decryption key. Factoring $n$ and computing $\varphi(n)$ are computationally equivalent problems.

# The RSA-relevant formula: phi(pq) = (p-1)(q-1)
print('Verifying phi(pq) = (p-1)(q-1) for distinct prime pairs:\n')
prime_pairs = [(3, 5), (5, 7), (7, 11), (11, 13), (17, 19), (101, 103)]

for p, q in prime_pairs:
    n = p * q
    phi_formula = (p - 1) * (q - 1)
    phi_actual = euler_phi(n)
    assert phi_formula == phi_actual
    print(f'  p={p}, q={q}:  n={n}  phi(n)={phi_actual}  = ({p}-1)*({q}-1) = {p-1}*{q-1}  ✓')

# Slightly larger RSA-like example
p, q = 61, 53
n = p * q
phi_n = (p - 1) * (q - 1)
print(f'\nRSA-like example: p={p}, q={q}')
print(f'  n = p*q = {n}')
print(f'  phi(n) = (p-1)*(q-1) = {p-1}*{q-1} = {phi_n}')
print(f'  SageMath verification: euler_phi({n}) = {euler_phi(n)}')

Fermat's Little Theorem

Now we come to the power result. Fermat's Little Theorem (1640) says:

If $p$ is prime and $\gcd(a, p) = 1$, then $a^{p-1} \equiv 1 \pmod{p}$.

Equivalently: $a^p \equiv a \pmod{p}$ for all $a$ (even when $p \mid a$).

Why does this work? The multiplicative group $(\mathbb{Z}/p\mathbb{Z})^*$ has order $p - 1$. By Lagrange's theorem (01e), every element's order divides the group size. So $\text{ord}(a)$ divides $p - 1$, which means $a^{p-1} = a^{\text{ord}(a) \cdot k} = (a^{\text{ord}(a)})^k = 1^k = 1$.

Let's verify this experimentally.

# Fermat's Little Theorem: a^(p-1) ≡ 1 (mod p) for all a not divisible by p
p = 17
print(f"Fermat's Little Theorem for p = {p}:")
print(f"Every a^{p-1} should be 1 mod {p}\n")

for a in range(1, p):
    result = power_mod(a, p - 1, p)
    print(f'  {a}^{p-1} mod {p} = {result}  {"✓" if result == 1 else "✗"}')

# Also verify the a^p ≡ a form (works even for a = 0)
print(f'\nAlternative form: a^{p} ≡ a (mod {p}), for ALL a:')
all_pass = all(power_mod(a, p, p) == a % p for a in range(0, p))
print(f'  Verified for a = 0, 1, ..., {p-1}: {all_pass}')

Using Fermat to Simplify Large Powers

Remember our opening question? $3^{1{,}000{,}000} \bmod 7$.

Since $7$ is prime and $\gcd(3, 7) = 1$, Fermat tells us $3^6 \equiv 1 \pmod{7}$.

So we reduce the exponent modulo 6:

$$1{,}000{,}000 = 6 \cdot 166{,}666 + 4$$$$3^{1{,}000{,}000} = (3^6)^{166{,}666} \cdot 3^4 \equiv 1 \cdot 3^4 = 81 \equiv 81 \bmod 7 = 4$$

# Verify our opening question
p = 7
a = 3
exponent = 1000000

# By hand using Fermat:
reduced_exp = exponent % (p - 1)
print(f'{exponent} mod {p-1} = {reduced_exp}')
print(f'So 3^{exponent} mod {p} = 3^{reduced_exp} mod {p} = {power_mod(a, reduced_exp, p)}')

# Direct computation (SageMath handles big exponents with fast modular exponentiation)
print(f'Direct: power_mod({a}, {exponent}, {p}) = {power_mod(a, exponent, p)}')

# They match!
assert power_mod(a, reduced_exp, p) == power_mod(a, exponent, p)

Euler's Theorem: The Generalization

Fermat's Little Theorem only works modulo a prime. Euler generalized it to any modulus:

If $\gcd(a, n) = 1$, then $a^{\varphi(n)} \equiv 1 \pmod{n}$.

When $n = p$ is prime, $\varphi(p) = p - 1$, and Euler's theorem reduces to Fermat's. But Euler's theorem works for composite $n$ too, and that's what RSA needs.

Why does this work? Same argument as before, now in the group $(\mathbb{Z}/n\mathbb{Z})^*$ of order $\varphi(n)$. By Lagrange's theorem, $\text{ord}(a)$ divides $\varphi(n) = |(\mathbb{Z}/n\mathbb{Z})^*|$, so $a^{\varphi(n)} \equiv 1$.

Checkpoint: Predict $2^{\varphi(15)} \bmod 15$ before running the next cell.

We computed $\varphi(15) = 8$ above, and $\gcd(2, 15) = 1$. So Euler says $2^8 \equiv \;$? $\pmod{15}$.

# Euler's theorem: a^phi(n) ≡ 1 (mod n) when gcd(a, n) = 1
n = 15
phi_n = euler_phi(n)
print(f'n = {n}, phi(n) = {phi_n}')
print(f'Units mod {n}: {[a for a in range(1, n) if gcd(a, n) == 1]}\n')

for a in range(1, n):
    g = gcd(a, n)
    result = power_mod(a, phi_n, n)
    if g == 1:
        print(f'  {a}^{phi_n} mod {n} = {result}  {"✓" if result == 1 else "✗"}')
    else:
        print(f'  {a}^{phi_n} mod {n} = {result}  (gcd={g}, theorem does not apply)')

Common mistake: "$a^{\varphi(n)} \equiv 1 \pmod{n}$ for all $a$." No! The theorem requires $\gcd(a, n) = 1$. Look at $a = 3$ in the table above: $\gcd(3, 15) = 3 \neq 1$, so Euler's theorem does not apply, and indeed $3^8 \not\equiv 1 \pmod{15}$. The coprimality condition is essential.

Mass Verification: Euler's Theorem for Many $n$

One example is convincing. Hundreds are better. Let's verify $a^{\varphi(n)} \equiv 1 \pmod{n}$ for all coprime $a$ and many values of $n$.

# Mass verification of Euler's theorem
failures = 0
tests = 0

for n in range(2, 101):
    phi_n = euler_phi(n)
    for a in range(1, n):
        if gcd(a, n) == 1:
            tests += 1
            if power_mod(a, phi_n, n) != 1:
                failures += 1
                print(f'FAILURE: {a}^{phi_n} mod {n} != 1')

print(f'Tested {tests} pairs (a, n) with n from 2 to 100.')
print(f'Failures: {failures}')
print(f'Euler\'s theorem holds in every case. ✓')

Connection to Element Orders

In 01e, we learned that in a group of order $N$, every element's order divides $N$ (Lagrange's theorem). The group $(\mathbb{Z}/n\mathbb{Z})^*$ has order $\varphi(n)$. So:

$$\text{ord}(a) \mid \varphi(n) \quad \text{for all } a \in (\mathbb{Z}/n\mathbb{Z})^*$$

This is exactly why Euler's theorem works: $a^{\varphi(n)} = a^{\text{ord}(a) \cdot k} = 1^k = 1$.

Some elements have order exactly $\varphi(n)$ (these are the generators of the group, recall 01d). Others have smaller orders, but those smaller orders still divide $\varphi(n)$.

# Element orders in (Z/nZ)* all divide phi(n)
n = 21  # = 3 * 7
phi_n = euler_phi(n)
divs = divisors(phi_n)

print(f'n = {n}, phi(n) = {phi_n}')
print(f'Divisors of phi(n) = {divs}')
print(f'So possible element orders: {divs}\n')

units = [a for a in range(1, n) if gcd(a, n) == 1]
order_counts = {}
for a in units:
    order = Mod(a, n).multiplicative_order()
    divides = phi_n % order == 0
    print(f'  ord({a}) = {order}  divides {phi_n}? {"yes" if divides else "NO!"}')
    order_counts[order] = order_counts.get(order, 0) + 1

print(f'\nOrder distribution: {dict(sorted(order_counts.items()))}')
print(f'All orders divide phi({n}) = {phi_n}: ✓')

Why RSA Decryption Works

Now for the payoff. RSA encryption uses a public key $(n, e)$ and a private key $d$ where:

$$ed \equiv 1 \pmod{\varphi(n)}$$

This means $ed = 1 + k\varphi(n)$ for some integer $k$. Decryption raises the ciphertext $c = m^e \bmod n$ to the power $d$:

$$c^d = (m^e)^d = m^{ed} = m^{1 + k\varphi(n)} = m \cdot (m^{\varphi(n)})^k$$

By Euler's theorem, $m^{\varphi(n)} \equiv 1 \pmod{n}$ (when $\gcd(m, n) = 1$). So:

$$c^d \equiv m \cdot 1^k = m \pmod{n}$$

Euler's theorem is the ENTIRE reason RSA decryption recovers the original message.

Let's see this in action.

# Mini-RSA demonstration: Euler's theorem in action
p, q = 61, 53
n = p * q
phi_n = (p - 1) * (q - 1)

# Choose e coprime to phi(n)
e = 17
assert gcd(e, phi_n) == 1, 'e must be coprime to phi(n)'

# Compute d = e^(-1) mod phi(n)
d = inverse_mod(e, phi_n)

print(f'RSA parameters:')
print(f'  p = {p}, q = {q}')
print(f'  n = p*q = {n}')
print(f'  phi(n) = (p-1)*(q-1) = {phi_n}')
print(f'  e = {e}')
print(f'  d = e^(-1) mod phi(n) = {d}')
print(f'  Check: e*d mod phi(n) = {(e * d) % phi_n}\n')

# Encrypt and decrypt several messages
messages = [42, 100, 1234, 3000, 7]
for m in messages:
    c = power_mod(m, e, n)    # encrypt: c = m^e mod n
    m2 = power_mod(c, d, n)   # decrypt: m = c^d mod n
    print(f'  m={m}  ->  encrypt: {c}  ->  decrypt: {m2}  {"✓" if m == m2 else "✗"}')

print(f'\nDecryption works because m^(ed) = m^(1 + k*phi(n)) = m * (m^phi(n))^k = m * 1^k = m')

Exercises

Exercise 1 (Worked): Computing $\varphi(n)$ from Prime Factorization

Compute $\varphi(360)$ using the prime factorization $360 = 2^3 \cdot 3^2 \cdot 5$.

Strategy: Use multiplicativity and the prime-power formula:

$$\varphi(360) = \varphi(2^3) \cdot \varphi(3^2) \cdot \varphi(5) = 2^2(2-1) \cdot 3^1(3-1) \cdot (5-1)$$

# Exercise 1 (Worked), phi(360) from prime factorization
n = 360

# Step 1: Factor n
print(f'Prime factorization of {n}: {factor(n)}')

# Step 2: Apply the formula phi(p^k) = p^(k-1) * (p-1) to each prime power
# 360 = 2^3 * 3^2 * 5^1
phi_2_3 = 2^2 * (2 - 1)   # phi(8) = 4
phi_3_2 = 3^1 * (3 - 1)   # phi(9) = 6
phi_5_1 = 5 - 1            # phi(5) = 4

print(f'\nStep-by-step:')
print(f'  phi(2^3) = 2^2 * (2-1) = {phi_2_3}')
print(f'  phi(3^2) = 3^1 * (3-1) = {phi_3_2}')
print(f'  phi(5)   = 5 - 1       = {phi_5_1}')

# Step 3: Multiply (since gcd of any two prime powers is 1)
phi_360 = phi_2_3 * phi_3_2 * phi_5_1
print(f'\n  phi(360) = {phi_2_3} * {phi_3_2} * {phi_5_1} = {phi_360}')

# Step 4: Verify
print(f'  SageMath: euler_phi(360) = {euler_phi(360)}')
assert phi_360 == euler_phi(360)
print(f'  Match! ✓')

# Bonus: general formula from factorization
print(f'\nGeneral method using SageMath\'s factor():')
phi_general = prod(p^(k-1) * (p - 1) for p, k in factor(n))
print(f'  phi({n}) = {phi_general}  ✓')

Exercise 2 (Guided): Fermat's Theorem as a Primality Hint

Fermat's Little Theorem says: if $p$ is prime, then $a^{p-1} \equiv 1 \pmod{p}$ for all $1 \leq a < p$.

What about the converse? If $a^{n-1} \equiv 1 \pmod{n}$ for some $a$, does that prove $n$ is prime? (Spoiler: no! These are called Carmichael numbers.)

Your task: test whether $n = 561$ passes the Fermat test for base $a = 2$, and then check if 561 is actually prime.

# Exercise 2 (Guided), Carmichael numbers: Fermat liars
n = 561

# Step 1: Check if n is prime
# TODO: use is_prime(n) to check
# print(f'Is {n} prime? {is_prime(n)}')

# Step 2: Factor n to see its structure
# TODO: use factor(n)
# print(f'Factorization: {factor(n)}')

# Step 3: Test Fermat's condition a^(n-1) ≡ 1 (mod n) for several bases
# TODO: compute power_mod(a, n - 1, n) for a in [2, 3, 5, 7, 11, 13]
# and check which give 1
# bases = [2, 3, 5, 7, 11, 13]
# for a in bases:
#     result = power_mod(a, n - 1, n)
#     print(f'  {a}^{n-1} mod {n} = {result}  {"(looks prime!)" if result == 1 else "(composite!)"}')

# Step 4: 561 is a Carmichael number! It fools the Fermat test for EVERY
# base coprime to it. Count how many bases pass:
# TODO: count how many a in range(2, n) with gcd(a, n) == 1 satisfy
# power_mod(a, n-1, n) == 1

# Takeaway: Fermat's test is a NECESSARY condition for primality, not sufficient.

Exercise 3 (Independent): RSA by Hand

Carry out a complete mini-RSA by hand (with SageMath to check your work):

1. Let $p = 11$, $q = 23$. Compute $n$ and $\varphi(n)$.

2. Choose $e = 3$. Verify $\gcd(e, \varphi(n)) = 1$.

3. Find $d = e^{-1} \bmod \varphi(n)$ using the extended Euclidean algorithm (or inverse_mod).

4. Encrypt the message $m = 42$: compute $c = m^e \bmod n$.

5. Decrypt: compute $c^d \bmod n$ and verify you recover $m = 42$.

6. Explain which theorem guarantees that step 5 recovers $m$.

# Exercise 3 (Independent), Your code here
# p, q = 11, 23
# n = ?
# phi_n = ?
# e = 3
# d = ?
# m = 42
# c = ?   (encrypt)
# m2 = ?  (decrypt)
# assert m2 == m, 'Decryption failed!'

Summary

Concept	Key idea
Euler's totient $\varphi(n)$	Counts integers in $\{1, \ldots, n\}$ coprime to $n$. Key formulas: $\varphi(p) = p - 1$, $\varphi(p^k) = p^{k-1}(p-1)$, and $\varphi(mn) = \varphi(m)\varphi(n)$ when $\gcd(m,n) = 1$
RSA formula	For distinct primes $p, q$: $\varphi(pq) = (p-1)(q-1)$
Fermat's Little Theorem	$a^{p-1} \equiv 1 \pmod{p}$ when $p$ is prime and $p \nmid a$
Euler's theorem	$a^{\varphi(n)} \equiv 1 \pmod{n}$ when $\gcd(a, n) = 1$, the generalization to composite moduli
Group theory connection	$\varphi(n) =
RSA correctness	$m^{ed} = m^{1 + k\varphi(n)} = m \cdot (m^{\varphi(n)})^k = m \cdot 1^k = m$. Euler's theorem is the entire reason RSA works

Next: The Chinese Remainder Theorem, another essential tool for RSA, and the reason $\varphi$ is multiplicative.