Diophantine equation - all solutions

Question

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?

Answer 1

$$ \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 $$