On a Property of the Least Common Multiple of Two Integers
Dan Kalman

The Least Common Multiple of two integers, is the least positive integer that is divisible by both integers. This is connected by a simple formula with the greatest common divisor of the two integers, a familiar topic from modern algebra and number theory. The purpose of this paper is to present a proof for the connection between least common multiple and greatest common divisor. Along the way we will see several other properties of the least common multiple, as well as a number of examples.

Throughout the discussion, we will consider only positive integers, the set of which is expressed as N. We also assume the notation and properties of the greatest common divisor presented in Hungerford [1]. In particular, if a and b are positive integers, we denote the greatest common divisor of a and b by (a,b). To begin the discussion of least common multiple, we present the following definition.

Definition 1. If a and b are positive integers, the least common multiple of a and b, denoted [a,b], is the least positive element of the set {z ( N : a | z and b | z }.

It should be remarked that for any positive integers a and b, their product ab is always divisible by both a and b, showing that the set of positive common multiples is not empty. Thus, [a,b] is always defined.

As an example, [4,6] = 12. To see this, observe that the multiples of 4 and 6, respectively, can be listed as follows:

4N = {4, 8, 12, 16, 20, 24, …} 6N = {6, 12, 18, 24, 30, 36 …}.

We see that 12 is the least entry that is common to both sets. Indeed, 4|12 and 6|12 so 12 is definitely a common multiple. On the other hand, since the only positive multiple of 6 less than 12 is 6 itself, and since 4 is not a divisor of 6, we see that no other common multiple can be less than 12. This shows that 12 is the least common multiple.

In this example, we notice that 12 is not only less than or equal to every other common multiple of 4 and 6, it is also a divisor of all those multiples. We state this as a theorem.

Theorem 2. Let a and b be positive integers, and let c = [a,b]. Also, let C be the common multiples of a and b. That is, C = {z ( N : a | z and b | z }. Then C = cN.

Proof. Because c is a common multiple of a and b, we know both a and b are divisors of c. This shows they are also divisors of cn for any n in N. Put another way, every such cn is a common multiple of a and b, and so is an element of C. Therefore, we have established that cN ( C.

For the opposite inclusion, let d(C, so that d is an arbitrary common multiple of a and b. We must show that d ( cN. To that end, apply the division algorithm, expressing

d = cq + r (1)

where q and r are non-negative integers, and 0 ≤ r < c. Now both d and c are multiples of a, so we can write c = as and d = at for some positive integers s and t. Substitution in equation (1) then leads to at = asq + r. Rearranging this last equation then produces r = a (t - sq), demonstrating that a divides r. Exactly the same argument with b in place of a shows that b divides r as well. Thus, r is a common multiple of a and b. Now since r < d, which is the least positive common multiple, we see that r cannot be positive. Thus, we conclude r = 0, and by equation (1), d = cq. This shows that d is an element of cN. In summary, we have shown that d ( C implies d ( cN, which proves that C ( cN. This completes the proof that C = cN. ■

The preceding theorem shows that the LCM of two integers is a divisor of every other common multiple of the integers. This is very similar to the situation with the greatest common divisor, which is also a divisor of every other common divisor. Next we show how factorization can be used to simplify the computation of LCM. This is provided by the following two lemmas.

Lemma 3. If r and s are positive integers, and if (r,s) = 1, then [r,s] = rs.

Proof. Let c = [r,s] . Since rs is a common multiple of r and s, and c is the least common multiple, we must have c ≤ rs. Now we know c is a multiple of r, so we can write c = rt for some positive integer t. By substitution, we observe that rt ≤ rs, and hence, t ≤ s.

Next, using the fact that c is also a multiple of s, we obtain s | c = rt, so s| rt. But recall that s and r are relatively prime. Therefore, by Theorem 1.5 in reference [1], we conclude that s| t. Since we already know that t ≤ s , it must follow that s = t. Finally, using the equation c=rt, we obtain c = rs. That is what we wanted to show. ■

As an example, observe that [2,3] = 6 = 2(3. On the other hand, in the earlier example, we saw [4,6]= 12 ( 4(6. This is consistent with the lemma because 4 and 6 are not relatively prime, sharing a common factor of 2. Indeed, in this example, we see that [4,6]= 4(6/(4,6). As we will see below, this relationship between the least common multiple and the greatest common divisor holds in general. But first, let us proceed to the second lemma.

Lemma 4. If a, b, and t are positive integers, then [at,bt] = t [a,b].

Proof. Let c = [a,b] and let d = [at,bt]. Then a | c and b | c, so at | ct and bt | ct. This shows that ct is a common multiple of at and bt, and so ct ( d = [at,bt]. On the other hand, we know at | d and bt | d, so we may write d = atx = bty for some positive integers x and y. But then a | (d/t) and b | (d/t), so d/t is a common multiple of a and b. This implies d/t ( c, the least common multiple. Multiplying by t yields d ( ct. Combined with the earlier inequality, this shows d = ct. That is, we have derived [at,bt] = t [a,b], as desired. ■

To illustrate this example, consider [10,35]. Factoring these two integers, we see that [10,35] = [2(5,7(5] = 5 [2,7]. Proceeding further, since (2,7) = 1, Lemma 3 shows [2,7] = 14. In this way we easily find [10,35] = 5(14 = 70. This approach to calculating the least common multiple is generally valid, and provides a proof for our main result.

Theorem 5. If a and b are positive integers, then (a,b)[a,b] = ab.

Proof. Let t = (a,b). Thus we may write a = rt and b = st for some positive integers r and s. Moreover, as stated in problem 16 in section 1.2 of reference [1], (r,s) = 1. Now according to Lemma 4, we can compute [a,b] = [rt,st] = t [r,s]. Next, by Lemma 3, we see that [a,b] = trs. Now multiply both sides of this equation by t. That gives t[a,b] = trts = ab. But t = (a,b). Therefore, we have shown that
(a,b)[a,b] = ab. This completes the proof. ■

Notice that the conclusion of Theorem 5 can be rewritten in the form

[a,b] = ab/(a,b).

We can apply this to the earlier example with a = 10 and b = 35. We obtain [10,35] = 10(35/ (10,35) = 350/5 = 70.

REFERENCES

[1.] Thomas Hungerford, Abstract Algebra an Introduction, 2nd Ed., Brooks-Cole, www.brookscole.com, 1997.