# Diophantine equation - all solutions

I have a question concerning diophantine equations. I get the first steps right with the Euclides Algorithm and then doing it backwards. However, when trying to find all solutions I often make some small mistakes so I figured that I don't understand that part well enough. I'll make an example to show.

Find all solutions to 186x + 69y = 3

First I do Euclides algorithm:

186 = 69(2) + 48

69 = 48(1) + 21

48 = 21(2) + 6

21 = 6(3) + 3

I won't show the substitution but I get: 69(27) - 186(10) which divided by 3 gives: x = 62(-10) and y = 23(27)

Now is the time that I always screw up somehow. How should I think here when I try to add something times k to both X and Y to make this work for every possible value?

In this I added: x = 62(-10 - 23k) and y = 23(27 + 62k) which was wrong (it should be the opposite +/- on the k). But why?

• Before using the Euclidean algorithm, simplify the equation by dividng both sides by $3$. Oct 17, 2017 at 23:16

$$\gcd( 186, 69 ) = ???$$
$$\frac{ 186 }{ 69 } = 2 + \frac{ 48 }{ 69 }$$ $$\frac{ 69 }{ 48 } = 1 + \frac{ 21 }{ 48 }$$ $$\frac{ 48 }{ 21 } = 2 + \frac{ 6 }{ 21 }$$ $$\frac{ 21 }{ 6 } = 3 + \frac{ 3 }{ 6 }$$ $$\frac{ 6 }{ 3 } = 2 + \frac{ 0 }{ 3 }$$ Simple continued fraction tableau:
$$\begin{array}{cccccccccccc} & & 2 & & 1 & & 2 & & 3 & & 2 & \\ \frac{ 0 }{ 1 } & \frac{ 1 }{ 0 } & & \frac{ 2 }{ 1 } & & \frac{ 3 }{ 1 } & & \frac{ 8 }{ 3 } & & \frac{ 27 }{ 10 } & & \frac{ 62 }{ 23 } \end{array}$$  $$\begin{array}{ccc} \frac{ 1 }{ 0 } & \mbox{digit} & 2 \\ \frac{ 2 }{ 1 } & \mbox{digit} & 1 \\ \frac{ 3 }{ 1 } & \mbox{digit} & 2 \\ \frac{ 8 }{ 3 } & \mbox{digit} & 3 \\ \frac{ 27 }{ 10 } & \mbox{digit} & 2 \\ \frac{ 62 }{ 23 } & \mbox{digit} & 0 \\ \end{array}$$
$$62 \cdot 10 - 23 \cdot 27 = -1$$
$$\gcd( 186, 69 ) = 3$$
$$186 \cdot 10 - 69 \cdot 27 = -3$$