the remainder 24, that is (72) 360 is three times 112 and 24, or 360 = 112 × 3 + 24. From this it follows, that 24 is the difference between 360 and 3 times 112, or 24 = 360-112 × 3. Take any number which measures both 360 and 112; for example, 4.
- 4 measures 360,
- 4 measures 112, and therefore (94) measures 112 × 3,
- or 112 + 112 + 112.
Therefore (93) it measures 360-112 × 3, which is the remainder 24. The same reasoning may be applied to all other measures of 360 and 112; and the result is, that every quantity which measures both the dividend and divisor also measures the remainder. Hence, every common measure of a dividend and divisor is also a common measure of the divisor and remainder.
- Every common measure of the divisor and remainder is also a common measure of the dividend and divisor. Take the same example, and recollect that 360 = 112 × 3 + 24. Take any common measure of the remainder 24 and the divisor 112; for example, 8. Then
- 8 measures 24;
- and 8 measures 112, and therefore (94) measures 112 × 3.
Therefore (93) 8 measures 112 × 3 + 24, or measures the dividend 360. Then every common measure of the remainder and divisor is also a common measure of the divisor and dividend, or there is no common measure of the remainder and divisor which is not also a common measure of the divisor and dividend.
- I. It is proved in (95) that the remainder and divisor have all the common measures which are in the dividend and divisor.
II. It is proved in (96) that they have no others.
It therefore follows, that the greatest of the common measures of the first two is the greatest of those of the second two, which shews how to find the greatest common measure of any two numbers,5 as follows:
- Take the preceding example, and let it be required to find the g. c. m. of 360 and 112, and observe that
| 360 divided by | 112 gives the remainder | 24, |
|---|---|---|
| 112 divided by | 24 gives the remainder | 16, |
| 24 divided by | 16 gives the remainder | 8, |
| 16 divided by | 8 gives no remainder. |
Now, since 8 divides 16 without remainder, and since it also divides itself without remainder, 8 is the g. c. m. of 8 and 16, because it is impossible to divide 8 by any number greater than 8; so that, even if