Page images
PDF
EPUB

expressed by (a — pb)m, so that m is the greatest common divisor of am, bm, and (a-pb)m.

In the same way, if we divide bm by (a — pb)m, we may show that m is the greatest common divisor of the remainder of this division, bm and (a — pb)m and am; also, if we divide (a-pb)m by the last remainder, m will still be the greatest common divisor of the remainder and the corresponding divisor and dividend, and so on, so long as the division can be continued. Hence, in order to find the greatest common measure or divisor of two numbers or quantities of the same kind, we have the following

RULE.

Divide the greater number or quantity by the less, and the last divisor by the last remainder, and so on, till nothing remains, then the last divisor will be the greatest common measure or divisor required.

If the greatest common divisor equals 1, the numbers or quantities are prime to each other.

Also, if the successive divisors and remainders decrease indefinitely, so as ultimately to become less than any given quantities, without any remainder having actually become equal to 0, the quantities will have no common measure, and are said to be incommensurable.

(33.) If the greatest common divisor of three or more numbers or quantities is to be found, then we find (by the rule) the greatest common divisor of any two of them; and then we find (as before) the greatest common divisor of the common divisor just found, and of any one of the remaining numbers or quantities, and so on, for any common divisor found and any one of the remaining numbers or quantities, until all the numbers or quantities have been used; then will the last divisor found evidently be the greatest common divisor.

(34.) Remark.—In finding the greatest common divisor of two numbers or quantities, we may, if we please, omit any divisor of one of them, provided it is not a divisor of the other; for the divisor thus rejected evidently can not affect the common divisor; we may also multiply one of the numbers or quantities by any factor which is not a divisor of the

remaining number or quantity; for it is evident that the factor thus introduced can not affect the common divisor.

It may also be observed that the common divisor of any two numbers or quantities of the same kind is clearly a common divisor of their sum and difference. And analogous observations will have place when we have to find the greatest common divisor of more than two numbers or quantities.

EXAMPLES.

Ex. 1.-To find the greatest common divisor of 27 and 72. Dividing 72 by 27 we have the quotient 2, and remainder 18; then dividing the last divisor, 27, by the remainder, 18, we have the quotient 1 and remainder 9; and dividing the last divisor, 18, by the remainder, 9, we have the quotient 2 and remainder 0; consequently 9 is the greatest common divisor required.

Ex. 2.-To find the greatest common divisor of 11648 and and 12051.

Proceeding as in Ex. 1, we have the following process.

11648|12051|1

11648

403 1164828

806

3588

3224

364 403 1

364

393649
351

13|39|3

39

0

and 13 is the greatest common divisor required.

Ex. 3.-To find the greatest common divisor of 826 and 897. Dividing 897 by 826, we get the quotient 1 and remainder 71. Since 71 is a prime number, which does not exactly divide 826, it is unnecessary to continue the division any further; for the greatest divisor sought must be a divisor of 71 and 826, and since 71, and 1,are the only divisors of 71, and

as 71 does not divide 826, it follows that 1 is the greatest common divisor of 71 and 826. Hence, since the greatest divisor of 71 and 826 must be the greatest divisor of 826 and 897, 1 is their greatest common divisor, and they are of course prime to each other.

Ex. 4. To find the greatest common divisor of 301, 364, and 819.

Here, by proceeding as in the preceding examples, we find 91 to be the greatest common divisor of 364 and 819. And in the same way we get 7 for the greatest, common divisor of 91 and 301, and of course 7 is the greatest common divisor of the three given numbers. If we divide the given numbers by their greatest common divisor, 7, the quotients will be 43, 52, and 117, which clearly have no other common divisor than 1, and the numbers are said to be reduced to their lowest terms, with reference to their greatest common divisor.

Ex. 5. To find the greatest common divisor of 1 and 12, if possible.

14142135

We have heretofore shown that 2 has

and

10000000

[blocks in formation]

Hence, dividing 2 by 1, and the divisor 1 by the remainder, and so on, according to the rule, we shall have the following process.

11/21

1

√2-112

212-2

3-2 1/2 1/2-1/2

6-412

5 1/2-7 3-2 1/2 2

10 1/2-14

17-12 1/2 5 1/2-72
34-24 1/2

and so on, indefinitely; for it is manifest that we shall never arrive at a remainder which is 0.

It is easy to see that the remainders successively diminish, and that they will ultimately become indefinitely small. For the first remainder, 12-1 = 0.4142135 +, the second remainder 3 2 1/2 = 0.17157 +, the third remainder 5 √2 -7= 0.07106 +, and so on, the remainders continually diminishing without limit. Hence we conclude that 1 and √2 are incommensurable, or that they have no common divisor.

The same conclusion may be obtained in the following manner, viz., it is easy to see that the greatest common divisor of 1 and 2 must be the same as that of 1 and 2

- 1 and of 1 and 2+1. Hence, instead of dividing 1 by √2 −1, we may divide 12+ 1 by 1, and we shall have

12+12
2

√2-11

and instead of dividing 1 by 12-1, we may again divide √2 + 1 by 1, and so on, so that we have continually to divide 12+1 by 1. Hence, since the division never terminates, it follows that 1 and 2 are incommensurable.

This method coincides with the process given by Legendre in his Geometry, for the purpose of showing that the diagonal and side of a square have no common measure.

Remark. From what has been done in the solution of this example, we may be enabled to conceive of the division of quantity into parts that are less than any given quantities.

Ex. 6. To find the greatest common divisor of 15a1 + 15a3b-21ab1ab3, and 5a7ab + 5a2b3 — 7V3.

Since 3a is a common factor of the terms of the first quantity, and not of the terms of the second quantity, it may be rejected because it does not enter into the common divisor. Hence, dividing each term of the first quantity by 3a, and using the result as the divisor of the other quantity,

and arranging the terms of the divisor and dividend according to the descending powers of a, we have, by Rule I. of Division, the following process.

5a3+5ab

7ab2-7b35a5+0 -7ab2+ 5a2b3+0-76° a2-ab+b2 5a+5a1b-7a3b2 — 7a2b3

[merged small][merged small][ocr errors][merged small][merged small][merged small][merged small]

The process is so evident that it needs no other explanation than to observe that we have supplied the terms that were wanting in the dividend by naughts.

Ex. 7.—To find the greatest common divisor of 3a3 + 5a2b +6ab10b, and 7a3 - 9ab14ab2-1863. 7a3

Since 3 does not divide the first quantity, we shall multiply the second quantity by 3, and it becomes 21a3 — 27a2b +42ab2-54b; whose first term 21a3 can now be exactly divided by the first term 3a of the other quantity. Hence, taking the first quantity for a divisor, and three times the second for a dividend, and arranging according to the descending powers of a, we have (by Rule I. of Division) 7 for the quotient, and - 62ab — 12463 for the remainder. Since 626 does not divide the first divisor, it must be rejected in the remainder, which will be reduced to a2 + 263, which is the greatest required divisor, since it divides the first divisor.

[ocr errors]

Ex. 8.-To find the greatest common divisor of 9ab2 24ab3 + 54a1b1 — 60a3b3 + 57ab21ab7, and 36ab60al +138ab-90al + 126a2b

Since 3ab2 is a factor of each term of the given quantities,. it is consequently a factor of the sought divisor. And to find if the quantities have any compound common divisor, we divide 2 times the first by 3ab2, and the second by 6ab2; then dividing the first result by the second, we get

« PreviousContinue »