Diophantine Equation--Linear

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

$$ax+by=c,$$ (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

$$ax+by=1.$$ (2)

Now use a variation of the Euclidean Algorithm, letting $a=r_1$ and $b=r_2$

$$r_1 = q_1r_2+r_3$$ (3)

$$r_2 = q_2r_3+r_4$$ (4)

$$r_{n-3} = q_{n-3}r_{n-2}+r_{n-1}$$ (5)

$$r_{n-2} = q_{n-2}r_{n-1}+1.$$ (6)

Starting from the bottom gives

$$1 = r_{n-2}-q_{n-2}r_{n-1}$$ (7)

$$r_{n-1} = r_{n-3}-q_{n-3}r_{n-2},$$ (8)

so

$$1 = r_{n-2}-q_{n-2}(r_{n-3}-q_{n-3}r_{n-2})$$

$$= -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.$$ (10)

Proceed as follows.

$$\matrix{ \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

$$1 = -A_{i+1}r_i+A_ir_{i+1}$$ (11)

$$r_{i+1} = r_{i-1}-r_iq_{i-1}$$ (12)

$$1 = 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

$$A_{i-1}=-(A_iq_{i-1}+A_{i+1}).$$ (14)

Repeating the above example using this information therefore gives

$$\matrix{ \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

$$ax+by=1$$ (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

$$ax-by=1$$ (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

$$p_nq_{n-1}-p_{n-1}q_n=(-1)^n,$$ (17)

so one solution is $x_0=(-1)^nq_{n-1}$, $y_0=(-1)^np_{n-1}$, with a general solution

$$x = x_0+kb$$ (18)

$$y = 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

$$ax+by=c.$$ (20)

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

$$a'x+b'y=c',$$ (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

$$a'x+b'y=1$$ (22)

and multiply the solutions by $c'$, since

$$a'(c'x)+b'(c'y)=c'.$$ (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.