---
url: https://findutils.com/blog/gcd-and-lcm-explained-euclids-algorithm-for-fractions-ratios-and-schedules
title: "GCD and LCM Explained: Euclid's Algorithm for Fractions, Ratios and Schedules"
description: "What the greatest common divisor and least common multiple are, how Euclid's algorithm finds them in a few steps, and where they show up: fractions, screen ratios, schedules."
category: calculators
content_type: blog
cluster: math
locale: en
read_time: 7
status: published
author: "olgunozoktas"
published_at: 2026-10-21T15:08:00Z
excerpt: "Why is a 1920 × 1080 screen 16:9 but a 2560 × 1080 one 64:27? When do two buses leaving every 12 and 18 minutes meet again? Both answers come from the GCD and the LCM. Here is what they are, how a 2,300-year-old algorithm finds them in a handful of steps, and the everyday places they turn up."
tag_ids: ["math", "calculators", "gcd", "lcm", "number-theory"]
tags: ["Math", "Calculators", "GCD", "LCM", "Number Theory"]
primary_keyword: "gcd and lcm"
secondary_keywords: ["euclidean algorithm", "greatest common divisor", "least common multiple", "how to find gcd", "lcm formula", "simplify aspect ratio"]
tool_tag: "gcd-lcm-calculator"
related_tool: "gcd-lcm-calculator"
related_tools: ["gcd-lcm-calculator", "prime-checker", "fraction-calculator", "aspect-ratio-calculator", "scientific-calculator", "percentage-calculator"]
updated_at: "2026-10-21T15:08:00Z"
og_image: "/images/content/blog/gcd-and-lcm-explained-euclids-algorithm-for-fractions-ratios-and-schedules-cover-20261021.webp"
image_alt: "A long rectangle filled with progressively smaller squares in violet, blue and teal, the smallest square highlighted, beside two gear wheels of different sizes whose marked teeth line up."
---

The greatest common divisor (GCD) of two whole numbers is the largest number that divides both exactly. The least common multiple (LCM) is the smallest number that both divide into exactly. For 12 and 18, the GCD is 6 and the LCM is 36. The two are linked by one formula, GCD × LCM = a × b, and both can be found in a few steps with Euclid's algorithm, without factoring either number.

That sounds like school arithmetic, and it is, but the same two numbers decide how far a fraction reduces, why a monitor sold as "21:9" is really 64:27, and when two repeating schedules line up again. You can check every example below in the FindUtils [GCD & LCM Calculator](/calculate/gcd-lcm-calculator/).

## GCD and LCM in One Table

| Numbers | GCD | LCM | Check: GCD × LCM = a × b |
|---------|-----|-----|---------------------------|
| 12 and 18 | 6 | 36 | 6 × 36 = 216 = 12 × 18 |
| 48 and 180 | 12 | 720 | 12 × 720 = 8,640 = 48 × 180 |
| 1920 and 1080 | 120 | 17,280 | 120 × 17,280 = 2,073,600 |
| 7 and 13 | 1 | 91 | Coprime: no shared factor, so LCM = a × b |
| 0 and 5 | 5 | 0 | Every number divides 0 |

GCD, HCF (highest common factor) and GCF (greatest common factor) are three names for the same number. When the GCD is 1, as for 7 and 13, the numbers are called coprime. Neither has to be prime for that: 6 and 35 are coprime too.

## Euclid's Algorithm: Find the GCD Without Factoring

The method in Euclid's *Elements* (Book VII, around 300 BC) rests on one fact: the GCD of two numbers does not change if you replace the larger one with its remainder after dividing by the smaller one. Repeat until the remainder is 0. The last non-zero number is the GCD.

The textbook example is 1071 and 462:

| Step | Division | Remainder |
|------|----------|-----------|
| 1 | 1071 = 2 × 462 + 147 | 147 |
| 2 | 462 = 3 × 147 + 21 | 21 |
| 3 | 147 = 7 × 21 + 0 | 0 |

The GCD is 21, found in three divisions. Factoring both numbers would have given the same answer (1071 = 3² × 7 × 17 and 462 = 2 × 3 × 7 × 11 share 3 × 7), but factoring gets slow for large numbers, while Euclid's algorithm stays fast. In 1844 Gabriel Lamé proved that it never needs more than five times as many steps as the smaller number has decimal digits. His proof is often called the beginning of computational complexity theory.

There is also a picture behind it. Cover a 1071 × 462 rectangle with the largest squares that fit, then fill the leftover strip the same way, and so on. The smallest square that finally fits exactly is 21 × 21.

## From GCD to LCM

Once you have the GCD, the LCM is one division away:

**LCM(a, b) = a × b ÷ GCD(a, b)**

For 12 and 18: 12 × 18 ÷ 6 = 36. For more than two numbers, work in pairs: GCD(a, b, c) = GCD(GCD(a, b), c), and the LCM works the same way. The calculator takes two numbers at a time, so for three numbers, run it twice and feed the first result into the second run.

## Where GCD Shows Up

### Reducing Fractions

Divide the top and bottom of a fraction by their GCD and it is fully reduced in one step. 48/180: the GCD is 12, so 48/180 = 4/15. The [Fraction Calculator](/calculate/fraction-calculator/) does this automatically after every operation and shows the steps.

### Screen and Image Aspect Ratios

An aspect ratio is width and height divided by their GCD. This is exactly what the [Aspect Ratio Calculator](/calculate/aspect-ratio-calculator/) does:

| Resolution | GCD | Exact ratio | Usually sold as |
|------------|-----|-------------|-----------------|
| 1920 × 1080 | 120 | 16:9 | 16:9 |
| 2560 × 1080 | 40 | 64:27 | "21:9" |
| 3440 × 1440 | 80 | 43:18 | "21:9" |
| 1366 × 768 | 2 | 683:384 | "16:9" |

"21:9" is a marketing name, not a reduced ratio, and 1366 × 768 is only close to 16:9 (1.779 against 1.778). If an exact ratio comes out with large numbers, the size is an approximation of a familiar ratio, not a true one. That matters when you crop or scale an image and want no stretched pixels.

### Tiles, Cuts and Equal Groups

The GCD is the largest equal size that divides two lengths with nothing left over. A 24 × 60 cm panel can be covered by 12 × 12 cm tiles (GCD 12) with no cutting: 2 by 5 tiles. The same logic splits 48 pencils and 180 sheets into the largest number of identical packs: 12 packs of 4 pencils and 15 sheets.

## Where LCM Shows Up

### Repeating Schedules

Two buses leave a stop together, one every 12 minutes and one every 18. They leave together again after LCM(12, 18) = 36 minutes. The same goes for a task that runs every 4 days and another every 6: they coincide every 12 days.

### Adding Fractions

To add 1/12 + 1/18, you need a common denominator, and the smallest one is the LCM: 36. That gives 3/36 + 2/36 = 5/36, with no reducing needed afterwards.

### Gears and Cycles

Two meshing gears with 12 and 18 teeth return to the same starting position after LCM(12, 18) = 36 teeth have passed: 3 turns of the small gear and 2 of the large one.

## Two Things to Watch

**Zero.** GCD(a, 0) is a, because every number divides 0, and the LCM with 0 is 0. GCD(0, 0) has no natural answer; the calculator shows 0 for it.

**Very large inputs.** The LCM can grow far larger than either input; for coprime numbers it is their full product. Browsers store whole numbers exactly only up to 9,007,199,254,740,991, so when the LCM goes past that, the last digits of any browser-based answer can be rounded. For numbers that large, use a tool with exact big-integer arithmetic.

## FAQ

### What is the difference between GCD and LCM?

The GCD is the largest number that divides both of your numbers. The LCM is the smallest number that both of your numbers divide into. For 12 and 18 the GCD is 6 and the LCM is 36.

### How do you find the GCD of two numbers quickly?

Use Euclid's algorithm: divide the larger number by the smaller, keep the remainder, and repeat with the smaller number and the remainder until the remainder is 0. The last non-zero remainder is the GCD.

### How do you calculate the LCM from the GCD?

Multiply the two numbers and divide by their GCD. For 12 and 18: 12 × 18 ÷ 6 = 36.

### Are GCD, GCF and HCF the same?

Yes. Greatest common divisor, greatest common factor and highest common factor are three names for the same number.

### How do I simplify an aspect ratio?

Divide the width and height by their GCD. 1920 × 1080 has a GCD of 120, which gives 16:9.

### Can I find the GCD of three numbers?

Yes. Find the GCD of the first two, then the GCD of that result and the third number. The LCM of several numbers works the same way.

## Related Reading

- [Prime Checker guide: test any number and get its prime factorization](/guides/prime-checker-guide/)
- [Aspect Ratio Calculator guide](/guides/aspect-ratio-calculator-guide/)
- [Percentage Calculator guide](/guides/percentage-calculator-guide/)
- [Sample vs population standard deviation](/blog/sample-vs-population-standard-deviation-why-n-minus-1/)

Need help with a project? The team behind FindUtils takes on [freelance work](https://www.upwork.com/freelancers/~010a5875eab37b4bd7), such as [a fast React front end for your web app, dashboard or admin panel](https://www.upwork.com/services/product/development-it-a-fast-react-front-end-for-your-web-app-dashboard-or-admin-panel-2112446421681618043).

## Sources

- [Wikipedia: Euclidean algorithm (Elements Book VII, Lamé's theorem, 1071 and 462 example)](https://en.wikipedia.org/wiki/Euclidean_algorithm)
- [Wikipedia: Greatest common divisor](https://en.wikipedia.org/wiki/Greatest_common_divisor)
- [Wikipedia: Least common multiple](https://en.wikipedia.org/wiki/Least_common_multiple)
- [Euclid's Elements, Book VII, Propositions 1 and 2 (D. E. Joyce, Clark University)](https://mathcs.clarku.edu/~djoyce/java/elements/bookVII/propVII2.html)
- [MDN Web Docs: Number.MAX_SAFE_INTEGER](https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Number/MAX_SAFE_INTEGER)