GCD Calculator
Find the greatest common divisor.
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
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?
What is the GCD of 48 and 18?
What is the GCD of 0 and 5?
What is the GCD of 1,000,000,000,000,000 and 250,000,000,000,000?
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 YouTubeRectangle 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.