Skip to content
calculateeveryday

GCD Calculator (Greatest Common Divisor / HCF, with Steps)

Greatest common divisor of two or three numbers, by Euclid's algorithm and by prime factors, working shown.

Inputs

GCD of 48, 18
6

Use this calculator on your own site

Free embed

  • Two lines of HTML, unlimited views
  • Shows a small CalculateEveryday bar, with a credit link under the calculator

What each GCD input means

First number
The first whole number. A negative number is treated as its size; decimals are refused, because the GCD is only defined for whole numbers.
Second number
The second whole number. The order makes no difference: GCD(18, 48) = GCD(48, 18).
Third number (optional)
An optional third number. Leave it at 0 for two numbers — 0 is ignored here, since every number divides it.

GCD formula

Euclid: divide the larger by the smaller, then the divisor by the remainder, until the remainder is 0 — the last non-zero remainder is the GCD · By primes: multiply the primes the numbers share

gcd⁡(a,b)=gcd⁡(b, a mod b),gcd⁡(a,0)=a\gcd(a, b) = \gcd(b,\ a \bmod b), \quad \gcd(a, 0) = a

The greatest common divisor — also called the greatest common factor or highest common factor — is the largest whole number that divides all the given numbers exactly. Euclid's algorithm finds it without any factoring: divide the larger number by the smaller and keep the remainder, then divide the previous divisor by that remainder, and repeat until a remainder of 0 appears; the last non-zero remainder is the GCD. For 48 and 18: 48 = 2 × 18 + 12, 18 = 1 × 12 + 6, 12 = 2 × 6 + 0, so the GCD is 6. The prime-factor route gives the same answer and shows why: 48 = 2 × 2 × 2 × 2 × 3 and 18 = 2 × 3 × 3 share one 2 and one 3, and 2 × 3 = 6. For three numbers, find the GCD of two of them and then the GCD of that result with the third.

GCD worked example

GCD of 48 and 18 by Euclid: 48 ÷ 18 is 2 remainder 12; 18 ÷ 12 is 1 remainder 6; 12 ÷ 6 is 2 remainder 0. The last non-zero remainder is 6, so GCD(48, 18) = 6 — and indeed 48 = 6 × 8 and 18 = 6 × 3. By prime factors: 48 = 2 × 2 × 2 × 2 × 3, 18 = 2 × 3 × 3; the shared primes are one 2 and one 3, and 2 × 3 = 6.

More GCD examples

Euclid's algorithm on 1,071 and 462: 1071 = 2 × 462 + 147, then 462 = 3 × 147 + 21, then 147 = 7 × 21 + 0. The last non-zero remainder gives GCD = 21, after three divisions and no factoring at all. The prime factors agree: the shared primes are 3 and 7, and 3 × 7 = 21.

Three numbers: GCD(84, 126) = 42, then GCD(42, 210) = 42, since 210 = 5 × 42. So 84, 126 and 210 items can be split into 2, 3 and 5 equal groups of 42.

Where the GCD calculator can give the wrong answer

  • GCD is defined for whole numbers. Decimals are refused; for fractions, put them over a common denominator first, or find the GCD of the numerators and the LCM of the denominators.
  • GCD(a, 0) = a for any a above 0, because every number divides 0. GCD(0, 0) has no answer and the page says so.
  • A GCD of 1 means the numbers are coprime — they share no prime factor — even if neither of them is prime. 8 and 15 are coprime.
  • The prime-factor lines are only shown for numbers up to a billion, since factoring bigger ones takes noticeably longer than Euclid's algorithm, which works instantly at any size allowed here.
  • Sign is ignored: GCD(−48, 18) is treated as GCD(48, 18) = 6, the usual convention.

Spotted a mistake? Tell us

GCD FAQ

Either list both numbers' prime factors and multiply the ones they share, or use Euclid's algorithm: divide the larger by the smaller, replace the larger with the remainder, and repeat until the remainder is 0 — the last non-zero remainder is the GCD. For 54 and 36: 54 = 1 × 36 + 18, 36 = 2 × 18 + 0, so GCD = 18.

Related calculators