GCD Calculator

The greatest common divisor (GCD) of two or more whole numbers is the largest number that divides all of them exactly, with no remainder. It is also called the greatest common factor (GCF) or highest common factor (HCF). For example, the numbers that divide both 48 and 18 are 1, 2, 3 and 6, and the biggest of these is 6, so the GCD of 48 and 18 is 6. This GCD calculator finds the answer for two or more numbers and shows the Euclidean algorithm one step at a time, plus a Venn diagram of the prime factors for two numbers.

• The GCD is never larger than the smallest of the numbers, and it is always at least 1.
• If the GCD is 1, the numbers are called coprime (or relatively prime). 35 and 18 are coprime even though neither is prime.
• GCD(a, 0) = a, and GCD(a, a) = a.
• GCD(a, b) × LCM(a, b) = a × b. For 48 and 18: 6 × 144 = 864 = 48 × 18.
• The order of the numbers does not matter, and for more than two numbers you can combine them in pairs: GCD(a, b, c) = GCD(GCD(a, b), c).

The Euclidean algorithm is the fastest method by hand, and it is the one used in the animated walk-through above. It rests on one fact: the GCD of two numbers does not change when you replace the larger number by its remainder after division by the smaller one. Take 252 and 105 as an example.

1. Divide the larger number by the smaller one: 252 = 105 × 2 + 42. The remainder is 42.
2. Now divide the previous divisor by that remainder: 105 = 42 × 2 + 21. The remainder is 21.
3. Repeat: 42 = 21 × 2 + 0. The remainder is 0, so stop.
4. The last non-zero remainder is the GCD. GCD(252, 105) = 21.
5. Check: 252 = 21 × 12 and 105 = 21 × 5, and 12 and 5 have no common factor left.

The second method writes each number as a product of primes. Then the GCD is the product of the primes the numbers share, each taken to the smaller of its powers. This is what the Venn diagram shows: the overlap holds the shared primes. For 48 = 2⁴ × 3 and 18 = 2 × 3², the shared part is 2 × 3 = 6, so GCD(48, 18) = 6. The Euclidean algorithm gives the same answer: 48 = 18 × 2 + 12, 18 = 12 × 1 + 6, 12 = 6 × 2 + 0.

Find the GCD of the first two numbers, then find the GCD of that result and the third number, and so on. For 24, 36 and 60: GCD(24, 36) = 12, then GCD(12, 60) = 12. So the GCD of 24, 36 and 60 is 12.

• Simplifying fractions: divide the top and bottom by their GCD. For 36/84 the GCD is 12, so 36/84 = 3/7.
• Simplifying ratios: 12 : 18 becomes 2 : 3 after dividing both by 6.
• Tiling and cutting: the biggest square tile that exactly covers a 48 cm by 18 cm floor strip has a side of GCD(48, 18) = 6 cm, giving 8 × 3 = 24 tiles.
• Sharing equally: the most groups you can make from 24 apples and 36 oranges with the same mix in each group is GCD(24, 36) = 12 groups.
• Computer science: the GCD is used in cryptography (such as RSA key generation), in reducing rational numbers and in modular arithmetic.