Euclid's 2,000-year-old trick for finding the greatest common divisor turns out to be a building block of RSA — the encryption protecting your online passwords. Pure number theory quietly guards every secure login you make.
The oldest algorithm still in daily use
The greatest common divisor gcd(a, b) is the largest integer dividing both. Euclid's algorithm computes it by repeated remainders: gcd(a, b) = gcd(b, a mod b), until the remainder hits 0. It is blazingly fast — the number of steps grows only with the number of digits.
gcd(252, 198): 252 = 1·198 + 54 → 198 = 3·54 + 36 → 54 = 1·36 + 18 → 36 = 2·18 + 0. Answer: 18.
Running the algorithm backwards gives Bézout's identity: gcd(a, b) = ax + by for some integers x, y. When gcd(a, n) = 1 this yields a's multiplicative inverse mod n — the key that unlocks modular division, and with it, modern cryptography.
Pick huge primes p, q; publish n = pq and an exponent e. Encryption is c = mᵉ mod n — anyone can do it. Decryption needs d with ed ≡ 1 mod (p−1)(q−1), which requires knowing p and q. Multiplying primes is easy; factoring n apart is (as far as anyone knows) astronomically hard. That asymmetry is the lock.
- Take p = 3, q = 11, so n = 33 and (p−1)(q−1) = 20. Choose e = 3 (check gcd(3, 20) = 1).
- Find d with 3d ≡ 1 (mod 20) by trying small numbers or Bézout — you should get d = 7.
- Encrypt the message m = 4: compute c = 4³ mod 33.
- Decrypt: compute c⁷ mod 33 (square-and-multiply keeps the numbers small). Did you recover 4?
What you should see: You ran a complete RSA encrypt/decrypt cycle with pencil-sized numbers — the identical math, with 600-digit primes, protects real traffic.