homechevron_rightStudychevron_rightMath

Linear Diophantine equations

This calculator solves linear diophantine equations.

This page exists due to the efforts of the following people:

Timur

Timur

As usual, here goes the calculator, and theory goes below it.

PLANETCALC, Linear Diophantine equations

Linear Diophantine equations

Equation
 
All solutions for x
 
All solutions for y
 
x
 
y
 

Since this is all about math, I copy some content from wikipedia for the 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

ax + by = c,

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

The solutions are completely described by the following theorem: 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 are 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 x_g и y_g, so:

ax_g + by_g = g.

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

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

a x_g (\frac{c}{g}) + b y_g (\frac{c}{g})=c

and one of the possible solutions is:

x_0 = x_g (\frac{c}{g})

y_0 = y_g(\frac{c}{g})

If either a or b is negative, we can solve equation using it's modulus, then change sign accordingly.

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

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

ax_0 + by_0 = c.

By adding \frac{b}{g} to x_0 and subtracting \frac{a}{g} from y_0, we get:

a(x_0 + \frac{b}{g}) + b(y_0 - \frac{a}{g}) = ax_0+by_0 + \frac{ab}{g}-\frac{ba}{g}=c

So, any numbers like these:
x = x_0 + k \frac{b}{g}

y = y_0 - k \frac{a}{g},

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

URL copied to clipboard
Creative Commons Attribution/Share-Alike License 3.0 (Unported) PLANETCALC, Linear Diophantine equations

Comments