97. 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,[13] as follows:
98. 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 16 had a greater measure than 8, it could not be common to 16 and 8.
| Therefore | 8 | is g. c. m. of | 16 and 8, |
| (97) g. c. m. of | 16 and 8 | is g. c. m. of | 24 and 16, |
| g. c. m. of | 24 and 16 | is g. c. m. of | 112 and 24, |
| g. c. m. of | 112 and 24 | is g. c. m. of | 360 and 112, |
| Therefore | 8 | is g. c. m. of | 360 and 112. |
The process carried on may be written down in either of the following ways:
- 112) 360 (3
- 336
- 24) 112 (4
- 96
- 16) 24 (1
- 16
- 8) 16 (2
- 16
- 0
| 112 | 360 | 3 |
| 96 | 336 | 4 |
| 16 | 24 | 1 |
| 16 | 16 | 2 |
| 0 | 8 |