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=25+107y37 (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-12+4y37

Since x and 1+3y mean integers, also

z:=12+4y37

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

y=-12+37z4=-3+9z+z4

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

t:=z4

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+94t+t=-3+37t,x=1+3(-3+37t)-4t=-8+107t.

Accordingly, we may write the of (1) as

{x=-8+107ty=-3+37t

where  t=0,±1,±2,

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