Euler's Method for Solving Linear Diophantine Equations
Euler's Method for Solving Linear Diophantine Equations
A linear Diophantine equation in two variables is an equation of the form , where , , and are integers and solutions are sought in integers. This Demonstration shows Euler's method for solving such an equation.
ax+by=c
a
b
c
When using the second method dividing by means finding an integer such that , while in the first it is the integer part of .
b
a
n
|b-an|≤1/2
a/b
As an example, consider the linear Diophantine equation ; rewrite it as . Introduce the variable and simplify to get a new equation, . Solving for gives , and finally . Assigning integer values to gives all possible solutions to the original equation.
4x+7y=25
x=6-2y+(1+y)/4
z=(1+y)/4
-y+4z=1
-y+2z=1
y
y=-1+4z
x=8-7z
z
If we rewrite the equation as one more step is needed.
4x+7y=25
x=6-y+(1-3y)/4
In this example, we can write for integers and (i.e. ), so the process terminates on the first iteration. If there had been a fraction, another variable would be introduced to produce a new equation between the last two variables and . After a finite number of iterations, the process must end because the coefficients are decreasing positive integers. Assigning integer values to the last variable and substituting back up the chain gives all solutions to the original equation in and .
y=dz+e
d
e
y=1+4z
s
z
s
x
y