Linear Diophantine Equation Calculator

Enter a, b and c to find every whole-number solution of ax + by = c.

The coefficient of x.

The coefficient of y.

The number on the right.

Try

Result

You entered4x+6y=104x + 6y = 10

x=−5+3t, y=5−2t\displaystyle x = -5 + 3t,\ y = 5 - 2t

Particular solution

(−5, 5)\displaystyle \left(-5,\ 5\right)

gcd

gcd⁡(4,6)=2\displaystyle \gcd(4, 6) = 2
Show the work
  1. Solvability test

    The gcd of the coefficients must divide cc. Here gcd⁡(4,6)=2\gcd(4, 6) = 2 divides 1010, so integer solutions exist.

    Using gcd⁡(a,b)∣c\gcd(a, b) \mid c

  2. A particular solution from the extended Euclidean algorithm

    The extended Euclidean algorithm gives 4×(−1)+6×1=24 \times \left(-1\right) + 6 \times 1 = 2. Multiplying through by c/g=5c / g = 5 turns this into a solution of the equation.

    x0=(−1)×5=−5,  y0=1×5=5x_0 = \left(-1\right) \times 5 = -5,\ \ y_0 = 1 \times 5 = 5
  3. General solution

    Adding b/g=3b/g = 3 to xx and taking a/g=2a/g = 2 from yy leaves ax+byax + by unchanged, and every solution arises this way for a whole number tt.

    Using x=x0+bg t,y=y0−ag tx = x_0 + \dfrac{b}{g}\,t,\quad y = y_0 - \dfrac{a}{g}\,t

    x=−5+3t,  y=5−2tx = -5 + 3t,\ \ y = 5 - 2t
  4. Check with t = 0

    Putting t=0t = 0 back into the equation confirms the particular solution.

    4×(−5)+6×5=−20+30=10\begin{aligned} 4 \times \left(-5\right) + 6 \times 5 &= -20 + 30 \\ &= 10 \end{aligned}
  5. Result

    So every solution has x=−5+3tx = -5 + 3t and y=5−2ty = 5 - 2t for a whole number tt.

Worked examples