info prev up next book cdrom email home

Diophantine Equation--Linear

A linear Diophantine equation (in two variables) is an equation of the general form

\end{displaymath} (1)

where solutions are sought with $a$, $b$, and $c$ Integers. Such equations can be solved completely, and the first known solution was constructed by Brahmagupta. Consider the equation
\end{displaymath} (2)

Now use a variation of the Euclidean Algorithm, letting $a=r_1$ and $b=r_2$
$\displaystyle r_1$ $\textstyle =$ $\displaystyle q_1r_2+r_3$ (3)
$\displaystyle r_2$ $\textstyle =$ $\displaystyle q_2r_3+r_4$ (4)
$\displaystyle r_{n-3}$ $\textstyle =$ $\displaystyle q_{n-3}r_{n-2}+r_{n-1}$ (5)
$\displaystyle r_{n-2}$ $\textstyle =$ $\displaystyle q_{n-2}r_{n-1}+1.$ (6)

Starting from the bottom gives
$\displaystyle 1$ $\textstyle =$ $\displaystyle r_{n-2}-q_{n-2}r_{n-1}$ (7)
$\displaystyle r_{n-1}$ $\textstyle =$ $\displaystyle r_{n-3}-q_{n-3}r_{n-2},$ (8)

$\displaystyle 1$ $\textstyle =$ $\displaystyle r_{n-2}-q_{n-2}(r_{n-3}-q_{n-3}r_{n-2})$  
  $\textstyle =$ $\displaystyle -q_{n-2}r_{n-3}+(1-q_{n-2}q_{n-3})r_{n-2}.$ (9)

Continue this procedure all the way back to the top.

Take as an example the equation

1027x+712 y=1.
\end{displaymath} (10)

Proceed as follows.

\hfill 1027\!\!\!\!\!&= \hfill 712\cdot\!\!\!\!\!& ...
...rrow\cr \vert\cr \vert\cr \vert\cr \vert\cr \vert\cr \vert\cr}

The solution is therefore $x=-165$, $y=238$. 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
$\displaystyle 1$ $\textstyle =$ $\displaystyle -A_{i+1}r_i+A_ir_{i+1}$ (11)
$\displaystyle r_{i+1}$ $\textstyle =$ $\displaystyle r_{i-1}-r_iq_{i-1}$ (12)
$\displaystyle 1$ $\textstyle =$ $\displaystyle A_ir_{i-1}-(A_iq_{i-1}+A_{i+1}),$ (13)

so the Coefficients of $r_{i-1}$ and $r_{i+1}$ are the same and
\end{displaymath} (14)

Repeating the above example using this information therefore gives

\hfill 1027\!\!\!\!\!&= \hfill 712\cdot\!\!\!\!\!& ...
...rrow\cr \vert\cr \vert\cr \vert\cr \vert\cr \vert\cr \vert\cr}

and we recover the above solution.

Call the solutions to

\end{displaymath} (15)

$x_0$ and $y_0$. If the signs in front of $ax$ or $by$ are Negative, then solve the above equation and take the signs of the solutions from the following table:

equation $x$ $y$
$ax+by=1$ $x_0$ $y_0$
$ax-by=1$ $x_0$ $-y_0$
$-ax+by=1$ $-x_0$ $y_0$
$-ax-by=1$ $-x_0$ $-y_0$

In fact, the solution to the equation

\end{displaymath} (16)

is equivalent to finding the Continued Fraction for $a/b$, with $a$ and $b$ Relatively Prime (Olds 1963). If there are $n$ terms in the fraction, take the $(n-1)$th convergent $p_{n-1}/q_{n-1}$. But
\end{displaymath} (17)

so one solution is $x_0=(-1)^nq_{n-1}$, $y_0=(-1)^np_{n-1}$, with a general solution
$\displaystyle x$ $\textstyle =$ $\displaystyle x_0+kb$ (18)
$\displaystyle y$ $\textstyle =$ $\displaystyle y_0+ka$ (19)

with $k$ an arbitrary Integer. The solution in terms of smallest Positive Integers is given by choosing an appropriate $k$.

Now consider the general first-order equation of the form

\end{displaymath} (20)

The Greatest Common Divisor $d\equiv {\rm GCD}(a,b)$ can be divided through yielding
\end{displaymath} (21)

where $a'\equiv a/d$, $b'\equiv b/d$, and $c'\equiv c/d$. If $d \notdiv c$, then $c'$ 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 $d\vert c$. If this is the case, then solve
\end{displaymath} (22)

and multiply the solutions by $c'$, since
\end{displaymath} (23)


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.

info prev up next book cdrom email home

© 1996-9 Eric W. Weisstein