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
x2 = 2y2 + 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 = xo + pt
y = yo - qt
Where (xo, yo) 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 equation14x + 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 arep = 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 isx = 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