0
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ The EEA always works to find the GCD. It's just not helpful for finding inverses when the GCD isn't $1$. $\endgroup$ – pjs36 Oct 12 '15 at 19:33
2
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.