4. Of 3102 and 3666? 6. Of 4652 and 5544? 7. Of 924 and 1188? 5. Of 287 and 369 ? 8. What is the greatest common divisor of 72, 108, and The greatest common divisor of 72, 108, and 252, is the product of all the prime factors common to those numbers. From which we see that the only common factors are 22 and 32. Therefore, 32 X 22, or 36, is the greatest common divisor required. What is the greatest common divisor 110. A more brief Method. (a.) The following solution will usually be found much more brief than the preceding, inasmuch as it avoids the necessity of separating all the numbers into their factors. By it, we find the factors of any one of the numbers, and then see which of them are factors of all the other numbers. 1. What is the greatest common divisor of 756, 840, 1386, and 1596? Solution. We first find the factors of 840, because they can be the most readily found. 840 = 23 X 3 X 5 × 7, and we have now to find which of these factors, if any, are factors of all the other given numbers. It is obvious (104, I.) that 2 is a factor of all of them, and (104, II.) that it is contained but once as a factor in 1386. Hence, 2 will enter once only as a factor of the greatest common divisor. 5 is (104, I.) a factor of no other number. 3 being a factor (104, IV.) of all the numbers, is a factor of the greatest common divisor. By trial, 7 is found to be a factor of all the numbers, and hence of the greatest common divisor. Hence, the greatest common divisor is 2 X3 X 7. or 42. (b.) What is the greatest common divisor — 3. Of 1792, 936, 1224, and 1656? 111. Factoring not always necessary. (a.) We can frequently find the greatest common divisor of the given numbers without finding their prime factors. (b.) Thus, in finding the greatest common divisor of 24 and 42, we can see at a glance that 6 is a divisor of both; that 246 X 4, and 426 X 7; therefore, since 4 and 7 have no common factor, 6 must be the greatest common divisor required. (c.) Again. In finding the greatest common divisor of 693 and 819, we see at once that 9 will divide each. Now, comparing 77 and 91, we see that 7 will divide each. And as 7 and 11 are prime tor to the given numbers. divisor required. 77 = 7 X 11 91 = 7 X 13 to each other, there is no other common facHence, 7 X 9, or 63, is the greatest common (d.) Again. In finding the greatest common divisor of 36 and 72, we may see that 36 is a divisor of 72, and hence the greatest common divisor required. (e.) What is the greatest common divisor 1. Of 12 and 18? 2. Of 28 and 42? 3. Of 18 and 54? 4. Of 48 and 84? 5. Of 324 and 594? 6. Of 2025 and 2916? 112. Method by Addition and Subtraction. (a.) When the sum or the difference of any two of the given numbers is a small number, or one more easily divided into factors than any of the original numbers, the work may be abbreviated by applying the principles of 102, Proposition II. 1. What is the G. C. D.* of 8379 and 8484? Suggestion. The G. C. D. required must be a divisor of 8484 8379, which is 1053 X 5 X 7; and we have only to ascertain which of these factors, if any, are factors of one of the given numbers. 2. What is the G. C. D. of 89437, 95429, and 90537 ? Suggestion. — The G. C. D. required must be a divisor of the difference of any two of the given numbers, as of 89437 and 90537, which is 1100= 22 X 52 X 11; and we have only to ascertain which of these factors, if any, are factors of all the given numbers. 3. What is the G. C. D. of 56474 and 28526? Suggestion. The G. C. D. required must be a divisor of 56474 + 28526, which is 85000 23 X 54 X 17; and we have only to ascertain which of these factors, if any, are factors of one of the given numbers. 4. What is the G. C. D. of 3598, 5383, 6545, and 8617? Suggestion. — The G. C. D. required must be a divisor of the sum of any two of the given numbers, as of 5383, and 8617, which is 14000 = 24 × 53 × 7; and we have only to ascertain which of these factors, if any, are factors of all the given numbers. What is the greatest common divisor 5. Of 949 and 962? 6. Of 857637 and 857692 ? 7. Of 5489 and 7689 ? 8. Of 9709, 10906, and 10241 ? 9. Of 71227, 72553, 73840, and 75127? 10. Of 930069, 992673, and 1103673 ? 11. Of 12551 and 25949 ? 12. Of 169881 and 170119 ? 13. Of 16181 and 16324? 14. Of 180006, 293694, 468963, and 596862 ? *G. C. D. means greatest common divisor. 113. Demonstration of Method by Division. (a.) Proposition. The G. C. D. of any two numbers is the same as the G. C. D. of the smaller, and the remainder left after dividing the larger by the smaller. (b.) To prove this, let the letter a represent any number whatever, and the letter b represent any other number larger than a. Now, whatever numbers a and b represent, it is obvious that a is contained in b some number of times, which we will call c times, and that there may, or may not, be a remainder. If there is no remainder, a will be the G. C. D. of a and b. If, however, there is a remainder, we will call it d, and we have to prove that the G. C. D. of a and b is the same number as the G. C. D. of a and d. (c.) Representing the division by writing the letters as we should the numbers they represent, we have, Dividend. Divisor a) b (c = Quotient. ax c = d Product of divisor by quotient. Remainder. (d.) From the nature of division, it follows that (e.) Now, as any divisor of a must (102, Prop. I.) be a divisor of cxa, the G. C. D. sought must be a divisor of b and c × a, and hence (102, Prop. II.) of b - cx a, or d. Again. Any divisor of d and a must be a divisor of d and c X a, and hence (102, Prop. II.) of d + cxa, or b. It therefore follows that the G. C. D. sought is the same number as the G. C. D. of d and a, which, as a and b may represent any numbers whatever, establishes the proposition. 114. Application of the foregoing Principle. (a.) When the numbers of which the G. C. D. are required are such as cannot easily be divided into factors, or solved by the methods heretofore given, the principle just demonstrated may be advantageously applied, thus: (b.) Divide the greater of any two numbers by the less; then will the remainder obtained by this division and the smaller of the two numbers have the same G. C. D. as the uumbers themselves. (c) But as the remainder after any division must always be less than the divisor, we may divide the original divisor, 1. e., the smaller number, by this remainder. Now, if there be a remainder from this division, it follows, from the proposition, that the G. C. D. sought must be the G. C. D. of this remainder and the last divisor; and we may divide the last divisor by the last remainder. (d.) But as the remainders must constantly be decreasing, it follows that if we continue this process, we shall at last find a remainder which will exactly divide the preceding, and will therefore be the G. C. D., or we shall have a remainder of 1, in which case the numbers are prime to each other. 1. What is the G. C. D. of 4277 and 9737? 4277) 9737 (2 WRITTEN WORK. 1183) 4277 (3 728) 1183 (1 455) 728 (1 273) 455 (1 182) 273 (1 91 ) 182 (2 00 Explanation. Dividing the greater number by the less gives 1183 for a remainder. Therefore, the G. C. D. required is the G. C. D. of the smaller number, 4277 and 1183. Dividing 4277 by 1183 gives 728 for a remainder. Therefore, the G. C. D. required is the G. C. D. of 728 and 1183. Dividing 1183 by 728 gives 455 for a remainder. Therefore, the G. C. D. required is the G. C. D. of 728 and 1183. Proceeding in this way we find that the G. C. D. required is the same as the G. C. D. of 91 and 182, which is 91. (e.) The work can frequently be much shortened by observing that if any remainder contains a prime factor which is not a factor of the preceding divisor, the factor may be cast out without affecting the G. C. D. Thus 728, the second remainder in the above example, is obviously a multiple of 8, or 23, and 2 is not a factor of 1183, the preceding divi |