Extended Euclidean Algorithm, Euler's Theorem & Cryptological Applications

Articles · 2026 · Ioannis (John) Konstas

1. The Euclidean Algorithm — GCD Computation

The Greatest Common Divisor (GCD) of two integers a and b is the largest integer that divides both without remainder. Euclid's algorithm (c. 300 BC) computes it in O(log min(a,b)) steps using the key identity:

Worked Example — gcd(252, 105)

# Python
from math import gcd
print(gcd(252, 105))   # → 21

2. The Extended Euclidean Algorithm

The Extended Euclidean Algorithm not only finds gcd(a, b) but also computes the Bézout coefficients s and t such that:

When gcd(a, b) = 1 (coprime), this gives us s·a ≡ 1 (mod b) — meaning s is the modular inverse of a modulo b. This is the foundation of RSA.

Algorithm — Back-Substitution Method

Run the standard Euclidean algorithm forward, then back-substitute the remainders to express the GCD as a linear combination of the originals.

Worked Example — Extended gcd(35, 15)

Step 1 — Forward pass (Euclidean divisions):

Step 2 — Back-substitute:

Worked Example — Modular Inverse: gcd(17, 60)

Find s such that 17·s ≡ 1 (mod 60) — i.e., the modular inverse of 17 mod 60.

Forward pass:

Back-substitution:

Iterative Algorithm (no back-substitution needed)

def extended_gcd(a, b):
    old_r, r   = a, b
    old_s, s   = 1, 0
    old_t, t   = 0, 1
    while r != 0:
        q         = old_r // r
        old_r, r  = r, old_r - q * r
        old_s, s  = s, old_s - q * s
        old_t, t  = t, old_t - q * t
    # old_r = gcd,  old_s = s,  old_t = t
    return old_r, old_s, old_t

gcd, s, t = extended_gcd(17, 60)
print(f"gcd={gcd}  s={s}  t={t}")      # gcd=1  s=-7  t=2
print(f"inverse = {s % 60}")           # 53

3. Euler's Totient Function φ(n)

Euler's totient function φ(n) counts integers from 1 to n that are coprime to n (i.e., gcd(k, n) = 1).

def totient(n):
    count = 0
    for k in range(1, n + 1):
        if gcd(k, n) == 1:
            count += 1
    return count

# Efficient version using prime factorization
def totient_fast(n):
    result = n
    p = 2
    while p * p <= n:
        if n % p == 0:
            while n % p == 0:
                n //= p
            result -= result // p
        p += 1
    if n > 1:
        result -= result // n
    return result

4. Euler's Theorem

If gcd(a, n) = 1, then aφ(n) ≡ 1 (mod n)

This is one of the most powerful results in number theory. It says that raising a to the power of φ(n) always lands on 1 in modular arithmetic — as long as a and n share no common factor.

Special Case — Fermat's Little Theorem

When n = p is prime, φ(p) = p−1, giving Fermat's Little Theorem:

Verified Example — a=3, n=7

Consequence — Modular Exponentiation Shortcut

Because aφ(n) ≡ 1, exponents can be reduced modulo φ(n):

# Fast modular exponentiation (built into Python)
pow(base, exp, mod)   # Python's built-in uses square-and-multiply

# Example: 3^100 mod 7
# φ(7) = 6,  100 mod 6 = 4
# So 3^100 ≡ 3^4 ≡ 81 ≡ 4 (mod 7)
print(pow(3, 100, 7))   # → 4
print(pow(3, 4, 7))     # → 4  ✓

5. Cryptological Applications

5.1 RSA Key Generation

RSA is built entirely on these two theorems. The security relies on the difficulty of factoring large n = p·q.

Minimal RSA Example (small numbers)

from math import gcd

def extended_gcd(a, b):
    old_r, r = a, b
    old_s, s = 1, 0
    while r:
        q = old_r // r
        old_r, r = r, old_r - q * r
        old_s, s = s, old_s - q * s
    return old_r, old_s

# Key generation
p, q   = 61, 53
n      = p * q             # 3233
phi_n  = (p - 1) * (q - 1)  # 3120
e      = 17                # public exponent, gcd(17, 3120) = 1

_, d   = extended_gcd(e, phi_n)
d      = d % phi_n         # private exponent = 2753

print(f"n={n}  φ(n)={phi_n}  e={e}  d={d}")

# Encrypt M=65
M = 65
C = pow(M, e, n)           # 2790
print(f"Ciphertext: {C}")

# Decrypt
M2 = pow(C, d, n)          # 65
print(f"Decrypted:  {M2}")  # → 65 ✓

5.2 Diffie-Hellman Key Exchange

Fermat's Little Theorem ensures that discrete exponentiation in ℤp is a one-way function when p is a large prime and g is a primitive root.

# Diffie-Hellman demonstration
p = 23    # prime (use 2048-bit in production)
g = 5     # primitive root mod 23

a = 6     # Alice's private key
b = 15    # Bob's private key

A = pow(g, a, p)   # Alice's public: 8
B = pow(g, b, p)   # Bob's public:   19

Ka = pow(B, a, p)  # Alice computes shared secret: 2
Kb = pow(A, b, p)  # Bob computes shared secret:   2

print(Ka == Kb)    # True ✓ — same shared secret

5.3 Modular Inverse in Elliptic Curve Cryptography

In ECC, the Extended Euclidean Algorithm computes modular inverses needed for point addition and scalar multiplication over a finite field 𝔽p.

def mod_inverse(a, p):
    """Extended Euclidean — modular inverse of a mod p"""
    _, s, _ = extended_gcd(a % p, p)
    return s % p

# ECC point addition over Fp
def point_add(P, Q, p):
    if P is None: return Q
    if Q is None: return P
    x1, y1 = P
    x2, y2 = Q
    if x1 == x2 and y1 != y2:
        return None   # point at infinity
    if P == Q:
        lam = (3 * x1 * x1) * mod_inverse(2 * y1, p) % p
    else:
        lam = (y2 - y1) * mod_inverse(x2 - x1, p) % p
    x3 = (lam * lam - x1 - x2) % p
    y3 = (lam * (x1 - x3) - y1) % p
    return (x3, y3)

6. Quick Reference — Key Identities

7. The Mathematical Chain

Mathematics doesn't become obsolete. Euler's 1763 theorem is inside every TLS handshake, every SSH session, every encrypted email — running billions of times per second on the global internet.

← All articles

Research and direction by Ioannis (John) Konstas; compiled and finalized with AI assistance.