Extended Euclidean Algorithm and Inverse Modulo Tutorial

Using EA and EEA to solve inverse mod.

[@callofdutyfanboy555]

how did i get from call of duty to this?

[@raymondpang3896]

+callofduty fanboy999 The words "EA" and "mod" exist in the video description And those words are also related to video games :)

[@davidakoji3696]

@@raymondpang3896 wow mad!!

[@sangeethjoseph1995]

@@raymondpang3896 Nerdiest man ever!!

[@banoshreebose2682]

its a curse (goodluck you are heading towards some fun times)

[@aswinraj1284]

@@raymondpang3896 I wanted to upvote but didnt want to make it 70

[@iamaboss2528]

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.

[@crow4505]

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.

[@SmartTactics101]

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

[@cosymarissa]

same!

[@sudhanshusaini504]

hope someone will teach you the past form of teach

[@GeekUpdates]

In one min kzbin.info/www/bejne/oZeYpHSklLqHY9k

[@coolbrampton]

you moron you can't even learn the english language correctly, let alone discrete mathematics. fuck you, ruined my day just like that.

[@GeekUpdates]

Doomlad me??

[@-INK-]

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

[@jakeneylon1853]

not saying much XD

[@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.

[@niyatich7621]

My teacher is a shit!🙂 X'cuse me Lady,, can you come to my college 😒

[@t.lnnnnx]

i love you for that

[@kyletanyente6149]

Can you solve 80-¹(mod 171) My teacher is not good like you

[@kyletanyente6149]

12/10/21 hope you'll notice this ma'am

[@mastermind2971]

@@kyletanyente6149 8 yrs ago lol good luck

[@CyberCatto]

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

[@abdulrahmanmuhammad731]

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

[@haiass4725]

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

[@ayanabedin7611]

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

[@neomincerneo7616]

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

[@gg1bbs]

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

[@JahedShaikh]

Even our P. HD professor can not teach like this. Teaching is a art 🎨. And you have it. Congrats

[@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!

[@91099Babar]

How come 38 is obtained ,plz show ???

[@mishasharma3656]

43-5

[@renegirard2173]

Perhaps another way to obtain the "38" is to recall that q*43 = 0 (mod 43) for any integer "q" as she did in the video when she set 2*43 = 0 (mod 43). So adding on both sides of equation 1 = 2*43 +(-5)*17 the term 17*43 = 0 (mod 43) we obtain 1+17*43 = 1+0 = 2*43+(-5)*17 + 43*17= 0+(43-5)*17 = 38*17. So we get the desired result 38*17 = 1 (mod 43).

[@DanielPerez-kz2ec]

Think of it as -5 + 43 =38 since you can’t have a negative remainder

[@readward2572]

Your explanation is different from my textbook but I like your way of finding out the solution. Some KZbin 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.

[@user-bp7oo2yz4i]

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

[@durgar9755]

I have a doubt from elgmmal when recoving the key I got key value as 7 and when taking inverse for key value it gets 11. I still couldn't understand how it goes?.... it says the concept follows extended euclidean algorithm help me

[@PankajKumar6493]

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

[@durgar9755]

I have a doubt from elgmmal when recoving the key I got key value as 7 and when taking inverse for key value it gets 11. I still couldn't understand how it goes?.... it says the concept follows extended euclidean algorithm... help me

[@bobjones5869]

Durga R did you get it?

[@PiriyaSambandaraksa]

thank you, you have explained what i have been trying to understand for weeks in a few minutes.

[@ZirJohn]

Thank you. Im in a 6 week discrete math class and im really not understanding things because the professor just flies by everything. This helps!

[@peyuaa9203]

I'm glad that videos like this exist on KZbin.

[@sanvedlop]

Finally a non Indian video with clear explanation of what happens instead of a really thick accent. Thanks for making this !

[@chargeittothegame3253]

This is a great video. The process is long, but you explained everything so perfectly. Thank you.

[@christiancoder454]

This is the best explanation I have came by thus far. Thank you friend.

[@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.

[@apoorvkala6381]

The best and most easy explanation so far! Kudos to you! Thank you for bringing the red color as well

[@user-ig8hq6op6o]

by far the best explanation on modular inverse! thank you so much

[@Udinanon]

This is worth 10 points on my tuesday exam, thank you so much

[@rawool]

Lovely voice, clear explanation. Thanks!

[@biplavpoudel]

After watching your video twice, I finally understood this. Tysm!

[@xxsarah52009xx]

Talented, brilliant, incredible, amazing, show stopping, spectacular, never the same, totally unique saved my life

[@haniakhalidshariff4573]

i didnt understand why u got 38

[@johnchang8279]

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.

[@bwp2bruce]

And how would you do that if you have d ≡ (1/65537) (mod 7275919392).

[@altairezio6850]

Thank you very much, miss Emily! I just watched your video and instantly was able to solve it on my own. I hope you have a great day!

[@alihassan5651]

So helpful it was 7 years ago wao what a simple explanation..:) Why did youstop making videos they are very helpful to students.

[@bonginhlanhlangema7125]

Abantu bezibalo bayathanda ukusiqhumisa amakhanda ngamabomu ugcine ungasizakalanga. Ngiyabonga Dadewethu. That's Zulu, which translates to Mathematicians are so condescending, thank you so much for this simple explanation my sister.

[@VFXCommander]

I like your hand writing. Perfect video!

[@ahmedmustafa4501]

I don't understand the rule you have applied to get -5 in that simplification

[@RealKalleAnka]

You should make more videos like this Emily, seriously.

[@Mavers49]

This was the explanation I needed to clarify the final step and it all makes sense now :) thanks a lot :)

[@emaldonado001]

I just spent two weeks on this. Thank you.

[@DerGizmoKanal]

Go to 2:45 and turn the subtitles on. :)

[@KaustubhGhanekar]

+Finian Zeps LoL... how? oh Google...!

[@steveandrews2121]

+Finian Zeps It's the Aussie accent... wow youtube/google need to lift there game o.O

[@steveandrews2121]

+Finian Zeps It's the Aussie accent... wow youtube/google need to lift there game o.O

[@evanmastermind]

One year later and the subtitles are great.

[@yatin9403]

brilliant explanation! And love the voice, very soothing!

[@Mikelectric]

I love the sound the pen makes

[@wills2537]

Very helpful video and a fit voice. Win win.

[@swetaswabasak6191]

yo...I love u maa g....ur stupendous ... thanks a lot for the explanation.....hv been scavenging youtube for over an hr till I found yours🥰

[@dsanchomariaca]

You litterally saved me from a catrophe

[@cecileinhighheels]

Hi Emily! Thanks for making this video, I found it really helpful while studying for a discrete math exam. I had a question: how did you orient your camera to capture this? I was trying to make a math video but I was getting stuck how to set up the camera.

[@EmDickinson]

Hahah I used the super professional method of balancing my iphone over the edge of a big stack of books.

[@louis-marcmercier5730]

A short, sharp and very well explained tutorial. Thank you! :)

[@adillion7362]

Brilliantly explained! Helped me out a lot with my assignment, much thanks

[@gurvirsandhar6295]

what if instead of having congruent to 1(mod n) you have a different value for one? I'm trying the solve 3x congruent to 17(mod 20). So I would have to find the inverse of 3 to get x by itself. Or at least thats how I think i'm supposed to do it.

[@EmDickinson]

Nah just find the answer like normal and multiply the final solution by 3 and take the mod again. Easy peasy.

[@laurietsao8733]

In this case, 17 = -3 (mod 20), so 3x = -3 (mod 20), and x=-1(mod 20). Add 20 to get 19.

[@lakshmivijay3857]

Omg thank you so much, I was struggling with this for so long!!!

[@thepickicool97]

YOU SAVED MY LIFE !!!!!! I LOVE YOU AND THANK YOU !!! 🙌🏾🙌🏾🙌🏾

[@SnGrg]

such a clear explanation Emily. Thank you

[@masabahsaeed]

YOU'RE A LIFE SAVER!

[@nausherofficial]

i like the way you hold the pen.

[@alitokur2729]

the best famous person ı've ever seen. thanks for my midterm.

[@sagarakaraavan]

Thanks for the explanation...I must say you are a great teacher

[@SwissExperiments]

AHHH finally one video that made me snap! Thank you for taking your time and explaining step by step what you do! I'm curious about one thing: What is your field of study?

[@lifeandprimes]

I'm studying a bachelor of teaching and a bachelor of science with a major in mathematical modelling and a minor in biological chemistry.

[@faisalwaqas1963]

great ...today is my cryptography paper ..u done a reat job for me ...best wishes

[@thomassheldon2365]

Thank you for such a straightforward explanation! This was really helpful👍

[@Goldie3Gaming]

i have a crypto exam in a couple days. thank you so much

[@yO_o.velin0va]

First, I would like to say that the explanation is great and the video really helped me with solving my problem, since I've been surfing throughout the internet for the past hour or so searching for a decent and clear explanation of how to do this :D I have a question, though - in this case 1 is on the right side, what if it were to be 3 or any other number? As in, for example, 17x congruent to 3 (mod 43) (doesn't matter, if this exists or not, I'm just giving it as an example to explain what I want to say, because I find no other way of saying it xD), so does that mean that the gcd of 17 and 43 has to be 3?

[@EmDickinson]

Good question! The number on the right can be any number. Because when you take 17 across to the right side you get (in your example) x = 3/17 (mod 43). Another way of writing this is x = 1/17 multiplied by 3 (mod 43). So you work out the 1/17 (mod 43) bit, which in the video equals 38. Then you multiply 38 by 3, which equals 114. 114 mod 43 is 28. Therefore 17x = 3 (mod 43) equals 28. The gcd always has to be 1, no matter what number is on the right side of the equation.

[@yO_o.velin0va]

Emily Scott Thanks! Your video helped me shitton for my exam on Thursday! : ))))

[@fastest1321]

What happened in that last step? where's 17 go and where did 38 come from?

[@Jdiddy1792]

At the very beginning x = 1/17 mod 43, so your final answer should be 1/17 Note 17^-1 is 1/17 so, 1 = -5 * 17 1/17 = -5 Then because you have a negative number you subtract from 43, 43-5 = 38 Note if you got +5, then the answer is 5.

[@lifeandprimes]

Yeah, when you finish the extended euclidean algorithm, you'll get something being multiplied by the mod number (which you can cross out) and something multiplied by the inverse number (which is the answer). The answer was -5, but it has to be between 0 and 42. So -5 + 43 = 38

[@durgar9755]

@@Jdiddy1792 I have a doubt from elgmmal when recoving the key I got key value as 7 and when taking inverse for key value it gets 11. I still couldn't understand how it goes?.... it says the concept follows extended euclidean algorithm help me

[@durgar9755]

@@lifeandprimes I have a doubt from elgmmal when recoving the key I got key value as 7 and when taking inverse for key value it gets 11. I still couldn't understand how it goes?.... it says the concept follows extended euclidean algorithm help me

[@krishnaMurari48]

why didn't i watched this when i was in college . thanks :-)

[@Jalagarn_kayyalli_keysbidthini]

Thank you so much. It helped me top my cryptography exam.

[@funnywaves8765]

Not good for begginers

[@nIrUbU01]

THIS IS NOT HOW YOU WRITE AN X!

[@pradeepraghuraman4430]

Thanks a lot! Your video explanation really helped for my exam preparation.

[@aseemahir]

What a wonderful video! How nicely explained! Thank you

[@nasimibrahim1217]

Such a great explanation, thank you so much ,much needed it.keep it up like this

[@jonatansvensson8346]

Just curious, at the very end shouldn’t it be x is equivalente to 38 and not x is equal to 38? Great video btw!

[@gursevaksingh2504]

thanks, I was confused about negative answer.

[@pratikbista5345]

Damn with this video the Bezout theorem makes sense too and now i understood this algorithm helps to understand that too :))

[@1234s6]

Your voice is so sweet :)

[@Vistorri]

This helped me. I wasn't after a wikipedia-like explanation so this was ideal.

[@chris_the_scientist]

Thank you Emily Scott this was a great help!

[@yifuxero5408]

Here's a much faster & easier method. Given 17/43, write out the continued fraction representation (partial quotients) = [2, 1, 1, 8]. Underneath, write the convergents, = [1/2, 1/3, 2/5 17/43]. For an even number of partial quotients [2, 1, 1, 8] = four, access the rightmost denominator in the convergent row = 43, and subtract the next denominator to the left (5), giving 38, the answer. If the number of convergents is odd, the answer is the denominator to the left. Example: find 2*x = 1 mod 5. Our setup is [2, 1, 1] with convergents [1/2, 1/3, 2/5] Ans is 3. since 2*3 = 6 = 1 mod 5.

[@jkli6031]

The answer is equal to (43+1)/17*2*(-1)^3 (mod 43, round up) = 38 appreciate

[@jianingzhuang104]

Nice video! Helped me in my course assignment.

[@YuNgHaSaN]

Why would you add this many equations man? This is extremly frustrating. Just make the equation simple instead of adding more equations like 1 = 9 - (17-9) 1 = 9 - 17+9 1 = 2 x 9 - 17 It's ridiculous. I don't understand how people are commenting ah thank you made this easier. Just make it simple.

[@EmDickinson]

I do that so I don’t make any mistakes. It makes it easier for me. I’m sorry that you are frustrated, I hope you have a better day tomorrow.

[@katashi1995]

Thank you for the video! Why do we bring down the 17 and 9? why not the 2?

[@slaozeren8742]

I love you and sending you corona-proof hugs from Turkey

[@spiz02930]

therapeutic voice

[@Synarite]

Very helpful and easy to understand. Thanks!

[@ismailrashid9761]

thanks a lot , I was confused with the minus answer you subtract and got the inverse .

[@elpidiopiscosiii6435]

Hello Emily. Whats the difference between (17)^-1(mod43) and 43^-1(mod17)? I think what you just solved in the video is the latter. Correct me if i'm wrong.

[@lifeandprimes]

I did 17^-1 (mod 43) in this video. They use the same process except when you get to the end of the Extended Euclidean Algorithm. 1 = 2x43 - 5x17 If you are doing 43^-1 (mod 17) instead, you will cross out the -5x17 and your answer will be the number multiplied by 43, which in this case is 2. So 43^-1 (mod 17) = 2. Hope this helped!

[@elpidiopiscosiii6435]

Emily Jane Thanks Emily.

[@tugboathk]

Good stuff. I actually refer to this video when I did RSA in Cryptography Class. Which uni are you from?

[@lifeandprimes]

I go to Deakin Uni in Melbourne. I actually run a Cryptography tutorial there now!

[@tugboathk]

Emily Scott Nice! I'm from RMIT (BCompSci)! Melburn represent!

[@uzeyirveli]

thanks for the nice video but there is one thing I want to point out. In the beginning you divide both sides by 19 even though there is a congruence symbol in the middle. I think that is not allowed and leads to wrong answers.

[@MaximoBrazil2000]

Thank you Emily Scott, you are an angel...

[@qiji3309]

thank you a lot for this brief video! :)

[@akshatjain671]

thanks a lot for the video, it helped me in my exams!! :D

[@sumanthns1538]

Thank you Emily Jane..Keep up the good work

[@technical3182]

Like the way you hold the pen

[@Hitokage]

Thank you very much!

[@rajatsharma3335]

Why is anything multiplied to mod 43=0

[@vighnesh153]

What would you do if the numbers were way larger than 17 & 43? It wouldn't be feasible to do that using euclidean algorithms as it would have way many steps..... So, is there any other method that helps us deal with large numbers? By the way, the tutorial was excellent.....

[@lifeandprimes]

Vighnesh Raut Actually it just depends on the numbers. Even some really large numbers might have only 2 or 3 steps. It's not necessarily that larger numbers have more steps!

[@miltonsegura]

It's just what I was looking for, thanks.

[@Meta-Drew]

Anyone who uses a 4-in-1 pen is cool in my book