Two of the most useful ideas in basic math are the greatest common divisor (GCD) and the least common multiple (LCM). They show up in school homework, coding interviews, and everyday puzzles like figuring out when two repeating events line up. This guide explains both with simple examples you can do in your head.
The GCD of two numbers is the largest number that divides both of them evenly. For 12 and 18, the common divisors are 1, 2, 3, and 6, so the GCD is 6. Listing every divisor works for small numbers, but there is a smarter way for bigger ones: Euclid's algorithm.
Euclid's algorithm is over two thousand years old and still the fastest simple method. To find the GCD of 48 and 18, divide 48 by 18 and take the remainder: 48 = 2 x 18 + 12. Now replace the pair (48, 18) with (18, 12) and repeat: 18 = 1 x 12 + 6. Repeat again with (12, 6): 12 = 2 x 6 + 0. When the remainder hits zero, the last non-zero remainder is the GCD. So GCD(48, 18) = 6.
The LCM is the flip side: the smallest number that is a multiple of both. For 4 and 6, the multiples of 4 are 4, 8, 12, 16, and the multiples of 6 are 6, 12, 18, so the LCM is 12. Here is the trick that saves you from listing: LCM(a, b) = (a x b) / GCD(a, b). For 4 and 6, that is (4 x 6) / 2 = 12. Compute one, get the other free.
Let us try a bigger pair by hand: 36 and 48. Euclid's algorithm: 48 = 1 x 36 + 12, then 36 = 3 x 12 + 0, so GCD = 12. Then LCM = (36 x 48) / 12 = 1728 / 12 = 144. Check it: 144 / 36 = 4 and 144 / 48 = 3, both whole numbers. Correct.
Where does this come up in real life? Adding fractions needs a common denominator, which is the LCM of the denominators. Simplifying a fraction to lowest terms means dividing top and bottom by their GCD. Two buses that leave every 12 and 18 minutes meet every LCM(12, 18) = 36 minutes. The same idea schedules tasks, syncs animations, and compresses data in code.
If you want to double-check your hand calculations or work with larger numbers, Factor Calculator factors any number instantly and makes GCD and LCM practice much faster.
Learn Euclid's algorithm once, remember the GCD-to-LCM formula, and these problems stop being work and start being fun.
Top comments (0)