# 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