where a, b, c denote given whole numbers, and x, y two numbers to be found, so that both may be integers. That this condition may be fulfilled, it is necessary that the coefficients a, b have no common divisor which is not also a divisor of c; for if a = md and b = me, then ax + by = mdx + mey = c, and dx + ey = c/m; but d, e, x, y are supposed to be whole numbers, therefore c/m is a whole number; hence m must be a divisor of c.
Of the four forms expressed by the equation ax ± by = ±c, it is obvious that ax + by = −c can have no positive integral solutions. Also ax − by = −c is equivalent to by − ax = c, and so we have only to consider the forms ax ± by = c. Before proceeding to the general solution of these equations we will give a numerical example.
To solve 2x + 3y = 25 in positive integers. From the given equation we have x = (25 − 3y) / 2 = 12 − y − (y − 1) / 2. Now, since x must be a whole number, it follows that (y − 1)/2 must be a whole number. Let us assume (y − 1) / 2 = z, then y = 1 + 2z; and x = 11 − 3z, where z might be any whole number whatever, if there were no limitation as to the signs of x and y. But since these quantities are required to be positive, it is evident, from the value of y, that z must be either 0 or positive, and from the value of x, that it must be less than 4; hence z may have these four values, 0, 1, 2, 3.
| If | z = 0, | z = 1, | z = 2, | z = 3; |
| Then | x = 11, | x = 8, | x = 5, | x = 2, |
| y = 1, | y = 3, | y = 5, | y = 7. |
3. We shall now give the solution of the equation ax − by = c in positive integers.
Convert a/b into a continued fraction, and let p/q be the convergent immediately preceding a/b, then aq − bp = ±1 (see [Continued Fraction]).
(α) If aq − bp = 1, the given equation may be written
ax − by = c (aq − bp);
∴ a (x − cq) = b (y − cp).
Since a and b are prime to one another, then x − cq must be divisible by b and y − cp by a; hence
(x − cq) / b = (y − cq) / a = t.