Greatest Common Divisor (GCD)

How the GCD calculator works

The greatest common divisor (GCD), also called the highest common factor (HCF) or greatest common factor (GCF), is the largest whole number that divides two numbers exactly, with no remainder. Finding it is the key step in simplifying fractions, splitting items into equal groups, tiling a rectangle with the largest possible squares, and many number-theory problems. This calculator uses the Euclidean algorithm, which is far faster than listing every factor: it repeatedly replaces the larger number by its remainder when divided by the smaller number until the remainder reaches zero. The last non-zero value is the GCD.

Required Inputs & Typical Use Cases

• First number and Second number

  Two positive whole numbers (integers of 1 or more). Commas such as 1,200 are accepted. Decimals, negatives, and zero are not allowed.

The Formula

gcd(a, b) = gcd(b, a mod b), with gcd(a, 0) = |a|.
For coprime numbers, gcd = 1.
Related: lcm(a, b) = (a × b) / gcd(a, b)

• a, b

  The two positive integers you want to compare, with a ≥ b for the first step.

• a mod b

  The remainder left after dividing a by b.

• coprime

  Two numbers whose only common divisor is 1, so their GCD is 1.

Worked Example

1. Example 1: GCD of 48 and 18

   48 = 18 × 2 + 12, so gcd(48, 18) = gcd(18, 12). 18 = 12 × 1 + 6, so gcd(18, 12) = gcd(12, 6). 12 = 6 × 2 + 0, so the GCD is 6.

2. Example 2: GCD of 84 and 36, checked by prime factors

   Euclid: 84 = 36 × 2 + 12, then 36 = 12 × 3 + 0, so the GCD is 12. Check: 84 = 2² × 3 × 7 and 36 = 2² × 3². The shared factors are 2² × 3 = 12.

3. Example 3: simplifying a fraction with the GCD

   To simplify 48/18, divide top and bottom by gcd(48, 18) = 6 to get 8/3. The LCM of 48 and 18 is 48 × 18 / 6 = 144.

4. Example 4: coprime numbers

   gcd(35, 64) = 1, because 35 = 5 × 7 and 64 = 2⁶ share no prime factor. A fraction such as 35/64 is already in lowest terms.

Tips, Assumptions & Limitations

• Common mistake: confusing GCD with LCM. The GCD is the largest number that divides both values and is never larger than the smaller input. The LCM is the smallest number both divide into and is never smaller than the larger input.
• Common mistake: stopping early. Keep dividing until the remainder is exactly 0, and take the previous divisor, not the zero.
• Common mistake: assuming a result of 1 means an error. Coprime numbers legitimately have a GCD of 1.
• Common mistake: entering decimals or negatives. This tool needs positive whole numbers; for decimals, scale both values to integers first.
• If one number divides the other exactly, the GCD is the smaller number. For example, gcd(12, 60) = 12.
• Need the LCM as well? Use the LCM & HCF calculator, or the fraction simplifier to reduce fractions automatically.