ART. 116. To find the greatest common divisor of two numbers.

FIRST METHOD.

OPERATION.

1. Find the greatest common divisor of 70 and 154. SOLUTION.-Resolving the numbers into their prime factors, by inspection or by the rule (Art. 113), shows that 70= 2X5X7, and 1542 X 7 X 11.

Since 2 and 7 are factors of each of the numbers, both may be exactly divided by 2 or 7, or by their product: 2X7=14.

70=2X5 X 7 154 2X7X11

=

Ans. 2 X 7=14

As 2 and 7 are the only prime factors common to the numbers, no number except 2, 7, and their product, 2 X 7=14, will exactly divide both of them: therefore, 2 X 7 = 14, is the G. C. D.

2. Find the G. C. D. of 6 and 10. 3. Of 30 and 42.

Ans. 2.

Ans. 2 X 3=6.

Rule I.-Resolve the given numbers into prime factors; the product of the factors which are common, will be the greatest common divisor.

REM. The greatest com. divisor of two numbers contains, as factors, all the other com. divisors of those numbers. Thus, 6, the greatest com. divisor of 30 and 42, contains, as factors, 2 and 3, the only remaining com. divisors of those numbers.

WHAT IS THE GREATEST COMMON DIVISOR

REVIEW.-115. REM. Can two numbers have more than one common divisor? 116. Find the G. C. D. of 30 and 42, by separating each into prime factors? What is Rule I?

116. REM. What factors does the G. C. D. of two numbers contain?

NOTE. When there are more than two numbers, resolve each into prime factors; then take the product of the common factors.

12.

WHAT IS THE GREATEST COMMON DIVISOR OF

30, 42, and G6?

13. 60, 90, and 150?

Ans. 2 X 3 = 6.

Ans. 2 X 3 X 5=30.

When the numbers arc large, it is better to adopt

ART. 117. THE SECOND METHOD.

This method depends on the following principles:

1ST PRIN. A divisor of a number, is a divisor of any multiple of that number; Art. 111, Prin. 1.

2D PRIN. A common divisor of Two numbers is a divisor of their SUM; Art. 111, Prin. 2.

3D PRIN. A common divisor of two numbers, is a divisor of their DIFFERENCE.

Since each of the numbers contains the com. divisor a certain number of times, their difference must contain it as many times as the larger contains it more times than the smaller.

Thus, 2, being a divisor of 14 and 8, must be a divisor of their difference; for, 14 is 7 twoɛ, and 8 is 4 twos, and their difference is 7 twos minus 4 twos. 3 twos.

Therefore, if a number be separated into two parts, any number which will exactly divide the given number and one of ́ its parts, will also exactly divide the other.

In this case, either of the parts is the difference between the given number and the other part.

4TH PRIN. The greatest common divisor of two numbers, is a divisor of their remainder after division. See Solu.

1. Find the G. C. D. of 16 and 44.

SOLUTION. As 16 is a divisor of itself, if it be a divisor of 44, it will

OPERATION.

16)44(2

32

12)16(1
12

4)12(3

the G. C. D. is a divisor of 16 and 44, by first Prin., it will be a

divisor of 16 X 2 = 32; hence, by 3d Prin., it must be a divisor of 44—32=12; that is, the G. C. D. of two numbers is also a divisor of their remainder after division.

Hence, the G. C. D. of 16 and 44 is also a com. divisor of 12 and 16, and it can not exceed 12. Since 12 is a divisor of itself, if it be a divisor of 16, it must be the G. C. D. sought.

By dividing 12 into 16, the remainder is 4; hence, 12 is not the G. C. D.; but, by Prin. 4th, the G. C. D. of 12 and 16 is a divisor of 4, their remainder after division; hence, the G. C. D. of 16 and 44 can not exceed 4, and must be a divisor of 4 and 12.

By dividing 12 by 4, there is no remainder; hence, 4 is a divisor of 12, and therefore, of 12×1+4=16, Prin. 2d. And,

Since 4 is a divisor of 12 and 16, it must be a divisor of 16X2+12=44; and since the G. C. D. can not exceed 4, and 4 is a divisor of 16 and 44, therefore, 4 is the G. C. D. sought.

2. What is the G. C. D. of 14 and 35? 3. What is the G. C. D. of 9 and 24?

-

Ans. 7.

Ans. 3.

Rule II. Divide the greater number by the less, and that divisor by the remainder, and so on, always dividing the last divisor by the last remainder, till nothing remains; the last divisor will be the greatest common divisor.

NOTE. To find the G. C. D. of more than two numbers, first find the G. C. D. of two of them, then of that com. divisor and one of the remaining numbers, and so on for all the numbers; the last com. divisor will be the G. C. D. of all the numbers.

REVIEW.-117. On what principles does the second method of finding the G. C. D. depend? Explain the third principle. Find the G. C. D. of 9 and 24, and explain the fourth principle. What is Rule II?

117. NOTE. How is the G. C. D. of more than two numbers found?

12. Find the G. C. D. of 2145 and 3471.

For additional problems, see Ray's Test Examples.

X. LEAST COMMON MULTIPLE.+ ART. 118. A multiple (dividend), of a number, is a number that can be divided by it without a remainder.

Thus, 12 is a multiple of 3, because 3 is contained in 12 an exact number of times, 4. Art. 110, Def. 10.

A common multiple (dividend), of two or more numbers, is a number that can be divided by each, without a remainder.

Thus, 24 is a common multiple of 3 and 4.

The least common multiple of two or more numbers, is the least number that can be divided by each without a remainder.

Thus, 12 is the least common multiple of 3 and 4.

REM.-1. As the Com. Mul. of two or more numbers contains each of them as a factor, it is a composite number.

2. As the continued product of two or more numbers is divisible by each of them, a Com. Mul. of two or more given numbers may always be found by taking their continued product; and,

Since any multiple of this product will be divisible by each of the given numbers, (Art. 111, 1st Prin:), an unlimited number of Com. Multiples may be found for any given numbers.

REVIEW.-118. What is a multiple of a number? Give an example. What is a common multiple of two or more numbers? What the least common multiple? REM. 1. Is a common multiple of two or more numbers, a prime or composite number? Why? 2. How may a Com. Mul. always be found? How many Com. Multiples may numbers have? Why?

ART. 119. To find the least common multiple of two or more numbers.

FIRST METHOD.

One number is divisible by another, when it contains all the prime factors of that number.

Thus, 30 is divisible by 6, because 302×3×5, and 6=2X3; the prime factors of 6, which are 2 and 3, being also factors of 30.

One number is not divisible by another, unless it contains all the prime factors of that other.

Thus, 10 is not divisible by 6, because 3, one of the prime factors of 6, is not a factor of 10.

Hence, a common multiple of two or more numbers must contain all the prime factors in those numbers; and, To be the least common multiple, (L. C. M.), it must not contain any prime factor not found in some one of the numbers. L. C. M. should be read, least common multiple.

1. What is the L. C. M. of 6 and 10?

SOLUTION.-By factoring, 6=2 × 3, and 10=2×5. A number composed of the factors 2, 3, and 5, will contain all the factors in each of the numbers

OPERATION.

6=2×3 10=2X5

6 and 10, and will contain no other 2 X3 X5=30 Ans. factor; therefore, cross out (cancel) the

factor 2, in one of the numbers; the product of the remaining factors, 2 X3 X5=30, will be the L. C. M. of 6 and 10.

2. What is the L. C. M. of 6, 8, and 12?

SOLUTION.-By factoring the numbers, the prime factor 2 occurs once in 6, three times in 8,

and twice in 12; hence it must occur three times, and only three

6=2×3

OPERATION.

8:

=

2×2×2

12=2X2X3

times, in the L. C. M.; therefore, 3 × 2 × 2 × 2=24 Ans.

after reserving it as a factor

three times, cancel it in the other numbers.

The prime factor 3 occurs once in 6 and once in 12; hence, it must occur once, and only once, in the L. C. M.

it once as a factor, cancel the other factor 3. then found by multiplying together the figures

After reserving The L. C. M. is not canceled,