solving linear Diophantine equation

Here we an elementary but very comprehensible method for solving any linear Diophantine equation with two unknowns, i.e. for finding the general integer solution of an equation of the form

$$ax-my=b$$

where $a,b,m$ are known integers and $x,y$ the unknowns.

The method is illustrated via a numerical example:

$37x-107y=25$ (1)

We solve first (1) for $x$ (which has absolutely smaller coefficient than $y$):

$x={\displaystyle \frac{25+107y}{37}}$ (2)

The in the numerator may be split so that division yields a polynomial with integer coefficients and that the remainder has absolutely smaller coefficients (now $-12$ and $-4$) than the dividend in (2) had:

$$x=1+3y-\frac{12+4y}{37}$$

Since $x$ and $1+3y$ mean integers, also

$$z:=\frac{12+4y}{37}$$

must be an integer.  Now solve this last equation for $y$ and split the new numerator similarly as above:

$$y=\frac{-12+37z}{4}=-3+9z+\frac{z}{4}$$

Since $y$ and $-3+9z$ mean integers, also

$$t:=\frac{z}{4}$$

must be an integer.  It is apparent that we can give any integer value for $t$, which thus may be thought as a parameter determining the values of the other letters.  We obtain successively

$$z=4t,y=-3+9\cdot 4t+t=-3+37t,x=1+3(-3+37t)-4t=-8+107t.$$

Accordingly, we may write the of (1) as

$\{\begin{array}{cc}x=-8+107t\hfill & \\ y=-3+37t\hfill & \end{array}$

where  $t=0,\pm 1,\pm 2,\mathrm{\dots }$

This method and the use of a parameter for expressing the solution were well known in the ancient world, especially in solving astronomical cycles as noted by Brahmagupta (598–668).

Title	solving linear Diophantine equation
Canonical name	SolvingLinearDiophantineEquation
Date of creation	2013-03-22 17:45:55
Last modified on	2013-03-22 17:45:55
Owner	pahio (2872)
Last modified by	pahio (2872)
Numerical id	6
Author	pahio (2872)
Entry type	Topic
Classification	msc 11D04
Related topic	LinearCongruence