CalculatorsUniverse
Engineering

GCD, LCM, and the Euclidean Algorithm: The Number Theory Behind Simplifying Fractions

The algorithm behind simplifying a fraction is over 2,300 years old — and it's also the exact number theory behind RSA encryption. The real math.

GCD, LCM, and the Euclidean Algorithm: The Number Theory Behind Simplifying Fractions

GCD, LCM, and the Euclidean Algorithm

The method behind simplifying a fraction to lowest terms is over 2,300 years old — and it’s also, without modification, the exact number theory underneath RSA encryption, the algorithm securing most of the web. Here’s the full chain, from “reduce this fraction” to “why your HTTPS connection is actually secure.”

GCD and LCM: The Basics

The greatest common divisor (GCD) of two numbers is the largest number that divides both evenly — it’s what you divide a fraction’s numerator and denominator by to simplify it. The least common multiple (LCM) is the smallest number both divide into evenly, needed to add fractions with different denominators. The two are directly related: LCM(a, b) = (a × b) / GCD(a, b). Find both for 2 to 10 numbers at once, with full working, using the GCF and LCM Calculator.

The Euclidean Algorithm: 2,300 Years Old and Still the Standard

Finding the GCD of two large numbers doesn’t require factoring either one — the Euclidean algorithm finds it through nothing but repeated division: gcd(a, b) = gcd(b, a mod b), repeated until the remainder hits zero. The last nonzero remainder is the GCD.

gcd(252, 105) = gcd(105, 42) = gcd(42, 21) = gcd(21, 0) = 21

Three quick divisions instead of factoring either number — this scales to numbers with hundreds of digits

This is one of the oldest algorithms still in continuous practical use. It appears in Euclid’s Elements (circa 300 BC, Book VII), though Euclid himself likely compiled it from earlier work — historians trace it possibly to Eudoxus of Cnidus (around 375 BC) or the Pythagorean school before him. The reason it’s still the standard today, over two millennia later, is speed: it finds the GCD of even enormous numbers in relatively few steps, without ever needing to factor either one. Run it yourself, step by step, with the GCF and LCM Calculator, or explore a number’s structure directly with the Prime Factorization Calculator and its visual factor tree.

Extended Euclidean Algorithm: Finding More Than Just the GCD

The Extended Euclidean algorithm runs the same division steps but also tracks enough information to solve Bézout’s identity: finding integers x and y such that ax + by = gcd(a, b). That might look like a purely academic extra step, but it’s the exact mechanism used to compute a modular inverse — a number that “undoes” multiplication under a given modulus, which is essential for both classical number theory and modern cryptography. Get the full step-by-step working, Bézout coefficients, and modular inverse with the GCD & Extended Euclidean Algorithm Calculator.

Modular Arithmetic: The Operations Behind Modern Cryptography

Everything above eventually feeds into modular arithmetic — arithmetic that “wraps around” after reaching a fixed value (the modulus). Beyond simple remainders, this includes modular inverses (found via the extended Euclidean algorithm above) and fast modular exponentiation — computing aᵇ mod n efficiently even when b is enormous, which is exactly what encryption and decryption operations require. Work through mod, modular inverse, and modular exponentiation with the Modular Arithmetic Calculator.

Euler’s Totient and RSA: Where This All Connects

Euler’s totient function, φ(n), counts how many integers from 1 to n are coprime to n (share no common factor with it). For RSA encryption specifically, where n is the product of two large primes p and q, this simplifies neatly to φ(n) = (p − 1)(q − 1). RSA’s private key exponent d is then found by solving d · e ≡ 1 (mod φ(n)) — which is precisely a modular inverse calculation, solved using the extended Euclidean algorithm covered above. Calculate φ(n), prime factors, and coprime density with a visual grid using the Euler’s Totient Function Calculator.

Euclidean GCD Extended Euclid Euler's φ(n) RSA Key Pair 2,300-year-old number theory, still generating every RSA key today

Each stage above feeds directly into the next — none of it is coincidental

Chinese Remainder Theorem: Solving Multiple Congruences at Once

The Chinese Remainder Theorem (CRT) solves systems of simultaneous congruences — for example, finding x such that x ≡ a₁ (mod n₁) and x ≡ a₂ (mod n₂) at once — whenever the moduli are pairwise coprime. It has a genuine, widely deployed real-world application: RSA decryption is commonly sped up by using CRT to compute the result modulo p and modulo q separately (both much smaller than n = pq), then combining them — significantly faster than a single exponentiation modulo the full n. Solve a full system of modular congruences step by step with the Chinese Remainder Theorem Calculator.

Frequently Asked Questions

What’s the actual difference between GCD and LCM?
GCD is the largest number that divides both inputs evenly (used to simplify fractions); LCM is the smallest number both inputs divide into evenly (used to find a common denominator) — and they’re related by LCM(a,b) = (a × b) / GCD(a,b).

Why is the Euclidean algorithm still used today if it’s over 2,000 years old?
Because it’s still one of the fastest known ways to find the GCD of two numbers — including numbers hundreds of digits long, as used in cryptography — without ever needing to factor either one.

What is Bézout’s identity actually used for?
Finding the integer coefficients x and y in ax + by = gcd(a, b) is the standard way to compute a modular inverse, a step required in RSA key generation and many other modular arithmetic applications.

How does Euler’s totient function relate to encryption?
In RSA, the totient of the product of two primes, φ(n) = (p−1)(q−1), is used to compute the private key exponent via a modular inverse — making it a direct, load-bearing part of how RSA keys are generated.

What is the Chinese Remainder Theorem actually used for?
Beyond solving systems of modular congruences directly, it’s used in practice to significantly speed up RSA decryption by splitting one large modular exponentiation into two smaller, faster ones.

Start with the GCF and LCM Calculator and Prime Factorization Calculator for the fundamentals, then move to the GCD & Extended Euclidean Algorithm Calculator and Modular Arithmetic Calculator for the cryptography-relevant operations. See where it all connects with the Euler’s Totient Function Calculator and solve systems of congruences with the Chinese Remainder Theorem Calculator.

External Resources