Tuesday, 25 September 2018

gcd and lcm - using extended euclidean algorithm to find s, t, r




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


Answer



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


No comments:

Post a Comment

real analysis - How to find $lim_{hrightarrow 0}frac{sin(ha)}{h}$

How to find $\lim_{h\rightarrow 0}\frac{\sin(ha)}{h}$ without lhopital rule? I know when I use lhopital I easy get $$ \lim_{h\rightarrow 0}...