Mathematics CalcyZone Calculator

GCD Calculator (Greatest Common Divisor)

Calculate the greatest common divisor (GCD) or highest common factor (HCF) of numbers.

Number 1

Number 2

Calculation Solution

GCD = 50

Euclidean Algorithm Result

Mathematical Formula

GCD(a, b) via Euclidean Algorithm

Overview & Explanation

The Greatest Common Divisor (GCD), also known as Highest Common Factor (HCF), is the largest positive integer that divides both numbers without a remainder.

How It Works

Apply the Euclidean algorithm iteratively: GCD(a, b) = GCD(b, a mod b) until remainder is zero.

Practical Applications

Simplifying ratios and fractions.
Tiling rectangular areas without cutting tiles.

Greatest common divisor

The greatest common divisor (GCD), also called the highest common factor (HCF), is the largest whole number that divides two or more numbers exactly. The divisors of 84 include 1, 2, 3, 4, 6, 7, 12, 14, 21, 28, 42, 84, and those of 36 include 1, 2, 3, 4, 6, 9, 12, 18, 36, so GCD(84, 36) = 12.

The Euclidean algorithm

Listing divisors is slow for large numbers. Euclid's algorithm repeatedly replaces the larger number by the remainder after dividing: 84 = 2 × 36 + 12, then 36 = 3 × 12 + 0. When the remainder reaches 0, the last non-zero remainder, 12, is the GCD. This method has been used for over two thousand years and is still how computers calculate it.

Prime factorisation also works: 84 = 2² × 3 × 7 and 36 = 2² × 3², and the shared primes at their lowest powers give 2² × 3 = 12.

Uses

The GCD simplifies fractions: 36/84 divided top and bottom by 12 becomes 3/7. It solves sharing problems, such as cutting 84 cm and 36 cm ribbons into equal pieces as long as possible (12 cm each), and it is linked to the LCM through GCD × LCM = a × b, so LCM(84, 36) = 3,024 ÷ 12 = 252.