Two questions that are really one question

The greatest common divisor of two numbers is the largest number that divides both exactly. The lowest common multiple is the smallest number both divide into. They sound like opposites and they are tied together by one identity:

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

So you only ever need to compute one of them. Find the GCD, which is fast, then get the LCM by division. This is how every implementation does it, and it is why a calculator that finds the LCM by listing multiples is doing far more work than necessary.

Euclid algorithm — worked on 48 and 180

Euclid method is over two thousand years old and still the fastest general approach. Divide the larger by the smaller, keep the remainder, repeat with the pair you just used:

The last non-zero remainder is the answer: GCD(48, 180) = 12. Three steps, no factorising.

Now the LCM comes free: 48 × 180 ÷ 12 = 8,640 ÷ 12 = 720.

The prime factorisation view, which shows why it works

Break both numbers into primes:

• 48 = 2⁴ × 3
• 180 = 2² × 3² × 5

For the GCD, take the lowest power of each shared prime: 2² × 3 = 12. For the LCM, take the highest power of every prime that appears in either: 2⁴ × 3² × 5 = 16 × 9 × 5 = 720. Same answers.

This method is more illuminating but much slower for large numbers, because factorising is hard while dividing is easy. Use it to understand the result; use Euclid to compute it.

Where these turn up in real work

• Simplifying fractions. To reduce 48/180, divide both by the GCD: 4/15. That is the definitive lowest form, in one step, with no guessing at common factors.
• Adding fractions. The LCM is the lowest common denominator. Adding 1/48 and 1/180 needs denominator 720: 15/720 + 4/720 = 19/720.
• Scheduling coincidences. One bus every 48 minutes, another every 180. Both leave together, then next coincide after LCM = 720 minutes, exactly 12 hours later. Any question of the form when will these cycles line up again is an LCM question.
• Gears and pulleys. Teeth counts sharing a large GCD mean the same pairs of teeth mesh repeatedly, concentrating wear. Engineers often choose counts that are coprime — GCD of 1 — so wear spreads evenly.
• Tiling and cutting. The largest square tile that fits a 48 by 180 cm area with no cutting is 12 cm, the GCD. The smallest square you can build from 48 by 180 rectangles has side 720.
• Aspect ratios. 1920 by 1080 divided by their GCD of 120 gives 16:9.

Special cases worth knowing

• Coprime numbers have GCD 1, so their LCM is simply their product. 9 and 28 share nothing, so LCM = 252.
• If one divides the other, the answers are trivial: GCD(6, 24) = 6 and LCM(6, 24) = 24.
• GCD with zero: GCD(a, 0) = a, since every number divides zero. This is the base case that terminates Euclid algorithm.
• More than two numbers: apply the operation pairwise. GCD(a, b, c) = GCD(GCD(a, b), c). The same chaining works for LCM.
• Careful with the identity for three or more numbers. GCD × LCM = product holds only for two numbers. For 4, 6 and 8 the GCD is 2 and the LCM is 24, whose product is 48, not 192.

Questions people actually ask

Is HCF the same as GCD?

Yes. Highest common factor, greatest common divisor and greatest common factor are three names for one thing. HCF is more common in British and South Asian curricula, GCD in computing and American texts.

How fast is Euclid algorithm really?

Remarkably fast. The number of steps grows with the logarithm of the inputs, and the worst case is a pair of consecutive Fibonacci numbers. Even for numbers with hundreds of digits it finishes in well under a thousand steps, which is why it underpins modular inverse computation in cryptography.

Can the GCD be larger than either number?

No. A divisor of a number cannot exceed it, so the GCD is at most the smaller input. Conversely the LCM is at least the larger input.

Are the numbers I enter stored?

No. Everything is computed in your browser, and nothing is transmitted or saved.