Euclidean algorithm and Multiplicative inverse in RSA Cryptosystem

Question

I understand RSA Cryptosystem, the Euclidean algorithm, and mod, however, I can't seem to understand how to solve the following problem.

-Use Euclidean algorithm to compute the multiplicative inverse $s = r^{-1}\bmod (p − 1)(q − 1)$, where $r = 89$ and $p = 173$, $q = 103$.

So, I've found the equation for the multiplicative inverse ($89x + 17544y = 1$) and some GCD:

$\gcd(17544, 89)= 11 (197×89 +11) $

$11=17544-197×89$

$\gcd(89, 11)= 1 (8×11+1)$

$1= 89 -8×11$

• $1=89-8×11 \implies 1= ?$ That is the part I'm confused about. I'm not sure with what I should substitute it with.

Answer 1

Use the extended Euclidean algorithm to obtain a direct answer, using the recursive relation $\:u_{n+1}=u_{n-1}-q_nr_n$:

\begin{array}{rrrr} r_n &u_n&v_n &q_n \\\hline 17544&0&1 \\ 89 &1&0&197 \\\hline 11&-197 &1 & 8 \\ 1 & \color{red}{1577} &-8 \\ \hline \end{array}

Answer 2

It's important to be neat and methodical when performing the extended Euclidean algorithm, so you don't get tangled up. ;)

Your goal is to find an $x,y$ pair that satisfy $$89x + 17544y = 1$$

You have calculated all the bits you need. You just need to replace the $11$ in $$1=89-8×11$$ with $$11=17544-197×89$$ Thus, $$1=89-8×(17544-197×89)$$ which can easily be simplified.