How to Find the General Solution of a Linear Diophantine Equation in Two Variables

Diophantine equations are polynomial expressions that have integer coefficients and integer solutions. Although they often appear in simple forms, they are challenging to solve because you cannot always apply standard analytical methods. For example, the quadratic Diophantine equation

x² = 2y² + 2y

looks simple enough, but finding only the integer solutions to this expression is difficult. A few solutions are

x = 0 and y = 0
x = 12 and y = 8
x = 408 and y = 288

Linear Diophantine equations in two variables are luckily very easy to solve by applying properties of divisibility. If you have an equation ax + by = c, the general solution takes the form

x = x_o + pt
y = y_o - qt

Where (x_o, y_o) is a particular solution, t ranges over the set of all integers, and p and q are fixed integer coefficients of t. You can use the method below to solve such equations, or try the calculator above.

Step 1: Find a Single Solution

The first step in finding a general solution to a linear two-variable Diophantine equation is to find a single solution. For instance, take the equation

14x + 99y = 107

Using trial and error, you can obtain the solution x = 43 and y = -5.

Step 2: Find p and q

The coefficients p and q depend on the greatest common divisor (GCD) of a and b. The formulas are

p = b/GCD(a,b)
q = a/GCD(a,b)

If a = 14 and b = 99, the GCD of a and b is 1, since these two integers are relatively prime to one another (they have no prime factors in common). Thus, p = 99 and q = 14.

Step 3: Putting It All Together

The general solution of 14x + 99y = 107 is

x = 43 + 99t
y = -5 - 14t

where t is any integer. If you replace t with any integer, you will generate a new solution to the equation. For instance, plug in t = -2, t = 3, and t = 17. This yields

x = -155 and y = 23
x = 340 and y = -47
x = 1726 and y = -243

© Had2Know 2010