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 entered3x+5y=13x + 5y = 1

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

Particular solution

(2, −1)\displaystyle \left(2,\ -1\right)

gcd

gcd⁡(3,5)=1\displaystyle \gcd(3, 5) = 1
Show the work
  1. Solvability test

    The gcd of the coefficients must divide cc. Here gcd⁡(3,5)=1\gcd(3, 5) = 1 divides 11, 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 3×2+5×(−1)=13 \times 2 + 5 \times \left(-1\right) = 1. Multiplying through by c/g=1c / g = 1 turns this into a solution of the equation.

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

    Adding b/g=5b/g = 5 to xx and taking a/g=3a/g = 3 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=2+5t,  y=−1−3tx = 2 + 5t,\ \ y = -1 - 3t
  4. Check with t = 0

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

    3×2+5×(−1)=6+(−5)=1\begin{aligned} 3 \times 2 + 5 \times \left(-1\right) &= 6 + \left(-5\right) \\ &= 1 \end{aligned}
  5. Result

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

Worked examples