## Linear Diophantine Equations

A Diophantine equation is any algebraic equation for which we seek only integer solutions. A linear diophantine equation is any equation of the form where are constants with not both zero and are variables.

Consider the equation Allowing and to take all possible integer values results in the left hand side taking on the set of multiples of (since the greatest common divisor of 6 and 15 is 3) and since 4 is not a multiple of 3 the equation has no solutions. The equation has solutions because 9 is in the set. We can divide this by the common factor 3 to give The greatest common divisor of 2 and 5 is 1 so so the left hand side takes on all integer values.

In fact for diophantine equations of the form the left hand side takes on all multiples of so a necessary and sufficient condition for the equation to have solutions is that divides In fact there are an infinite number of solutions.

Example: Find the set of solutions to Since this equation has solutions. Use the Euclidean algorithm to find a solution.

33=1*20+13

20=1*13+7

13=1*7+6

7=1*6+1

6=6*1+0

Then

1=7-6

=7-(13-7)=-1*13+2*7

=-1*13+2*(20-13)=2*20-3*13

=2*20-3*(33-20)=-3*33+5*20

So 1=-3*33+5*20. Multiplying by 3 gives 3=-9*33+15*20 and is one solution.

Put and substitute in to obtain which simplifies to We can put then the complete set of solutions is  