|
|
|
|
![[parent]](http://images.planetmath.org:8080/images/uparrow.png)
solving linear Diophantine equation
|
(Topic)
|
|
|
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:
 |
(1) |
We solve first (1) for $x$ (which has absolutely smaller coefficient than $y$ ):
 |
(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\cdot4t+t = -3+37t, \quad x = 1+3(-3+37t)-4t = -8+107t.$$ Accordingly, we may write the general solution of (1) as
where $t = 0,\,\pm1,\,\pm2,\,\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).
|
"solving linear Diophantine equation" is owned by pahio.
|
|
(view preamble | get metadata)
Cross-references: cycles, parameter, dividend, remainder, polynomial, division, numerator, coefficient, equation, solution, integer, Diophantine equation
This is version 3 of solving linear Diophantine equation, born on 2008-01-27, modified 2008-01-30.
Object id is 10220, canonical name is SolvingLinearDiophantineEquation.
Accessed 3755 times total.
Classification:
| AMS MSC: | 11D04 (Number theory :: Diophantine equations :: Linear equations) |
|
|
|
|
|
|
Pending Errata and Addenda
|
|
|
|
|
|
|
|
|
|
|
