GCD Calculator

Find the greatest common divisor.

FreeNo accountOn your device

Runs in your browser. How to verify

Loading tool…

About this tool

Enter two whole numbers to find the largest number that divides both. GCD(84, 36) is 12, so 84/36 reduces to 7/3.

How to use

1
Step 1
Enter the first whole number.
2
Step 2
Enter the second whole number.
3
Step 3
Press Calculate to see the GCD and the Euclidean steps.

How it works

The Euclidean algorithm replaces the pair (a, b) with (b, a mod b) until the remainder is 0. The last non-zero value is the GCD. For 1071 and 462 it takes three divisions. Two numbers with GCD 1 are called coprime.

GCD(a, b) = GCD(b, a mod b)      GCD(a, 0) = a      LCM(a, b) = a × b ÷ GCD(a, b)

Worked example

Euclid's classic pair

Input
a = 1071, b = 462
Output
21
Walkthrough
1071 = 2 × 462 + 147; 462 = 3 × 147 + 21; 147 = 7 × 21 + 0. The last non-zero remainder is 21.

Limitations

  • Both numbers must be whole and 0 or more; 12.5 or −12 is rejected.
  • For three or more numbers, take the GCD of the first pair and then of that result with the next number.

Questions

What is the GCD of 84 and 36?
GCD(84, 36) = 12, because 12 is the largest number that divides both 84 and 36.
What is the GCD of 48 and 18?
6.
What is the GCD of 0 and 5?
5. Every number divides 0, so the GCD is the other number.
What is the GCD of 1,000,000,000,000,000 and 250,000,000,000,000?
250,000,000,000,000, since the second number divides the first.

Features

  • Euclidean algorithm steps
  • Large whole numbers
  • Runs in your browser

Related resources

Guides and videos from around the web—opens on YouTube or the publisher’s site.

  • Variables, expressions, and equations

    Khan Academy

    Expression language for scientific and expression calculators.

    Watch on YouTube
  • Rectangle area as product of dimensions

    Khan Academy

    Foundational area thinking across math tools.

    Watch on YouTube
  • Scientific Notation

    Math is Fun

    Powers of ten for scientific calculator displays.

  • Pi

    Math is Fun

    What π means when calculators return pi-based results.