so that if a fraction whose numerator and denominator have no common measure greater than unity, be equal to a fraction of lower numerator and denominator, it is equal to another in which the numerator and denominator are still lower. If we proceed with
| a | = | e | in a similar manner, we find |
| b | f |
| a | = | g | where g < e, h < f, |
| b | h |
and so on. Now, if there be any process which perpetually diminishes the terms of a fraction by one or more units at every step, it must at last bring either the numerator or denominator, or both, to 0. Let
| a | = | v |
| b | w |
be one of the steps, and let a = kv + x, b = kw + y; so that
| kv + x | = | v |
| kw + y | w |
Now, if x = 0 but not y, this is absurd, for it gives
| kv | = | kv | . |
| kw + y | kw |
A similar absurdity follows if y be 0, but not x; and if both x and y be = 0, then a = kv, b = kw, or a and b have a common measure, k. Now k must be greater than 1, for v and w are less than c and d, which by hypothesis are less than a and b. Consequently a and b have a common measure k greater than 1, which by hypothesis they have not. If, then, a and b be integers not divisible by any integer greater than 1, the fraction a/b is really in its lowest terms. Also a and b are said to be prime to one another.