Linear Diophantine Equations Solver

This calculator solves linear diophantine equations (LDE). The LDE calculator is right below, and if you want to recall what linear diophantine equations are, you can find the theory after the calculator.

Esta página existe graças aos esforços das seguintes pessoas:



Criado: 2014-02-23 16:07:21, Ultima atualização: 2021-11-16 14:40:48
Creative Commons Attribution/Share-Alike License 3.0 (Unported)

Este conteúdo é licenciado de acordo com a Licença Creative Commons de Atribuição/CompartilhaIgual 3.0 (Unported). Isso significa que você pode redistribuir ou modificar livremente este conteúdo sob as mesmas condições de licença e precisa atribuir ao autor original colocando um hyperlink para este trabalho no seu site. Além disto, favor não modificar qualquer referência ao trabalho original (caso houver) que estiverem contidas neste conteúdo.

PLANETCALC, Linear Diophantine equations

Linear Diophantine equations

All solutions for x
All solutions for y
hidden output
hidden output

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:

ax + by = c,

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 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 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:

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 copiado para a área de transferência
PLANETCALC, Linear Diophantine Equations Solver