Calculate the Greatest Common Divisor of any integers.
Enter two or more positive integers separated by commas.
Greatest Common Divisor
—
Enter numbers to see GCD and Euclid\'s algorithm steps.
The GCD Calculator finds the Greatest Common Divisor (also called Highest Common Factor) of two or more positive integers using Euclid\'s algorithm — the same algorithm that has been used for over 2,000 years. Enter your numbers separated by commas, and the calculator returns the largest integer that divides all of them evenly. It also displays the step-by-step Euclidean reduction so you can verify the work.
GCD(a, b) = GCD(b, a mod b), repeated until b = 0
The key insight: if d divides both a and b, then d also divides (a mod b). So we can replace the larger number with the remainder, shrinking the problem each step. The algorithm always terminates because the second argument strictly decreases.
Find GCD(48, 18):
Verify: 48 ÷ 6 = 8 ✓, 18 ÷ 6 = 3 ✓. No larger number divides both.
The most common everyday use of GCD is simplifying fractions. The fraction 18/48 simplifies by dividing both top and bottom by GCD(18, 48) = 6, giving 3/8. Without GCD, you might simplify step-by-step (divide by 2 to get 9/24, then by 3 to get 3/8), but GCD gets you there in one step.
Beyond fractions, GCD powers the RSA encryption algorithm that secures internet communication. RSA relies on the difficulty of finding the GCD of two enormous prime products — easy in one direction (just multiply two primes), but computationally hard to reverse. Every time you visit a secure website, Euclid\'s 2,300-year-old algorithm is working behind the scenes.
GCD also appears in scheduling and tiling problems. To find the largest square tile that fits evenly in a 48-by-18 rectangle, you compute GCD(48, 18) = 6 — so 6×6 tiles fit perfectly (8 across, 3 down). If you tried 7×7 tiles, they would not fit evenly. This makes GCD a surprisingly practical tool for everything from interior design to computer graphics.
GCD (Greatest Common Divisor), also called HCF (Highest Common Factor), is the largest positive integer that divides each of the given numbers without a remainder. For example, GCD(12, 18) = 6 because 6 is the largest number that divides both 12 and 18.
The most efficient method is Euclid's algorithm: repeatedly replace (a, b) with (b, a mod b) until b becomes 0. The remaining a is the GCD. Example: GCD(48, 18) → GCD(18, 12) → GCD(12, 6) → GCD(6, 0) = 6.
GCD is the largest number that divides all inputs (greatest common divisor). LCM is the smallest number that all inputs divide (least common multiple). They are related by: GCD(a,b) × LCM(a,b) = a × b.
GCD is used to simplify fractions (divide numerator and denominator by their GCD), find the largest square tile that fits a rectangle evenly, and in cryptography (RSA algorithm). It also appears in number theory proofs.
Yes. GCD(a, b, c) = GCD(GCD(a, b), c). The calculator handles any number of comma-separated inputs.
Join thousands of students using Ahasn.xyz to track grades, plan studies, and reach academic goals — completely free.