0

i am stuck for many hours and i don't understand using the extended euclidean algorithm. i calculated it the gcd using the regular algorithm but i don't get how to calculate it properly to obtain s,t,r.

i understand that from the gcd i can get a linear combination representation, but i don't get how to do it using the algorithm.

how can i find $s,t,r$ for $a=154, b= 84$?

if it is of any importance, the algorithm i am referring to is from the book cryptography: theory and practice

thank you very much. became hopeless because of it

mathnoobie
  • 13
  • 3
  • Welcome to Mathematics Stack Exchange! Please, format maths on this site using LaTeX, as described [here](https://math.stackexchange.com/help/notation). There is also a [quick reference](https://math.meta.stackexchange.com/questions/5020/mathjax-basic-tutorial-and-quick-reference). Thank you. – bp99 Jan 07 '20 at 13:25
  • edited my post.. – mathnoobie Jan 07 '20 at 13:30

1 Answers1

1

Using the Euclidean algorithm, we have

$$ \begin{align} 154&=1\cdot84+70\tag{1}\\ 84&=1\cdot70+14\tag{2}\\ 70&=5\cdot14+0 \end{align} $$ The last nonzero remainder is 14. So $\gcd(154,84)=14$. Now $$ \begin{align*} 14&=84-70\qquad\text{(using 2)}\\ &=84-(154-84)\qquad\text{(using 1)}\\ &=2\cdot84-1\cdot154 \end{align*} $$ So $14=2\cdot84-1\cdot154$.