Greatest common divisor using the Euclidean algorithm with steps.
Looking for the GCF Calculator? GCD and GCF are the same concept with different names.
How to Use the GCD Calculator
The greatest common divisor is the largest whole number that divides two or more numbers evenly. It is what you reach for when simplifying fractions, reducing ratios, or dividing things into the largest possible equal groups.
- Enter two to four whole numbers. Type them separated by commas or spaces, such as 48 and 180.
- Watch the Euclidean steps. The calculator shows each division-with-remainder step, so you see the algorithm converge rather than just receiving an answer.
- Read the GCD. The final non-zero remainder is your greatest common divisor.
- Apply it. Use the result to simplify the fraction 48/180 to 4/15, or to split items into groups of 12.
GCD Calculator Formula
The calculator uses the Euclidean algorithm, known for over two thousand years and still the fastest method for the job. The insight: the GCD of a and b equals the GCD of b and the remainder of a divided by b. Repeat — replacing the pair with the divisor and remainder each round — until a remainder of zero appears. The last non-zero remainder is the GCD.
Why does this work? Any common divisor of a and b also divides the remainder, and any common divisor of b and the remainder also divides a — so the set of common divisors never changes, only the numbers shrink. Each step strictly reduces the numbers, guaranteeing termination, and it does so fast: the number of steps grows only logarithmically with input size.
For three or more numbers, the calculator chains the algorithm: the GCD of a, b, and c equals the GCD of the GCD of a and b with c. This works because divisibility is transitive across the grouping. As a cross-check, the prime-factor view shows the GCD as the product of the lowest shared prime powers — for 48 (2 to the fourth times 3) and 180 (2 squared times 3 squared times 5), the shared minimums give 2 squared times 3, which is 12.
GCD, GCF, HCF: Three Names for One Number
Depending on where you learned math, you may know this quantity by three different names. In the United States, textbooks usually call it the greatest common factor (GCF). British and Commonwealth curricula say highest common factor (HCF). Number theorists and computer scientists worldwide prefer greatest common divisor (GCD), the term this page uses. The definitions differ by a word — factor versus divisor — but the quantity is identical: GCF(48, 180) = HCF(48, 180) = GCD(48, 180) = 12. If your assignment says GCF or HCF, you are in the right place; we also keep a dedicated GCF Calculator page for the US naming.
Example Calculation
Find the GCD of 48 and 180. Step 1: 180 divided by 48 is 3 with remainder 36. Step 2: 48 divided by 36 is 1 with remainder 12. Step 3: 36 divided by 12 is 3 with remainder 0. The last non-zero remainder is 12, so the GCD is 12.
Verify with prime factors: 48 is 2 to the fourth times 3, and 180 is 2 squared times 3 squared times 5. Take the lowest exponent of each shared prime: 2 squared times 3 equals 12. Both methods agree. In practice, this tells you the fraction 48/180 simplifies to 4/15, and that 48 and 180 items can be split into equal groups of at most 12.
Special Cases Worth Knowing
| Case | Example | GCD | Why |
|---|---|---|---|
| A number and zero | GCD(24, 0) | 24 | Every integer divides 0, so the other number wins |
| Equal numbers | GCD(7, 7) | 7 | A number divides itself |
| One divides the other | GCD(6, 18) | 6 | The smaller number is already a common divisor |
| Consecutive numbers | GCD(14, 15) | 1 | Neighbours share no factor — always coprime |
| Two different primes | GCD(5, 11) | 1 | Each has no factors to share |
GCD at Work: Bags, Tiles, and Screen Ratios
Identical gift bags. You have 84 chocolates and 126 candies and want identical bags with nothing left over. The most bags you can make is GCD(84, 126) = 42, each holding 2 chocolates and 3 candies.
Tiling a floor. The largest square tile that covers a 24 × 36 foot floor without cuts has side GCD(24, 36) = 12 feet — a 2 × 3 grid of six tiles.
Simplifying a screen ratio. A 1920 × 1080 display reduces by GCD(1920, 1080) = 120 to 16:9 — the ratio printed on every monitor box. The same move shrinks 1280 × 720 and 3840 × 2160 to 16:9 as well, because all three share it.
Common Mistakes to Avoid
Expecting a GCD larger than your smallest input. Impossible — a common divisor cannot exceed any of the numbers. If your answer is bigger than the smallest number you entered, something went wrong.
Taking the higher prime powers. For the GCD you take the lowest power of each shared prime. Taking the highest gives the LCM instead — the classic mix-up. Our LCM Calculator covers the other side.
Stopping at the first common divisor. 2 divides both 48 and 180, but so do 3, 4, 6, and 12. Only the greatest counts.
Frequently Asked Questions
What is the greatest common divisor?
The largest whole number that divides each of your numbers with no remainder. The GCD of 12 and 18 is 6, because 6 is the biggest number dividing both. It is sometimes called the greatest common factor or highest common factor — all three names mean the same thing.
Why use the Euclidean algorithm instead of factoring?
Speed and simplicity. Factoring large numbers is slow, but Euclid's method only needs division with remainder and converges in a handful of steps even for huge inputs. It is one of the oldest algorithms still in daily use, appearing in Euclid's Elements around 300 BC.
How do you find the GCD of three or more numbers?
Chain the pairwise algorithm: first find the GCD of the first two numbers, then find the GCD of that result with the third number, and so on. For 24, 36, and 60: GCD(24,36) is 12, then GCD(12,60) is 12, so the answer is 12.
What does it mean if the GCD is 1?
The numbers are coprime — they share no prime factors. The GCD of 8 and 15 is 1. Coprime pairs appear everywhere from simplified fractions to cryptography, where RSA key generation depends on numbers being coprime.
Where is GCD used in real life?
Simplifying fractions and ratios is the everyday use. It also sizes the largest square tiles for a floor, synchronizes gear teeth, schedules repeating events, and compresses data in algorithms. Anytime you need the biggest equal split of several quantities, you are computing a GCD.
Is HCF the same as GCD?
Yes, and so is GCF. Highest common factor (HCF), greatest common factor (GCF), and greatest common divisor (GCD) are three regional names for the one quantity. US textbooks favor GCF, UK and Commonwealth curricula favor HCF, and number theory and computing favor GCD. The calculation never changes — GCD(24, 36) = HCF(24, 36) = GCF(24, 36) = 12.
What is the GCD of a number and zero?
The number itself: GCD(24, 0) = 24. Every integer divides zero exactly, so the common divisors of 24 and 0 are just the divisors of 24, and the greatest is 24. This is also why the Euclidean algorithm stops cleanly when it reaches a remainder of zero.
Related Calculators
Try our LCM Calculator — the GCD's partner via GCD × LCM = a × b — or our GCF Calculator if your textbook uses the US name.