0
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ Before using the Euclidean algorithm, simplify the equation by dividng both sides by $3$. $\endgroup$ – quasi Oct 17 '17 at 23:16
0
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Interesting take on Euclid' s algorithm $\endgroup$ – AmateurMathPirate Oct 17 '17 at 23:30
  • $\begingroup$ @AmateurMathGuy I find continued fractions fairly easy to remember, more so than the "back-substitution" that is often taught. $\endgroup$ – Will Jagy Oct 17 '17 at 23:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.