GREATEST COMMON DIVISOR. PREPARATORY STEPS. 189. STEP I.-Find by inspection an exact divisor for each of the following sets of numbers: STEP II. Find by inspection the greatest number that is an exact divisor of each of the following pairs of numbers: Find in the same manner the greatest exact divisor of the following: 7. 14, 35. 8. 25, 45. 9. 36, 96. 10. 72, 108. 11. 84, 132. 12. 88, 121. STEP III-Express the numbers in each of the foregoing examples in terms of their greatest exact divisor. Thus, the greatest exact divisor of 16 and 40 is 8, hence 16 may be expressed as 2 eights, and 40 as 5 eights. DEFINITIONS. 190. A Common Divisor is a number that is an exact divisor of each of two or more numbers. Thus, 5 is a divisor of 10, 15, and 20. 191. The Greatest Common Divisor is the greatest number that is an exact divisor of each of two or more numbers. Thus, 3 is the greatest exact divisor of each of the numbers 6 and 15. Hence 3 is their greatest common divisor. 192. Numbers are prime to each other when they have no common divisor besides 1; thus, 8, 9, 25. METHOD BY FACTORING. PREPARATORY PROPOSITION. 193. Illustrate the following proposition by examples. The greatest common divisor is the product of the prime factors that are common to all the given numbers; thus, 7 and 11 being prime to each other, 6 must be the greatest common divisor of 7 sixes and 11 sixes. But 6 is the product of 2 and 3, the common prime factors; hence the greatest common divisor of 42 and 64 is the product of their common prime factors. ILLUSTRATION OF PROCESS. 194. PROB. I.-To find the Greatest Common Divisor of two or more numbers by factoring. Find the greatest common divisor of 98, 70, and 154. 2x7= greatest common divisor. EXPLANATION.-1. We resolve each of the numbers into their prime factors, as shown in (1) or (2). 2. We observe that 2 and 7 are the only prime factors common to all the numbers. Hence the product of 2 and 7, or 14, according to (193). is the greatest common divisor of 98, 70, and 154. The greatest common divisor of any two or more numbers is found in the same manner; hence the following 195. RULE.—Resolve each number into its prime factors, and find the product of the prime factors that are common to all the numbers. PREPARATORY PROPOSITIONS. 197. Let the two following propositions be carefully studied and illustrated by other examples, before attempting to find the greatest common divisor by this method. PROP. I.-The greatest common divisor of two numbers is the greatest common divisor of the smaller number and their difference. Thus, 3 is the greatest common divisor of 15 and 27. Hence 155 threes and 9 threes and 279 threes; 5 threes 4 threes. But 9 and 5 are prime to each other; hence, 4 and 5 must be prime to each other, for if not, their common divisor will divide their sum, according to (169-II), and be a common divisor of 9 and 5. Therefore, 3 is the greatest common divisor of 5 threes and 4 threes, or of 15 and 12. Hence, the greatest common divisor of two numbers is the greatest common divisor of the smaller number and their difference. PROP. II.-The greatest common divisor of two numbers is the greatest common divisor of the smaller number and the remainder after the division of the greater by the less. This proposition may be illustrated thus: 22 6=16 16 6 = 10 10 6 4 1. Subtract 6 from 22, then from the difference, 16, etc., until a remainder less than 6 is obtained. 2. Observe that the number of times 6 has been subtracted is the quotient of 22 divided by 6, and hence that the remainder, 4, is the remainder after the division of 22 by 6. 3. According to Prop. I, the greatest common divisor of 22 and 6 is the greatest common divisor of their difference, 16, and 6. It is also, according to the same Proposition, the greatest common divisor of 10 and 6, and of 4 and 6. But 4 is the remainder after division and 6 the smaller number. Hence the greatest common divisor of 22 and 6 is the greatest common divisor of the smaller number and the remainder after division. 198. PROB. II.—To find the Greatest Common Divisor of two or more numbers by continued division. Find the greatest common divisor of 28 and 176. 28)176(6 8) 28 (3 4)8(2 EXPLANATION.-1. We divide 176 by 28 and find 8 for a remainder; then we divide 28 by 8, and find 4 for a remainder; then we divide 8 by 4, and find 0 for a remainder. 2. According to Prop. II, the greatest common divisor of 28 and 176 is the same as the greatest common divisor of 28 and 8, also of 8 and 4. But 4 is the greatest common divisor of 8 and 4. Hence 4 is the greatest common divisor of 28 and 176. The greatest common divisor of any two numbers is found in the same manner; hence the following 199. RULE.-Divide the greater number by the less, then the less number by the remainder, then the last divisor by the last remainder, and so on until nothing remains. The last divisor is the greatest common divisor sought. To find the greatest common divisor of three or more numbers by this method we have the following 200. RULE. Find the greatest common divisor of two of the numbers, then of the common divisor thus found and a third number, and so on with a fourth, fifth, etc., number. ARITHMETICAL DRILL TABLE NO. 3. 201. Table for Oral Exercises in Greatest Common Divisor, and for Oral and Written Exercises in Least Common Multiple. |