Greatest common divisor

To find it, list the common divisors or, better, factor: take the primes present in both numbers with the smaller exponent. So \(48=2^4\cdot3\) and \(180=2^2\cdot3^2\cdot5\) give \(\gcd(48,180)=2^2\cdot3=12\). Two integers with \(\gcd(a,b)=1\) are called coprime, like 35 and 64, even though neither is prime.

Some properties are used constantly: \(\gcd(a,0)=|a|\), \(\gcd(a,b)=\gcd(b,a)\) and \(\gcd(a,b)=\gcd(a-qb,\,b)\) for any integer \(q\). The last one says that subtracting multiples of one number from the other does not change the common divisors, and it drives the Euclidean algorithm. Also, if \(d=\gcd(a,b)\), then \(a/d\) and \(b/d\) are coprime, which is why a fraction is reduced by dividing numerator and denominator by their gcd.

The gcd is also the smallest positive integer of the form \(ma+nb\) with integers \(m,n\) (Bézout's identity), which guarantees that \(ax+by=c\) has integer solutions exactly when \(\gcd(a,b)\mid c\). It relates to the least common multiple through \(\gcd(a,b)\cdot\operatorname{lcm}(a,b)=|ab|\). A typical error is to mix them up: the gcd is always at most both numbers; the lcm is at least both.