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$.
No comments:
Post a Comment