## You are here

Homesolving linear Diophantine equation

## Primary tabs

# solving linear Diophantine equation

Here we represent 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:

$\displaystyle 37x-107y=25$ | (1) |

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

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

The terms 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,\quad y=-3+9\cdot 4t+t=-3+37t,\quad x=1+3(-3+37t)-4t=-8+107t.$ |

Accordingly, we may write the general solution of (1) as

$\displaystyle\begin{cases}x=-8+107t\\ y=-3+37t\end{cases}$ |

where $t=0,\,\pm 1,\,\pm 2,\,\ldots$

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).

## Mathematics Subject Classification

11D04*no label found*

- Forums
- Planetary Bugs
- HS/Secondary
- University/Tertiary
- Graduate/Advanced
- Industry/Practice
- Research Topics
- LaTeX help
- Math Comptetitions
- Math History
- Math Humor
- PlanetMath Comments
- PlanetMath System Updates and News
- PlanetMath help
- PlanetMath.ORG
- Strategic Communications Development
- The Math Pub
- Testing messages (ignore)

- Other useful stuff
- Corrections