# 4. Diophantine equations

diophantine equation is an equation where only integer solutions are accepted. This implies that diophantine equations becomes harder (or even impossible) to solve than equations that do not have this restriction. We will show that diophantine equations of the type a, b ,c, x, y integean be solved by Euclid’s algorithm (assuming that there is a solution). The method of solution depends of the coefficients a, b and c. We have three different variants that we treat in the examples below:
Example 1: Solve the equation First we examine gcd(97,35). We have This means that gcd(97,35)=1. Now we go backwards and express gcd(97,35) as a linear combination of 97 and 35: that is If we multiply this equation by 13 we get which means that one solution of the diophantine equation is x=169, y=-468. This is however not the only solution. We can exactly as in part 3add and subtract the least common multiple such that We thus have infinitely many solutions Example 2: Solve the equation First we examine gcd(98,35). We have This implies that gcd(98,35)=7, which means that every linear combination of 98 and 35 must contain the factor 7. Then also 98x+35ymust be a multiple of 7. But since the right hand side 13 does not contain the factor 7, there are no integer solutions to this equation.

Example 3: Solve the equation We had from example 2 that gcd(98,35)=7. If we go backwards and express gcd(98,35) as a linear combination of 98 and 35 we get: that is If we multiply this equation by 2 we get which implies that one solution to the diophantine equation is x=-2, y=-6. This is however not the only solution. We can exactly as in part 3 add and subtract the least common multiple such that We thus have infinitely many solutions 