ART. 114. Since any composite number is divisible not only by each of its prime factors, but also by the product of any two or more of them, (Art. 112, Prop. V.),

Therefore, to find the several divisors of a composite number, resolve it into its prime factors, and form from them as many different products as possible.

Thus, 30=2X3 X5, and its several divisors are 2, 3, 5, and 2X3, 2X5, and 3X5.

For additional problems, see Ray's Test Examples. ·

IX. GREATEST COMMON DIVISOR.

ART. 115. A divisor or measure of a number (Art. 110, Def. 8), is a number that will divide it without a remainder; thus, 2 is a divisor of 4; 3 of 6, &c.

A common divisor of two or more numbers, is a number that will divide each without a remainder; thus, 2 is a common divisor of 12 and 18.

The greatest common divisor of two or more numbers, is the greatest number that will divide each without a remainder; thus, 6 is the greatest common divisor of 12 and 18.

REM.-Two numbers may have several common divisors, but only one greatest common divisor.

G. C. D. should be read, greatest common divisor.

REVIEW.-114. How may the several divisors of a composite number be found? Why? 115. What is a divisor of a number? Give examples. 115. What is a common divisor of two or more numbers? Give example. What the greatest common divisor? Give example.

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= 2 X 5 X 7, and 154-2 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=2X5X 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 × 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.

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. WHAT IS THE GREATEST COMMON DIVISOR OF

When the numbers are 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 twos, 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 be the G. C. D. required, since no number can have a divisor greater than itself. But 16 is contained twice in 44, with a remainder 12; hence, 16 is not the G. C. D. Since

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 × 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 X 1+4=16, Prin. 2d. And,

Since 4 is a divisor of 12 and 16, it must be a divisor of 16 X2+12=44; and since the G. C. D. can not exceed 4, and 4 zs 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?