WOLFRAM NOTEBOOK

WOLFRAM|DEMONSTRATIONS PROJECT

Euler's Method for Solving Linear Diophantine Equations

​
Method 1
Method 2
a
13
b
21
c
25
show steps
1
2
3
4
show solution
Solve the equation 13x+21y25.
13x + 21y = 25
x2-2y + (
1
13
(5y-1))
z
1
13
(5y-1)
-5y + (13z) = -1
y3z + (
1
5
(1-2z))
s
1
5
(1-2z)
Solution:
s = 1-2t
z = -2+5t
y = -5+13t
x = 10-21t
A linear Diophantine equation in two variables is an equation of the form
ax+by=c
, where
a
,
b
, and
c
are integers and solutions are sought in integers. This Demonstration shows Euler's method for solving such an equation.
When using the second method dividing
b
by
a
means finding an integer
n
such that
|b-an|≤1/2
, while in the first it is the integer part of
a/b
.
As an example, consider the linear Diophantine equation
4x+7y=25
; rewrite it as
x=6-2y+(1+y)/4
. Introduce the variable
z=(1+y)/4
and simplify to get a new equation,
-y+4z=1
. Solving
-y+2z=1
for
y
gives
y=-1+4z
, and finally
x=8-7z
. Assigning integer values to
z
gives all possible solutions to the original equation.
If we rewrite the equation
4x+7y=25
as
x=6-y+(1-3y)/4
one more step is needed.
In this example, we can write
y=dz+e
for integers
d
and
e
(i.e.
y=1+4z
), so the process terminates on the first iteration. If there had been a fraction, another variable
s
would be introduced to produce a new equation between the last two variables
z
and
s
. 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
x
and
y
.
​
Wolfram Cloud

You are using a browser not supported by the Wolfram Cloud

Supported browsers include recent versions of Chrome, Edge, Firefox and Safari.


I understand and wish to continue anyway »

You are using a browser not supported by the Wolfram Cloud. Supported browsers include recent versions of Chrome, Edge, Firefox and Safari.