Calculate the GCD using the Euclidean algorithm and prime factorization. See Bézout identity, coprimality check, factor Venn diagram, and step-by-step solutions.
The Greatest Common Divisor (GCD) — also known as the Highest Common Factor (HCF) or Greatest Common Factor (GCF) — is the largest positive integer that divides two numbers without leaving a remainder. It's one of the most fundamental concepts in number theory and has applications ranging from simplifying fractions to cryptography.
This calculator computes the GCD using two classic methods. The Euclidean algorithm repeatedly divides the larger number by the smaller and takes the remainder until it reaches zero — the last non-zero remainder is the GCD. It's fast and elegant, running in O(log(min(a,b))) time. The prime factorization method breaks each number into prime powers and takes the minimum exponent of each shared prime — this gives a deeper structural understanding.
Beyond the GCD itself, the calculator shows the Bézout identity (integers x and y such that ax + by = GCD), the LCM (via the identity GCD × LCM = a × b), whether the numbers are coprime, and a complete Venn-style diagram of all divisors with common ones highlighted. The visual bars let you quickly compare divisor counts.
GCD underpins the RSA cryptosystem, the extended Euclidean algorithm for modular inverses, fraction simplification, and the construction of least common multiples. Whether you're studying elementary number theory or implementing algorithms, this tool makes the internals visible.
The Euclidean algorithm is simple in concept but easy to slip up on when the numbers are large — one wrong remainder and the whole chain is off. This calculator runs both the Euclidean and prime-factorization methods side by side, so you can cross-check results and see exactly where the GCD comes from. It also displays every divisor of each input, colour-coded to highlight the common ones, making the abstract concept concrete. Cryptography and competitive-programming students use it to verify Bézout coefficients and modular inverses.
Euclidean: GCD(a,b) = GCD(b, a mod b), base case GCD(a,0) = a. Factorization: GCD = ∏(p^min(eₐ,eᵦ)). Bézout: ∃ x,y ∈ ℤ such that ax + by = GCD(a,b).
Result: GCD = 12
Euclidean: 48 = 36×1 + 12, then 36 = 12×3 + 0. GCD = 12. Also: 48 = 2⁴×3, 36 = 2²×3². Min exponents: 2²×3¹ = 12.
The Euclidean algorithm computes GCD(a, b) by repeatedly replacing the larger value with the remainder: GCD(48, 36) → GCD(36, 12) → GCD(12, 0) = 12. Each step reduces the problem size by at least half, so the algorithm terminates in O(log(min(a, b))) steps — making it efficient even for very large numbers. This calculator shows every intermediate step so you can trace the algorithm from start to finish.
The extended Euclidean algorithm not only finds GCD(a, b) but also integers x and y satisfying ax + by = GCD(a, b). For 48 and 36: 48(1) + 36(−1) = 12. These Bézout coefficients are essential in cryptography — computing the modular inverse of e mod φ(n) in RSA is exactly this problem. If GCD(a, b) = 1, then x is the modular inverse of a mod b.
Simplifying fractions is the most familiar GCD application: divide numerator and denominator by their GCD to get lowest terms. In programming, GCD appears in reducing aspect ratios (1920 × 1080 → 16 : 9), synchronising gear trains, scheduling periodic events, and computing hash-table sizes. The GCD × LCM = a × b identity provides a fast path to the LCM once the GCD is known, avoiding potentially large intermediate products.
The Greatest Common Divisor of two integers is the largest positive integer that divides both of them evenly. For example, GCD(48, 36) = 12.
Yes. GCD (Greatest Common Divisor), HCF (Highest Common Factor), and GCF (Greatest Common Factor) all mean the same thing.
It repeatedly replaces the larger number with the remainder of dividing the larger by the smaller, until the remainder is zero. The last non-zero value is the GCD.
For any integers a and b, there exist integers x and y such that ax + by = GCD(a,b). The extended Euclidean algorithm finds x and y.
Two numbers are coprime (relatively prime) if their GCD is 1 — they share no common factor other than 1. Use this as a practical reminder before finalizing the result.
RSA encryption relies on the extended Euclidean algorithm to compute modular inverses. The GCD check ensures keys are valid (coprime to the totient).