(250.) To find, then, the greatest common divisor of two quantities, we divide the greater by the less; and the remainder, which is necessarily less than either of the given quantities, is by the last Article divisible by the greatest common divisor. Dividing the preceding divisor by the last remainder, a still smaller remainder will be found, which is divisible by the greatest common divisor; and by continuing this process with each remainder and the preceding divisor, quantities smaller and smaller are found, which are all divisible by the greatest common divisor, until at length the greatest common divisor must be obtained. Hence the following RULE. Divide the greater quantity by the less, and the preceding divisor by the last remainder, till nothing remains; the last divisor will be the greatest common divisor. When the remainders decrease to unity, the given quantities have no common divisor greater than unity, and are said to be incommensurable, or prime to each other. EXAMPLES. Ex. 1. What is the greatest common divisor of 372 and 246? 3721246 246 126, first Remainder. 126 1 126 120, second Remainder. 120 1 120 6, third Remainder. 120 20 Here we have continued the operation of division until we obtain 0 for a remainder; the last divisor (6) is the greatest common divisor. Thus, 246 and 372 being each divided by 6, give 41 and 62, and these quotients are prime with respect to each other; that is, have no common divisor greater than unity. Ex. 2 What is the greatest common divisor of 336 and 720? Ex. 3. What is the greatest common divisor of 918 and 522? Ans. 48. Ans. 18. (251.) In applying this rule to polynomials, some modification may become necessary. It may happen that the first term of the dividend is not divisible by the first term of the divisor. This may arise from the presence of a factor in the divisor which is not found in the dividend, and may therefore be suppressed. For, since the greatest common divisor of two quantities is only the product of their common factors, it can not be affected by a factor of the one quantity which is not found in the other. We may therefore suppress in the first polynomial all the factors common to each of its terms. We do the same with the second polynomial, and if the suppressed factors have a common divisor, we reserve it as forming part of the common divisor sought. But if, after this reduction, the first term of the dividend, when arranged according to the powers of some letter, is not divisible by the first term of the arranged divisor, we may multiply the dividend by any monomial factor which will render its first term divisible by the first term of the divisor. This will not affect the greatest common divisor, because we introduce into the dividend a factor which belongs only to the first term of the divisor; for by supposition, all the factors common to each of its terms have been suppressed. Whence x2+1 is the greatest common divisor. To verify this result, divide x+x by x2+1, and we obtain x'; divide x-1 by x+1, and we obtain x2-1. Ex. 2. Required the greatest common divisor of x3-b'x and x2+2bx+b2. Suppressing the factor x in the first polynomial, we proceed Whence x+b is the greatest common divisor. Ex. 3. Required the greatest common divisor of 4a3-2a2-3a+1 and 3a2-2a-1. Ex. 4. Find the greatest common divisor of x-a' and '—a3. Ex. 5. Find the greatest common divisor of a'-3ab+2b' and a-ab-2b2. Ex. 6. Find the greatest common divisor of a-x and a3—a2x-ax2+x3. Ans. a-1. Ans. x-a Ans. a-2b. Ans. a2-x3 Ex. 7. Find the greatest common divisor of Ans. a-b Ex. 8. Find the greatest common divisor of 1 CONTINUED FRACTIONS. (252.) From the operation on page 204, we see that the which is called a continued fraction. A continued fraction is one whose numerator is unity, and its denominator an integer plus a fraction whose numerator is likewise unity, and its denominator an integer plus a fraction, and so on. The general form of a continued fraction is 1 a+1 b+1 c+1 d+1 e+1, &c. (253.) Any fraction may be transformed into a continued fraction by the method of finding the greatest common divisor of the numerator and denominator. |