The greatest common factor is the largest number that divides every input exactly. The least common multiple is the smallest number every input divides into. They are opposite ends of the same idea, and both fall straight out of prime factorisation.
Through prime factors
Factor each number into primes. For the GCF take the lowest power of each shared prime; for the LCM take the highest power of every prime that appears.
The Euclidean algorithm
Factorising is slow for large numbers. Euclid’s method is far faster: divide the larger by the smaller, keep the remainder, repeat until the remainder is zero. The last non-zero remainder is the GCF.
This is one of the oldest algorithms still in everyday use, dating to around 300 BC, and it remains the method computers actually use. It is fast enough to handle numbers with hundreds of digits.
The identity linking them
This holds for exactly two numbers and is the usual way to get the LCM: find the GCF by Euclid, then divide the product by it. It fails for three or more, where you must chain the operation pairwise instead.
Where they get used
- Simplifying fractions. Divide top and bottom by their GCF to reach lowest terms in one step.
- Adding fractions. The LCM of the denominators is the least common denominator, which keeps the arithmetic as small as possible.
- Repeating events. Two buses leaving every 12 and 18 minutes coincide every LCM(12,18) = 36 minutes. Gear teeth, traffic lights and scheduling problems all reduce to this.
- Cryptography. Numbers whose GCF is 1 are coprime, and coprimality is central to RSA and to modular arithmetic generally.