Extended Euclidean Algorithm, what is our answer?

Question

I am learning Euclidean Algorithm and the Extended Euclidean Algorithm. The problem I have is:

Find the multiplicative inverse of 33 modulo n, for n = 1023, 1033, 1034, 1035.

Now I learned that a multiplicative inverse only exists if the gcd of two numbers is 1. Thus, there doesn't exist a multiplicative inverse for n = 1023, 1034, 1035 because there gcd's are not 1.

gcd(33, 1023) = 33
gcd(33, 1033) = 1
gcd(33, 1034) = 11
gcd(33, 1035) = 3

So we move forward with n = 1033 using the Euclidean Algorithm:

33x = 1 mod 1033
  x = 1/33 mod 1033
  x = 1033 = 33 * 31 + 10
  x = 33   = 10 * 3  + 3
  x = 10   = 3  * 3  + 1
  x = 1

Now we work our way back up using the Extended Euclidean Algorithm

//EEA
1 = 10 + 3(-3)
  = 10 + (33 + 10(-3))(-3)
  = 33(-3) + 10(10)
  = 33(-3) + (1033 + 33(-31))(10)
1 = 33(-313) + 1033(10)

So now how do we get the multiplicative inverse from this final equation that we have here?

Also, I used this video as a reference to running through EA and EEA: https://www.youtube.com/watch?v=hB34-GSDT3k and I was wondering how he was able to use EEA when his gcd was 6, and not 1?

Answer 1

From the last line of your calculation $1 = 33(-313) + 1033(10)$, reduce mod $1033$ to see that

$$ 1 \equiv 33(-313) \pmod{1033}. $$

So the inverse of $33$ modulo $1033$ is the equivalence class of $-313$, the least non-negative representative of which is $-313+1033 = 720$.

Answer 2

Here is a layout for the Extended Euclidean algorithm, so you don't haveto go back through the successive divisions. It is based on the fact that not only the g.c.d. (last non-zero remainder in the successive divisions) satisfies a Bézout relation, but all successive remainders, hence these coefficients are computed recursively:

\begin{array}[t]{l@{\qquad}rrrr} \text{Successive Divisions}& r_i & u_i & v_i & q_i\\ \hline & 1033 & 0 & 1 & \\ 1033= \color{red}{31} \times 33 +\color{blue}{10} & 33 &1 & 0 & \color{red}{31} \\ \hline 33 = {\color{red}3} \times 10 + \color{blue}{3} & \color{blue}{10} & -31 & 1 & \color{red}3 \\ 10 = {\color{red}3} \times 3 + \color{blue}{1} & \color{blue}{3} & 94 & -3 & \color{red}3 \\ & \color{blue}{1} & -313 & 10& \color{red}0 \\ \hline \end{array} From this we know the inverse of $33$ modulo $1033$ is $\;-313\equiv 720\mod 1033$.