Elements of Algebra

CHAP. III. ADDITIONS. 531 given equation $ax - by = c$, is resolvible in integer numbers, and we successively substitute for $x$ all the integer numbers, positive as well as negative, contained between these two limits $\frac{b'}{2}$, and $-\frac{b'}{2}$, we shall necessarily find one that will satisfy this equation: and we shall likewise find a satisfactory value of $y$ among the positive, or negative whole numbers, contained between the limits $\frac{a'}{2}$, and $-\frac{a'}{2}$. By these means we may find the first solution of the equation proposed; after which, we shall have all the others by the preceding formulæ. 43. But, without employing the method of trial, which we have now proposed, and which would sometimes be very laborious, we may make use of the very simple and direct method explained in Chap. I. of the preceding Treatise, or of the following method. First, if the numbers $a$ and $b$ are not prime to each other, the equation cannot subsist in integer numbers, unless the given number, $c$, be divisible by the greatest common measure of $a$ and $b$. Supposing, therefore, the division performed, and expressing the quotients by $a'$, $b'$, $c'$, we shall have to resolve the equation, $a'x - b'y = c'$, where $a'$ and $b'$ are prime to each other. Secondly, if we can find values of $p$ and $q$ that satisfy the equation, $a'p - b'q = \pm 1$, we may resolve the preceding equation; for it is evident that, by multiplying these values by $\pm c'$, we shall have values that will satisfy the equation, $a'x - b'y = c'$; that is to say, we shall have $x = \pm pc'$, and $y = \pm qc'$. Now, the equation $a'p - b'q = \pm 1$ is always resolvible in integers, as we have demonstrated, Art. 23; and, in order to find the least values of $p$ and $q$ that can satisfy it, we shall only have to convert the fraction $\frac{b'}{a'}$, into a continued fraction by the method of Art. 4, and then deduce from it a series of principal fractions, converging to the same fraction, $\frac{b'}{a'}$, by the formulæ of Art. 10; the last of these fractions will be the same fraction $\frac{b'}{a'}$; and if we represent the last M M 2