1
$\begingroup$

Calculate $6/87 \pmod{137}$

I do not understand the Euclidean GCD algorithm. If someone can please explain the overall logic of this it would be much appreciated.I have posted what the solution is supposed to be below:

solution

$\endgroup$
1
$\begingroup$

I highly recommend that you use this version of the Extended Euclidean algorithm, which is simpler and far less error-prone than the common back-substitution version. For an example see here.

Alternatively we can use my succinct fractional form of that algorithm, as below

$$\dfrac{0}{137} \overset{\large\frown}\equiv\ \bbox[5px,border:1px solid red]{\dfrac{6}{87}}\overset{\large\frown}\equiv\ \dfrac{-6}{50}\overset{\large\frown}\equiv\dfrac{18}{-13}\overset{\large\frown}\equiv \dfrac{66}{-2}\equiv \dfrac{-33}1\equiv \bbox[5px,border:1px solid red]{ \dfrac{104}1}\pmod{137} $$

$\endgroup$
0
$\begingroup$

$$ \frac{ 137 }{ 87 } = 1 + \frac{ 50 }{ 87 } $$ $$ \frac{ 87 }{ 50 } = 1 + \frac{ 37 }{ 50 } $$ $$ \frac{ 50 }{ 37 } = 1 + \frac{ 13 }{ 37 } $$ $$ \frac{ 37 }{ 13 } = 2 + \frac{ 11 }{ 13 } $$ $$ \frac{ 13 }{ 11 } = 1 + \frac{ 2 }{ 11 } $$ $$ \frac{ 11 }{ 2 } = 5 + \frac{ 1 }{ 2 } $$ $$ \frac{ 2 }{ 1 } = 2 + \frac{ 0 }{ 1 } $$ Simple continued fraction tableau:
$$ \begin{array}{cccccccccccccccc} & & 1 & & 1 & & 1 & & 2 & & 1 & & 5 & & 2 & \\ \frac{ 0 }{ 1 } & \frac{ 1 }{ 0 } & & \frac{ 1 }{ 1 } & & \frac{ 2 }{ 1 } & & \frac{ 3 }{ 2 } & & \frac{ 8 }{ 5 } & & \frac{ 11 }{ 7 } & & \frac{ 63 }{ 40 } & & \frac{ 137 }{ 87 } \end{array} $$ $$ $$ $$ 137 \cdot 40 - 87 \cdot 63 = -1 $$

..

$\endgroup$

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.