Find the Greatest Common Divisor (GCD / GCF / HCF) of up to 5 numbers using the Euclidean algorithm and prime factorization — with full step-by-step working for USA and UK math students.
The Greatest Common Divisor (GCD) — also called the Greatest Common Factor (GCF) in the United States or the Highest Common Factor (HCF) in the United Kingdom — is the largest positive integer that divides two or more numbers without leaving a remainder. This free GCD calculator finds the answer using both the Euclidean algorithm and prime factorization, showing every step of the working so you can learn the method, not just the answer.
All three terms — GCD, GCF, and HCF — refer to exactly the same mathematical concept. The terminology simply varies by country and educational tradition:
Regardless of the name, the calculation is identical. Our calculator displays all three abbreviations so students on both sides of the Atlantic can follow along.
The Euclidean algorithm is one of the oldest known algorithms in mathematics, described by Euclid in his Elements around 300 BC. It remains one of the most elegant and efficient methods for computing the GCD of two integers.
The algorithm is based on the principle that GCD(a, b) = GCD(b, a mod b). At each step, we replace the larger number with the remainder of the division, and continue until the remainder is zero. The last non-zero remainder is the GCD.
Example: GCD(48, 18)
Each step shows the division a = q × b + r, where q is the quotient and r is the remainder.
The proof relies on two observations: First, any common divisor of a and b also divides the remainder r = a − q×b (since r is a linear combination of a and b). Second, any common divisor of b and r also divides a. Therefore the set of common divisors of (a, b) equals the set of common divisors of (b, r), which means GCD(a, b) = GCD(b, r).
The algorithm terminates because the remainders form a strictly decreasing sequence of non-negative integers — a sequence that must eventually reach zero.
The extended Euclidean algorithm goes further: it finds integers x and y such that ax + by = GCD(a, b). This is known as Bézout's identity, named after French mathematician Étienne Bézout.
For example, GCD(48, 18) = 6, and we can find: 48×(−1) + 18×3 = −48 + 54 = 6. So x = −1, y = 3.
Bézout's identity has profound implications in number theory and cryptography. It is used to find modular inverses, which are essential in RSA encryption (the most widely used public-key cryptography system). RSA key generation involves finding the GCD of two large prime-related numbers and computing their extended Euclidean coefficients.
An alternative method for finding the GCD is to factor each number into its prime factors and then take the product of the common prime factors with the lowest exponent.
Example: GCD(48, 18)
The prime factorization method is intuitive and visual, but the Euclidean algorithm is much more efficient for large numbers (factoring large integers is computationally hard, while the Euclidean algorithm runs in polynomial time).
The GCD of three or more numbers is found iteratively: GCD(a, b, c) = GCD(GCD(a, b), c). This works because GCD is associative. Our calculator handles up to 5 numbers using this iterative approach.
Two integers are called coprime (or relatively prime) if their GCD equals 1. Coprime numbers share no common prime factors. For example, 8 and 15 are coprime: GCD(8, 15) = 1.
Coprimality is crucial in several areas: in fraction simplification (a fraction a/b is in lowest terms if and only if GCD(a, b) = 1), in modular arithmetic (a has a multiplicative inverse mod n if and only if GCD(a, n) = 1), and in the Chinese Remainder Theorem.
For any two positive integers a and b, the following fundamental relationship holds:
GCD(a, b) × LCM(a, b) = a × b
This means once you know the GCD, you can find the LCM with a single multiplication and division: LCM(a, b) = a × b / GCD(a, b). Our calculator always displays both GCD and LCM for two-number inputs.
To reduce a fraction a/b to lowest terms, divide both numerator and denominator by GCD(a, b). For example, 48/18 = 48÷6 / 18÷6 = 8/3. This is a core skill in GCSE Maths (UK) and middle school arithmetic (US).
The GCD answers questions like "What is the largest number of groups that 48 apples and 18 oranges can be divided into equally?" The answer is GCD(48, 18) = 6 groups of 8 apples and 3 oranges each.
RSA encryption relies on the fact that multiplying two large primes is easy but factoring the result is computationally infeasible. The GCD operation (specifically the extended Euclidean algorithm) is used in RSA to compute the private key exponent. This protects online banking, e-commerce, and communications worldwide.
In the United Kingdom, HCF (Highest Common Factor) is introduced at Key Stage 3 (Years 7–9), typically around age 11–14, as part of the Number strand in the National Curriculum. GCSE Mathematics (Years 10–11) requires students to find the HCF and LCM of numbers using prime factorisation, and to apply these concepts in fraction simplification and ratio problems. The Euclidean algorithm may appear in A-Level Further Mathematics.
In the United States, GCF (Greatest Common Factor) appears in the Common Core State Standards from 6th grade onward (ages 11–12). Students use GCF to simplify fractions and factor algebraic expressions. The Euclidean algorithm is typically introduced in high school Algebra 2 or a discrete mathematics course.
All three terms mean exactly the same thing — the largest integer that divides all given numbers without a remainder. GCF (Greatest Common Factor) is used in US schools. HCF (Highest Common Factor) is the UK school term. GCD (Greatest Common Divisor) is used in university mathematics worldwide.
The Euclidean algorithm repeatedly applies the rule GCD(a, b) = GCD(b, a mod b). At each step, divide the larger number by the smaller and keep the remainder. Continue until the remainder is zero. The last non-zero remainder is the GCD. For GCD(48,18): 48 = 2×18+12, then 18 = 1×12+6, then 12 = 2×6+0, so GCD = 6.
If GCD(a, b) = 1, the numbers are called coprime or relatively prime. They share no common prime factors. For example, GCD(8, 15) = 1 because 8 = 2³ and 15 = 3×5 share no common factors.
For any two positive integers a and b: GCD(a,b) × LCM(a,b) = a × b. This means LCM(a,b) = a×b / GCD(a,b). For example, GCD(48,18) = 6 and LCM(48,18) = 48×18/6 = 144.
Factor each number into primes, then take the product of primes that appear in all factorizations, using the lowest exponent each appears with. For 48 = 2⁴×3 and 18 = 2×3²: common factors are 2¹ and 3¹, so GCD = 2×3 = 6.
To simplify a/b to lowest terms, divide both by GCD(a,b). For example, 48/18: divide both by 6 to get 8/3. A fraction is in simplest form when GCD(numerator, denominator) = 1.
Yes. Find GCD(a,b) first, then GCD(result, c), and so on. For example, GCD(12, 18, 24): GCD(12,18) = 6, then GCD(6,24) = 6. Our calculator handles up to 5 numbers automatically.
The extended Euclidean algorithm finds integers x and y such that ax + by = GCD(a,b) (Bézout's identity). This is used to find modular inverses, which are essential in RSA cryptography and modular arithmetic in number theory.
Results are for educational purposes only. All GCD calculations are mathematically exact for integers within JavaScript's safe integer range.