GCD, LCM and the Euclidean algorithm
The greatest common divisor and the least common multiple, by factoring and by the Euclidean algorithm, and at the top level Bézout equations ax + by = c in integers.
How to solve it
The gcd is the largest number that divides both numbers; the lcm is the smallest number both divide. For small numbers both can be read from the prime factorizations; for large ones the Euclidean algorithm is faster: it divides with remainders without factoring anything.
Step by step
- By factoring: the gcd takes the common primes in the smallest powers, the lcm takes all primes in the largest powers.
- The Euclidean algorithm: divide the larger number by the smaller with a remainder, then the divisor by the remainder, and so on until the remainder is zero. The last non-zero remainder is the gcd.
- Get the lcm from the gcd: $\operatorname{lcm}(a, b) = \frac{a \cdot b}{\gcd(a, b)}$.
- The equation $ax + by = c$ is solvable only if $c$ is divisible by $\gcd(a, b)$. Run the Euclidean algorithm backwards to write the gcd through $a$ and $b$, then multiply by $\frac{c}{\gcd}$.
Common mistakes
- Taking the largest powers for the gcd and the smallest for the lcm. It is the other way round: the gcd cannot exceed the smaller number.
- Answering with the zero remainder or the last quotient. The answer is the last non-zero remainder.
- Not checking divisibility in a Bézout equation: $6x + 9y = 7$ has no integer solutions, because $7$ is not divisible by $3$.
- Thinking a Bézout equation has one solution. There are infinitely many: add $\frac{b}{d}t$ to $x$ and subtract $\frac{a}{d}t$ from $y$.