## Proposition 34

 To find the least number which two given numbers measure. Let A and B be the two given numbers. It is required to find the least number which they measure. Now either A and B are relatively prime or they are not. First, let A and B be relatively prime. Multiply A by B to make C. Then B multiplied by A makes C. Therefore A and B measure C. I say next that it is also the least number they measure. If not, then A and B measure some number D less than C Let there be as many units in E as the times that A measures D, and as many units in F as the times that B measures D. Then A multiplied by E makes D, and B multiplied by F makes D. Therefore the product of A and E equals the product of B and F. Therefore A is to B as F is to E. VII.Def.15 VII.19 But A and B are relatively prime, primes are also least, and the least measure the numbers which have the same ratio the same number of times, the greater the greater and the less the less, therefore B measures E as the consequent the consequent. VII.21 VII.20 And, since A multiplied by B and by E makes C and D, therefore B is to E as C is to D. But B measures E, therefore C also measures D, the greater the less, which is impossible. VII.17 Therefore A and B do not measure any number less than C. Therefore C is the least that is measured by A and B. Next, let A and B not be relatively prime. Take F and E, the least numbers of those which have the same ratio with A and B. Therefore the product of A and E equals the product of B and F. VII.33 VII.19 Multiply A by E to make C. Then B multiplied by F makes C. Therefore A and B measure C. I say next that it is also the least number that they measure. If not, then A and B measure some number D less than C. Let there be as many units in G as the times that A measures D, and as many units in H as the times that B measures D. Then A multiplied by G makes D, and B multiplied by H makes D. Therefore the product of A and G equals the product of B and H. Therefore A is to B as H is to G. VII.19 But A is to B as F is to E. Therefore F is to E as H is to G. (V.11) But F and E are least, and the least measure the numbers which have the same ratio the same number of times, the greater the greater and the less the less, therefore E measures G. VII.20 And, since A multiplied by E and by G makes C and D, therefore E is to G as C is to D. VII.17 But E measures G, therefore C also measures D, the greater the less, which is impossible. Therefore A and B do not measure any number less than C. Therefore C is the least that is measured by A and B. Q.E.D.
The least common multiple of two numbers a and b is the smallest number that they both divide. It is denoted LCM(a, b). This proposition construct it as the product divided by the greatest common divisor:

LCM(a, b) = ab/LCM(a, b).

#### Summary of the proof

Let a and b be the two numbers. There are two cases depending on whether they are relatively prime or not.

Case 1. Suppose a and b are relatively prime. An indirect proof shows that their least common multiple is their product ab. If not, then there is a smaller number d which both a and b divide. Since a:b = (d/b):(d/a), and a:b is in lowest terms (since a and b are relatively prime), therefore b divides d/a. Also, b:(d/a) = ab:d, so ab divides d, but d is smaller than ab, a contradiction. Thus, when a and b are relatively prime, their least common multiple is their product.

Case 2. Suppose a and b are not relatively prime. Reduce the ratio a:b to its lowest terms f:e using the previous proposition VII.33. Then ae = bf. Let c denote this product. (Note that f = a/GCD(a, b), and e = b/GCD(a, b), so c = ab/GCD(a, b).) Both a and b divide c, therefore c is a common multiple of a and b. Suppose that it's not the least common multiple. Then there is a smaller number d which both a and b divide. Now

f:e = a:b = (d/b):(d/a),

and f:e is in lowest terms, therfore e divides d/a. But e:(d/a) = ae:d, therefore ae also divides d. But c = ae, and d is less than c, a contradiction. Thus, LCM(a, b) = ab/LCM(a, b).

#### Use of this proposition

This proposition is used in VII.36 and VIII.4.

Next proposition: VII.35

Previous: VII.33

 Select from Book VII Book VII intro VII.Def.1-2 VII.Def.3-5 VII.Def.6-10 VII.Def.11-14 VII.Def.15-19 VII.Def.20 VII.Def.21 VII.Def.22 VII.1 VII.2 VII.3 VII.4 VII.5 VII.6 VII.7 VII.8 VII.9 VII.10 VII.11 VII.12 VII.13 VII.14 VII.15 VII.16 VII.17 VII.18 VII.19 VII.20 VII.21 VII.22 VII.23 VII.24 VII.25 VII.26 VII.27 VII.28 VII.29 VII.30 VII.31 VII.32 VII.33 VII.34 VII.35 VII.36 VII.37 VII.38 VII.39 Select book Book I Book II Book III Book IV Book V Book VI Book VII Book VIII Book IX Book X Book XI Book XII Book XIII Select topic Introduction Table of Contents Geometry applet About the text Euclid Web references A quick trip