Common Multiples and the Least Common Multiple
The purpose of the applet below is to illustrate the notion of a multiple and the least common multiple of two integers. For an integer P, a multiple is any other integer divisible by P. Any integer P, has an infinite sequence of multiples. Speaking formally, multiples may be both negative and positive (and 0 of course.) For example, -10, -5, 0, 5, 10 are all multiples of 5 and of -5(!) as is any number in the form 5k, where k is any integer. However, most often we focus exclusively on positive integers and on their positive multiples.
The applet displays to the number line (x-axis) and two rows of red dots, above and below the line. Each of the rows is preceded by a hollow moveable dot. The hollow dots designate two integers, say, P and Q. At the beginning, P = 2 and Q = 3. The red dots show their multiples. 2, 4, 6, 8, ..., for P = 2, and 3, 6, 9, 12, ..., for Q = 3.
Some numbers appear in both rows and these are emphasized with blue dots on the line itself. These are the common multiples of P and Q, i.e., the numbers which are both a multiple of P and a multiple of Q. Since we are only concerned with positive integers, among all common multiples of two integers P and Q, there is the smallest. This is the leftmost of the blue dots. The number is called the Least Common Multiple of P and Q: lcm(P, Q) or lcm(P, Q).
| |
|
Both P and Q are factors of lcm(P, Q): P|lcm(P, Q) and also Q|lcm(P, Q). lcm(P, Q) is the least positive integer with this property. The least common multiple of two integers can be found with a factor tree or with the onion algorithm.
The applet may suggest the following
Theorem 1
For two integers P and Q,
lcm(P, Q) = Q if and only if P|Q.
Proof
P is a factor of lcm(P, Q), i.e. P|lcm(P, Q). If lcm(P, Q) = Q, then P|Q.
In the opposite direction, the fact that P|Q means that Q is a multiple of P; and, since Q is also a multiple of itself, Q is the common multiple of both P and Q. But Q is certainly the smallest positive multiple of itself, so that no common multiple of P and Q may be smaller than Q. Which shows that Q = lcm(P, Q), as claimed.
The applet helps make another observation: all common multiples of two integers P and Q are divisible by (or are multiples of) lcm(P, Q).
Theorem 2
For three integers P, Q, R,
if P|R and Q|R then lcm(P, Q)|R.
In other words if R is divisible by both P and Q, i.e., if R is a common multiple of P and Q, then it is divisible by lcm(P, Q).
Proof
Assume, S is another common multiple of P and Q, i.e. P|S and Q|S. For simplicity, let lcm(P, Q) = s. By definition, S > s. Let's try dividing S by s. We can find two integers p and s, p > 0 and s gt; r ≥ 0, such that S = sp + r. As we know, P|S and also P|lcm(P, Q) and the same holds for Q. From r = S - sp it follows that the right-hand side is divisible by both P and Q and, therefore is a common multiple of P and Q. If r ≠ 0, then, since r < s = lcm(P, Q), this would contradict the minimality of the lcm. We conclude that r = 0, implying that S = sp or, in other words, S is divisible by s = lcm(P, Q).
|Contact|
|Front page|
|Contents|
|Arithmetic|
|Activities|
|Store|
Copyright © 1996-2012 Alexander Bogomolny
|
