Linear diophantine equation in two variables is equation of the form:
This calculator is based on the extended Euclidean algorithm written as a continued fraction. However, in some cases (for example, when the coefficient ) simpler methods are used. Also, the calculator does not consider the equations with at least one of the coefficients or equals to , since these cases lead to the ordinary linear equation.
If the coefficient is not divided by the , then the linear diophantine equation in two variables has no solutions. On the contrary, if is divided by , then the specified equation has infinitely many solutions in integers.
To solve a linear diophantine equation in two variables, one first need to find a particular solution and , and then find the general solution using the formulas:
Consider an example of solving a linear diophantine equation in two variables:
Coefficients of the equation: .
Since is divided by , this equation has solutions in integers.
Next, find some specific (particular) solution and of the original equation. To do this, one first need to find a particular solution and of the auxiliary equation with coefficient :
and then multiply the obtained particular solution and of the auxiliary equation by and get a particular solution and of the original equation:
To find a particular solution of the auxiliary equation, we use continued fractions. To do this, we compose a fraction, which is the ratio of the coefficients and , а знаменателем коэффициент .
Transform this fraction into a continuous fraction:
In the resulting continued fraction, discard the last fraction :
The resulting fraction is the ratio of particular solutions and chosen with the correct sign:
By substituting four values in an auxiliary equation, determine that a particular solution is:
Now, to find a particular solution and of the original equation, we multiply the obtained particular solution and of the auxiliary equation by :
Finally, find the final answer using formulas for the general solution:
Our online calculator is able to solve any linear diophantine equation with two unknowns with step by step solution. To get started, one need to input equation and set the variables to find.