Linear Diophantine Equations Solver

Linear Diophantine equations

Constant a

Constant b

Constant c

Calculate

Equation

 

All solutions for x

 

All solutions for y

 

x

 

y

 

hidden output

 

hidden output

 

 Link  Save  Widget

Since this is all about math, I copy some content from wikipedia for a start.

In mathematics, a Diophantine equation is a polynomial equation in two or more unknowns such that only the integer solutions are searched or studied (an integer solution is a solution such that all the unknowns take integer values). A linear Diophantine equation is an equation between two sums of monomials of degree zero or one.

The simplest linear Diophantine equation takes the form:

,

where a, b and c are given integers, x, y — unknowns.

The following theorem completely describes the solutions: This Diophantine equation has a solution (where x and y are integers) if and only if c is a multiple of the greatest common divisor of a and b. Moreover, if (x, y) is a solution, then the other solutions have the form (x + kv, y - ku), where k is an arbitrary integer, and u and v are the quotients of a and b (respectively) by the greatest common divisor of a and b.

To find the solution one can use Extended Euclidean algorithm (except for a = b = 0 where either there is an unlimited number of solutions or none).

If a and b are positive integers, we can find their GCD g using Extended Euclidean algorithm, along with и , so:

.

If c is a multiple of g, the Diophantine equation has solution, otherwise, there is no solution.

That is if c is a multiple of g, then:

and one of the possible solutions is:

If either a or b is negative, we can solve the equation using its modulus, then change the sign accordingly.

If we know one of the solutions, we can find their general form.

Let g = GCD(a,b), and we have:

.

By adding to and subtracting from , we get:

So, any numbers like these:

,

where k is integer, are the solutions of Linear Diophantine equation.