Greatest common divisor and least common multiple

The greatest common divisor and the least common multiple

In the lesson on divisibility and division with remainder the relation $d \mid a$ between two natural numbers was studied. When two numbers are considered at once, what matters are the divisors they have in common and the multiples they share. Every pair of natural numbers $a$ and $b$ has at least one common divisor, namely $1$, and at most finitely many of them, because no divisor of $a$ exceeds $a$; it has, moreover, infinitely many common multiples, among them the product $ab$. If this is so, the following definition makes sense.

Definition (greatest common divisor and least common multiple). The greatest common divisor of two natural numbers $a$ and $b$, written $\operatorname{gcd}(a, b)$, is the greatest natural number that divides both. The least common multiple, written $\operatorname{lcm}(a, b)$, is the least natural number that is a multiple of both.

The second is the least element of a nonempty set of natural numbers, which exists by the well-ordering principle. The first is the greatest element of the set of common divisors, which is nonempty and bounded by $a$; that a nonempty set of natural numbers bounded above has a greatest element also follows from well-ordering: the set of its upper bounds is nonempty and has a least element $M$, and $M$ belongs to the set, because otherwise every element would be less than $M$ and, since there are no natural numbers between $M - 1$ and $M$, not greater than $M - 1$, which would be an upper bound less than $M$ (if $M = 1$, the set is $\{1\}$ and contains $M$). For example, the common divisors of $12$ and $18$ are $1$, $2$, $3$ and $6$, and their common multiples are $36$, $72$, $108$, and so on:

Some particular cases follow immediately from the definition: $\operatorname{gcd}(a, 1) = 1$ and $\operatorname{lcm}(a, 1) = a$; $\operatorname{gcd}(a, a) = \operatorname{lcm}(a, a) = a$; and, if $a$ divides $b$, then $\operatorname{gcd}(a, b) = a$ and $\operatorname{lcm}(a, b) = b$. Both operations are, moreover, symmetric: the order of the numbers does not change the result.

Computation by means of the prime factorization

By the fundamental theorem of arithmetic, every natural number greater than $1$ factors uniquely into primes. It is convenient to write $a$ and $b$ with the same primes $p_1, \ldots, p_k$, allowing zero exponents for the primes that appear in only one of them:

A natural number $d$ divides $a$ exactly when no primes other than those of $a$ appear in its factorization, each with an exponent not greater than the one it has in $a$. It follows that $d$ divides both $a$ and $b$ when the exponent of each prime in $d$ exceeds neither of the two exponents; the greatest common divisor is therefore obtained by taking, for each prime, the smaller of the two exponents. Likewise, $m$ is a common multiple when the exponent of each prime in $m$ reaches both, and the least common multiple takes, for each prime, the larger of the two exponents. For example:

The method is clear, but it depends on knowing how to factor, and factoring large numbers is very costly: no fast procedure for doing so is known. The algorithm of the next section computes the greatest common divisor without factoring, with divisions alone.