Extended Euclidean Algorithm and Inverse Modulo Tutorial

Using EA and EEA to solve inverse mod.

[crow]

I know this video is from 7 years ago but it is insanely helpful. Answered a lot of uncertainties! If you ever see this, thank you a lot.

[callofdutyfanboy]

how did i get from call of duty to this?

[iamaboss]

I'm not going to say that my professor doesn't know how to explain or teach, but the way you did it was beautiful. Thank you a lot Emily.

[prikshit]

You are much much better than my cryptography teacher. 
He would have taken atleast 2 hours to explain this simple concept.

Thanks Emily for this great lecture.

[-INK-]

The most clear explanation of this topic on YouTube! Thank you very much.

[EmDickinson]

You always wanted your Euclidean Algorithm in the form a x b + c. So you start off by using the 43 and the 17 that are in the question. 17 goes into 43 two times with 9 remainder. Therefore 43 = 17 x 2 + 9.
Hope that helps.

[EmDickinson]

Because it's mod 43, you want your final answer to be mod 43 as well (ie. between 0 and 42).
So it's -5 + 43 = 38.

[SmartTactics]

In 5 minutes you taught me more than my professor could do in 5 hours. Thanks :)

[CyberCatto]

you just destroyed my professor's whole career in 5 minutes and 59 seconds

[ggbbs]

Great explanation, clear and concise. That was a massive help studding for my end of semester exams!

[neomincerneo]

Probably the best explanation I have ever seen. Well done!

[EmDickinson]

Al Amin When working mod 43, your answer has to be between 0 and 42. In this example, the answer is -5, which is equivalent to 38 (mod 43). You couldn't say the answer is 37, because it has to be a multiple of 43 (ie. you just add or subtract x lots of 43 until you get a number between 0 and 42).
-5 (mod43) and 38 (mod43)  is also equivalent to 81 (mod43), 124 (mod 43), -48 (mod 43), -91 (mod 43) etc, because when you add or subtract multiples of 43, the answer is always 38.
I hope this helps!

[PankajKumar]

Thank you Emily for such a clear explanation through an example.  Helped me in preparing for the Cryptography exam.

[ayanabedin]

In such a short time, you explained it very well. I was surfing all over the Internet and couldn't find a proper one. Thanks a lot...!!!

[readward]

Your explanation is different from my textbook but I like your way of finding out the solution. Some YouTube makers use so much fancy technology into their video that I get annoyed. Your video is good and just right to the point. Thank you.

[johnchang]

For hand computation, using modular arithmetic is 5-10x faster than using the extended Euclidean algorithm. 17x ≡ 1 mod 43. I want to add a multiple of 43 to 1 so that the sum is a multiple of 17. That way I can divide by 17 to solve for x. Since 43 ≡ 9 mod 17, and 1 + -2 * 9 = -17, it follows that 17x ≡ 1 - 2*43 ≡ -85 (mod 43). Dividing both sides by 17 then gives x ≡ -5 mod 43.

[abdulrahmanmuhammad]

You just taught me a 4 hour math lecture in 6 minutes. Thank you very much.

[JeanDoeShow]

First of all, thank you very much for the explanation (it sure has helped me in figuring out inverse). But I do have a question. Most of the time I do the subtract part that you do in the ending (the - 5 mod 38 bit).. but I have come across a few examples where this is not needed.. and I cannot explain why. I have an example here (where I have to find the inverse of 12 mod 3079):

3079 = 12 x 256 + 7
12 = 7 x 1 + 5
7 = 5 x 1 + 2
5 = 2 x 2 +1


1 = 5 – 2 x 2
Sub. 2 = 7 – 5
1 = 5 – (7 – 5) x 2
1 = 5 – 7 + 5 x 2
1 = 3 x 5 – 7 x 2
Sub. 5 = 12 – 7
1 = 3 x (12 – 7) – 7 x 2
1 = 3 x 12 – 7 + 7 x 2
1 = 3 x 12 – 7 x 5
Sub. 7 = 3079 – 12 x 256
1 = 3 x 12 – (3079 – 12 x 256) x 5
1 = 3 x 12 – 3079 + 12 x 256 x 5
1 = 1283 x 12 – 3079 x 5

Apparently, 1283 is already the inverse of 12 and substraction is not needed. Could you give me a good example so I can see when I do need to do the substraction and in which situations I do not have to do that step?

Thanks a bunch, Emily! And thanks again for the vid, been very helpful.

[いぬとかねことか]

this legit dissolved my worries so quickly. incredibly satisfying, thanks

[haiass]

I've been like 3 hours trying to find a good tutorial about this. I love you