Euler's Method for Solving Linear Diophantine Equations

Requires a Wolfram Notebook System

Interact on desktop, mobile and cloud with the free Wolfram CDF Player or other Wolfram Language products.

Requires a Wolfram Notebook System

Edit on desktop, mobile and cloud with any Wolfram Language product.

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.


When using the second method dividing by means finding an integer such that , while in the first it is the integer part of .

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.

If we rewrite the equation as one more step is needed.

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 .


Contributed by: Izidor Hafner (January 2014)
Open content licensed under CC BY-NC-SA




[1] T. Koshy, Elementary Number Theory with Applications, Amsterdam: Academic Press, 2007 p. 199.

Feedback (field required)
Email (field required) Name
Occupation Organization
Note: Your message & contact information may be shared with the author of any specific Demonstration for which you give feedback.