IV. Multiply all the combinations now obtained by another factor in continued multiplication, and thus proceed till all the different factors have been used. All the combinations obtained will be the exact divisors sought. EXAMPLES FOR PRACTICE. 1. What are all the exact divisors of 120 ? Ans. 1, 2, 3, 4, 5, 6, 8, 10, 12, 15, 20, 24, 30, 40, 60, 120. 2. Find all the exact divisors of 81. Ans. 1, 2, 3, 4, 6, 7, 12, 14, 21, 28, 42, 84. 3. Find all the exact divisors of 100. Ans. 1, 2, 4, 5, 10, 20, 25, 50, 100. 4. Find all the exact divisors of 420. 1, 2, 3, 4, 5, 6, 7, 10, 12, 14, 15, 20, 21, 28, Ans. 30, 35, 42, 60, 70, 84, 105, 140, 210, 420. 5. Find all the exact divisors of 1050. 1, 2, 3, 5, 6, 7, 10, 14, 15, 21, 25, 30, 35, 42, 50, 70, Ans. 75, 105, 150, 175, 210, 350, 525, 1050. GREATEST COMMON DIVISOR. 146. A Common Divisor of two or more numbers is a number that will exactly divide each of them. 147. The Greatest Common Divisor of two or more numbers is the greatest number that will exactly divide each of them. 148. Numbers Prime to each other are such as have no common divisor. NOTE.—A common divisor is sometimes called a Common Measure; and the greatest common divisor, the Greatest Common Measure. CASE I. 149. When the numbers can be readily factored. It is evident that if several numbers have a common divisor, they may all be divided by any component factor of this divisor, and the resulting quotients by another component factor, and so on, till all the component factors have been used. 1. 5.. 1. What is the greatest common divisor of 28, 140, and 420 ? OPERATION. ANALYSIS. We readily see that 7 728 .. 140 . . 420 will exactly divide each of the given 4.. 20.. 60 numbers; and then, 4 wili exactly 4 divide each of the resulting quotients. 15 Hence, each of the given numbers 4x7= 28, Ans. can be exactly divided by 7 times 4; and these numbers must be component factors of the greatest common divisor. Now, if there were any other component factor of the greatest common divisor, the quotients, 1, 5 and 15, would be divisible by it. But these quotients are prime to each other; therefore, 7 and 4 are all the component factors of the greatest common divisor sought. From this analysis we derive the following RULE. I. Write the numbers in a line, with a vertical line at the left, and divide by any factor common to all the numbers. II. Divide the quotients in like manner, and continue the division till a set of quotients is obtained that are prime to each other. III. Multiply all the divisors together, and the product will be the greatest common divisor sought. EXAMPLES FOR PRACTICE. 1. What is the greatest common divisor of 40, 75, and 100? Ans. 5. 2. What is the greatest common divisor of 18, 30, 36, 42, and 54 ? 3. What is the greatest common divisor of 42, 63, 126, and 189 ? Ans. 21. 4. What is the greatest common divisor of 135, 225, 270, and 315 ? Ans. 45. 5. What is the greatest common divisor of 84, 126, 210, 252, 294, and 462 ? 6. What is the greatest common divisor of 216, 360, 432, 648, and 936 ? Ans. 72. 7. What is the greatest common divisor of 102, 153, and 255 ? Ans. 51. 8. What is the greatest common divisor of 756, and 1575? 9. What is the greatest common divisor of 182, 364, and 455 ? 10. What is the greatest common divisor of 2520, and 3240 ? Ans. 360. 11. What is the greatest common divisor of 1428, and 1092 ? 12. What is the greatest common divisor of 1008, and 1036 ? Ans. 28. CASE II. OPERATION. 150. When the numbers cannot be readily factored. The analysis of the method in this case depends upon the following properties of divisors. I. An exact divisor divides any number of times its dividend. II. A common divisor of two numbers is an exact divisor of their sum. III. A common divisor of two numbers is an exact divisor of their difference. NOTE.-The last two properties are essentially the same as 102, II, III. 1. What is the greatest common divisor of 527, and 1207 ?, ANALYSIS. We will first describe the pro1207 cess, and then examine the reasons for the 527 2 1054 several steps in the operation, Drawing two vertical lines, we place the greater number 459 3 153 on the right, and the less number on the left, 68 2 136 one line lower down. We then divide 1207, the greater number, by 527, the less, and 68 4 17 virite the quotient, 2, between the verticals, the product, 1054, opposite the less number and under the greater, and the remainder, 153, below. We next divide 527 by this remainder, writing the quotient, 3, between the verticals, the product, 459, on the left, and the remainder, 68, below. We again divide the last divisor, 153, by 68, and obtain 2 for a quotient, 136 for a product, and 17 for a remainder, all of which we write in the same order as in the former steps. Finally, dividing the last divisor, 68, by the last remainder, 17, we have no remainder, and 17, the last divisor, is the greatest common divisor of the given numbers. Now, observing that the dividend is always the sum of the product and remainder, and that the remainder is always the difference of the OPERATION. A 1207 2 3 2 4 dividend and product, we first trace the work in the reverse order, as indicated by the arrow line in the diagram below. 17 divides 68, as proved by the last division; it will also divide 2 times 68, or 136, (I). Now, as 527 1054 17 divides both itself and 136, it will divide 153, their sum, (II). It will also divide 3 times 153, or 459 153 459, (I); and since it is a com mon divisor of 459 and 68, it 68 136 must divide their sum, 527, which is one of the given numbers. It 68 17 will also divide 2 times 527, or 1054, (I); and since it is a common divisor of 1054 and 153, it must divide their sum, 1207, the greater number, (II). Hence, 17 is a common divisor of the given numbers. Again, tracing the work in the direct order, as indicated in the fol lowing diagram, we know that 1207 the greatest common divisor, whatever it be, must divide 2 times 527, or 1054, (I). And since it 527 1054 will divide both 1054 and 1207, it must divide their difference, 459 153 153, (III). It will also divide 3 times 153, or 459, (I); and as it 68 136 will divide both 459 and 527, it must divide their difference, 68, 17 (III). It will also divide 2 times 68, or 136, (I); and as it will divide both 136 and 153, it must divide their difference, 17, (III); hence, it cannot be greater than 17. Thus we have shown, 2d. That their greatest common divisor, whatever it be, cannot be greater than 17. Hence it must be 17. From this example and analysis, we derive the following RULE. I. Draw two verticals, and write the two numbers, one on each side, the greater number one line above the less. 2 3 2 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 will be the greatest common divisor sought. IV. If more than two numbers be given, first find the greatest common divisor of two of them, and then of this divisor and one of the remaining numbers, and so on to the last; the last common divisor found will be the greatest common divisor required. Notes.--1. When more than two numbers are given, it is better to begin with 2. If at any point in the operation a prime number occur as a remainder, it must be a common divisor, or the given numbers have no common divisor. the least two. EXAMPLES FOR PRACTICE. 1. What is the greatest common divisor of 18607 and 417979? 2. What is the greatest common divisor of 10661 and 123037 |