A linear Diophantine equation (in two variables) is an equation of the general form
![\begin{displaymath}
ax+by=c,
\end{displaymath}](d1_1307.gif) |
(1) |
where solutions are sought with
,
, and
Integers. Such equations can be solved completely, and
the first known solution was constructed by Brahmagupta. Consider the equation
![\begin{displaymath}
ax+by=1.
\end{displaymath}](d1_1308.gif) |
(2) |
Now use a variation of the Euclidean Algorithm, letting
and
Starting from the bottom gives
so
Continue this procedure all the way back to the top.
Take as an example the equation
![\begin{displaymath}
1027x+712 y=1.
\end{displaymath}](d1_1325.gif) |
(10) |
Proceed as follows.
The solution is therefore
,
. The above procedure can be simplified by noting that the two left-most
columns are offset by one entry and alternate signs, as they must since
so the Coefficients of
and
are the same and
![\begin{displaymath}
A_{i-1}=-(A_iq_{i-1}+A_{i+1}).
\end{displaymath}](d1_1335.gif) |
(14) |
Repeating the above example using this information therefore gives
and we recover the above solution.
Call the solutions to
![\begin{displaymath}
ax+by=1
\end{displaymath}](d1_1336.gif) |
(15) |
and
. If the signs in front of
or
are Negative, then solve the above equation and take the signs of
the solutions from the following table:
In fact, the solution to the equation
![\begin{displaymath}
ax-by=1
\end{displaymath}](d1_1347.gif) |
(16) |
is equivalent to finding the Continued Fraction for
, with
and
Relatively Prime (Olds 1963).
If there are
terms in the fraction, take the
th convergent
. But
![\begin{displaymath}
p_nq_{n-1}-p_{n-1}q_n=(-1)^n,
\end{displaymath}](d1_1351.gif) |
(17) |
so one solution is
,
, with a general solution
with
an arbitrary Integer. The solution in terms of smallest Positive Integers is given
by choosing an appropriate
.
Now consider the general first-order equation of the form
![\begin{displaymath}
ax+by=c.
\end{displaymath}](d1_1356.gif) |
(20) |
The Greatest Common Divisor
can be divided through yielding
![\begin{displaymath}
a'x+b'y=c',
\end{displaymath}](d1_1358.gif) |
(21) |
where
,
, and
. If
, then
is not an Integer and the
equation cannot have a solution in Integers. A necessary and sufficient condition for the general
first-order equation to have solutions in Integers is therefore that
. If this is the case, then
solve
![\begin{displaymath}
a'x+b'y=1
\end{displaymath}](d1_1365.gif) |
(22) |
and multiply the solutions by
, since
![\begin{displaymath}
a'(c'x)+b'(c'y)=c'.
\end{displaymath}](d1_1366.gif) |
(23) |
References
Courant, R. and Robbins, H. ``Continued Fractions. Diophantine Equations.'' §2.4 in Supplement to Ch. 1 in
What is Mathematics?: An Elementary Approach to Ideas and Methods, 2nd ed.
Oxford, England: Oxford University Press, pp. 49-51, 1996.
Dickson, L. E. ``Linear Diophantine Equations and Congruences.'' Ch. 2 in
History of the Theory of Numbers, Vol. 2: Diophantine Analysis. New York: Chelsea, pp. 41-99, 1952.
Olds, C. D. Ch. 2 in Continued Fractions. New York: Random House, 1963.
© 1996-9 Eric W. Weisstein
1999-05-24