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).

If you are reading this, your browser is not set to run Java applets. Try IE11 or Safari and declare the site https:///www.cut-the-knot.org as trusted in the Java setup.

What if applet does not run?

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).

Related material Read more...
	Factoring with the Factor Tree
	GCD and LCM via Factor Tree
	GCD and LCM by Plain Factorization
	GCD(M, N) x LCM(M, N) = M x N
	Divisibility Criteria
	Euclid's Algorithm
	Algorithm for Computing the LCM
	Factors And Multiples
	Two Properties of Greatest Common Divisor
	Properties of GCD and LCM
	A Line in a Square Grid
	Number of Factors of an Integer
	Extension of Euclid's Game

|Contact| |Front page| |Contents| |Arithmetic| |Activities|

Copyright © 1996-2018 Alexander Bogomolny