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 formwhereare constants withnot both zero andare variables.

Consider the equationAllowingandto 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 equationhas no solutions. The equationhas solutions because 9 is in the set. We can divide this by the common factor 3 to giveThe 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 formthe left hand side takes on all multiples ofso a necessary and sufficient condition for the equation to have solutions is that dividesIn fact there are an infinite number of solutions.

Example: Find the set of solutions to

Sincethis 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 andis one solution.

Putand substitute in to obtainwhich simplifies toWe can putthen the complete set of solutions is