elementary number theory - Extended Euclidean Algorithm, what is our answer?

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

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