165. To find all the prime factors of a composite number.

1. What are the prime factors of 2772 ?

OPERATION.

ANALYSIS. Since the given number is even, di 2)2772 vide it by 2, the least prime factor, and the result also by 2, which gives an odd number for a quotient.

2)1386 3)693 3)231 7)77

11

Next divide by the prime factors 3, 3, and 7, successively, obtaining for the last quotient 11, which not being divisible, is a prime factor of the given number. Hence the divisors 2, 2, 3, 3, 7, and the last quotient 11, are all the prime factors, or divisors, of 2772, and may be written 22, 32, 7, 11.

RULE.-Divide the given number by any prime factor of it, and the resulting quotient by another, and so continu the division until the quotient is a prime number. The several divisors and the last quotient are the prime factors.

PROOF.-The product of all the prime factors is equal to the given number. (PRIN. 4.)

Of 20.

166. 1. Name two exact divisors of 12. Of 15. 2. Name three exact divisors of 24. Of 48. Of 72. 3. What number is an exact divisor of 27 and of 56? 4. What are the prime divisors of 15? 55? 49? 77! 5. What are the composite divisors of 72? 84? 120? 6. What prime divisor is common to 28, 35, and 42 ? 7. Name a common measure of 22, 44, and 66. 8. Name the greatest common measure of 16, 32, and 64. 9. Of what three numbers is 12 a common divisor? 10. What two numbers will exactly divide 15 and 30? Their sum and difference?

11. What is the smallest exact divisor of the sum and difference of 10 and 15? Of 21 and 56?

12. What is the greatest exact divisor of the sum and difference of 16 and 24? Of 18 and 45 ?

13. Find the greatest common measure of 14, 42, and 56. 14. Find the greatest common divisor of 27, 36, and 45.

DEFINITIONS AND PRINCIPLES.

167. A Common Divisor of two or more numbers is a common factor of each of them.

168. The Greatest Common Divisor of two or more numbers is the greatest common factor, and is the product of all the common prime factors.

169. PRINCIPLES.-1. The only exact divisors of a number are its prime factors, or the product of two or more of them.

2. An exact divisor divides any number of times its dividend.

3. A common divisor of two or more numbers will divide their sum, and also the difference of any two of them.

4. The greatest common divisor of two or more numbers is the product of all their common prime factors.

170. When the numbers can be readily factored. 1. What is the greatest common divisor of 42, 63, and 126?

3, and 6 would be exactly divisible by them.

Find the greatest common divisor

2. Of 42 and 112.

3. Of 96 and 544.

4. Of 40, 75, and 100.

5. Of 72, 126, and 216.

RULE.-Separate the numbers into their prime factors and find the product of all that are common. Or,

I. Write the numbers in a line, and divide by any prime factor common to all the numbers.

II. Divide the quotients in like manner, and so continue the division till all the quotients are prime to each other. III. The product of all the divisors will be the greatest common divisor. (PRIN. 4.)

What is the greatest common divisor

6. Of 144 and 720?

7. Of 308 and 506 ?

8. Of 126, 210, and 252?

9. Of 72, 96, 120, and 384?

171. When the numbers cannot be readily factored. 1. Find the greatest common divisor of 527 and 1207.

OPERATION.

1207 527 2 1054 459 3 153

682 684

136

17

Di.

ANALYSIS.-Draw two vertical lines, and place the greater number on the right, and the less on the left, one line lower down. vide 1207 by 527, and write the quotient 2 between the vertical lines, the product, 1054, under the greater number, and the remainder 153, below.

Next, divide 527 by this remainder 153, writing the quotient 3 between the verticals, the product 459, on the left, and the remainder 68, helow.

Again, divide the last divisor 153, by 68, and write the product, and remainder in the same order as before.

Finally, dividing the last divisor 68, by the last remainder 17, there is no remainder. Hence 17, the last divisor, is the greatest common divisor of 537 and 1207.

PROOF.-Now, observing that the dividend is always the sum of the product and remainder, and that the remainder is always the difference of the dividend and product, trace the work in the reverse order, as indicated by the arrow line in the diagram below.

A 1207

17 divides 68, as proved by the last division; it will also divide 2 times 68, or 136 (PRIN. 2). Since 17 divides both itself and 136, it will 1054 divide 153, their sum (PRIN. 3). It will also divide 3 times 153, or 459 153 (PRIN. 2); and, since it is a common divisor of 459 and 68, it must divide their sum, 527, which is one of the given numbers. It will also divide 2 times 527, or 1054 (PRIN. 2); and, since it divides 1054 and 153, it must

136

17

divide their sum, 1207, the greater number (PRIN. 3). Hence, 17

is a common divisor of the given numbers.

Again, tracing the work in the direct order, as indicated in the

2

527

459

2

68

1207

1054

153

136

17

following diagram, the greatest common divisor, whatever it is, must divide 2 times 527, or 1054 (PRIN. 2). And since it will divide both 1054 and 1207, it must divide their difference, 153 (PRIN. 3). It will also divide 3 times 153, or 459 (PRIN. 2); and as it will divide both 459 and 527, it must divide their difference, 68 (PRIN. 3). It will also divide 2 times 68, or 136 (PRIN. 2); and as it will divide both 136 and 153, it

must divide their difference, 17 (PRIN. 3); hence, it cannot be greater than 17.

Thus, it has been shown,

1st. That 17 is a common divisor of the given numbers.

2d. That their greatest common divisor, whatever it be, cannot be greater than 17. Hence it must be 17.

In like manner, find the greatest common divisor

2. Of 316 and 664.

3. Of 679 and 1869. 4. Of 1080 and 189. 5. Of 2192 and 458.

6. Of 825 and 1372.

7. Of 2041 and 8476. 8. Of 7241 and 10907. 9. Of 2373 and 6667.

RULE.-I. Draw two vertical lines, and write the two numbers, one on each side, the greater number one line above the less.

II. Divide the greater number by the less, writing the quotient between the verticals, the product under the dividend, and the remainder below.

III. Divide the less number by the remainder, the last divisor by the last remainder, and so on, till nothing remains. The last divisor is the greatest common divisor.