Modular inverse made easy

[@RandellHeyman]

If you having trouble with step 2 have a look at kzbin.info/www/bejne/jnurhWudpMitqaM

[@st1tch525]

I learned more in these four minutes than my college professor taught me in a week... THANK YOU!!!

[@SemihFatihAdem]

i want to touch an important point of this algorithm. When u go inverse, you changing NEXT SUB numbers and ONLY in parenthesis. Look upper eq, sub again[ 11=1(6)+5 goes 5=11-1(6) ] and put eq in the parenthesis. 1 = 6 - 1(5) --->> 1 = 6 - 1( 11-1(6) ) distrubute ( - ) and simplify 1= 6 - 11 + (6) -->> 1= 2(6)-11

[@ameliasaidwhat]

Short and sweet, very helpful video. Never learned this exactly in class just the definition so this was great.

[@TayoEXE]

I still don't quite understand what the gcd has to do with finding the modular inverse, but I have been racking my brains for hours now trying to understand this, and you're the only one who gave a nice concise answer and helped me with my homework, so thank you.

[@RandellHeyman]

Glad it helped.

[@yann8442]

My whole class is thanking you for the explanations!

[@RandellHeyman]

Glad it helped. I have other related videos...modular arithmetic made easy, modular exponentiation made easy, euler's theorem made easy, fermat's little theorem made easy and RSA code made easy.

[@MC-Minority]

0:44 3000 = 15(197) + 45 3000 div 197 = 15 3000 mod 197 = 3000 - (197 *15) = 45 2:05 Left side of video 6 = 1(5) + 1 (solve for 1) 6 -1(5) = 1 1 = 6 - 1(5) (just switched sides, now it looks like the top right) Now get rid of the 5 from this equation So we work with the 2nd last equation on the left side 11 = 1(6) + 5 5 = 11 - 1(6) Now plug into [5 = 11 - 1(6)] into [1 = 6 - 1(5)] 1 = 6 - 1(5) 1 = 6 - 1(-1(6) +11) 1 = 6 +6 - 11 1 = 2(6) - 11 Repeat the process one more time Use the 3rd last equation on the left side and isolate 6 17 = 1(11) + 6 17 - 1(11) = 6 6 = 17 - 1(11) [re-expressed the equation] Plug [6 = 17 - 1(11) ] into the 2nd equation on the right side [1 = 2(6) - 11 ] 1 = 2(6) - 11 1 = 2(17 -1(11)) - 11 1 = 2(17) -2(11) - 11 let a = 11 1 = 2(17) -2a - a 1 = 2(17) -3a 1 = 2(17) - 3(11) Hopefully, that helps, that was too much mental arithmetic going on for me 🤣😭

[@michaelcoughlan7757]

By far the easiest tutorial to follow! Thanks a million!

[@RandellHeyman]

+Michael Liam Coughlan Glad it helped.

[@thomasgardner838]

Hi Michael, weird question but wondering what you are doing now five years later?

[@michaelcoughlan7757]

Hi @@thomasgardner838 I'm contracting as a software engineer :)

[@tombardier]

Thank you. I've been running through these procedures, just with no actual intuition for them. I feel like I have a bit more insight now!

[@RandellHeyman]

Great. Thanks for letting me know.

[@johallyw3]

Really well explained and easy to understand!

[@tosscoin2206]

Incredibly helpful. Thank you

[@DaveandEm2000]

Again, thanks for making these videos. Much easier to understand than my textbook.

[@RandellHeyman]

Thanks for the positive feedback. Glad it made is easier for you.

[@snake1625b]

so if the GCD of two numbers is not 1 then there is no multiplicative inverse

[@RandellHeyman]

John Fernandez That is correct. Well done on working that out from the video :)

[@mage1over137]

John Fernandez Welcome to fascinating world of Ring.

[@snake1625b]

mage davee what are rings in a nutshell

[@mage1over137]

John Fernandez Are you Familiar with Groups, and if yes what about Fields?

[@lethargicastengah572]

+mage davee I am. Continue?

[@nikhilmadaan29]

Thanks for the effort. Much appreciated!!

[@ravishkumar8422]

thanks for the video, there are many videos on this topic but your video is the easiest one to grab, nice explanation.

[@RandellHeyman]

Thanks.

[@bulat3226]

Great tutorial, Thank You!

[@AmolGautam]

Holy shit dude. You are a fucking genius , never thought there was an algorithm to calculate the modular inverse for such a large number. Would have used 3 years ago to simplify cryptographic calculation. but yeah , i can use it now as well.

[@RandellHeyman]

I'd be a genius if I'd worked it worked it out first. But Euler largely gets the credit, not me.

[@melissamarlen1022]

Wow thank you so much! Great Video!!

[@RandellHeyman]

Thanks.

[@eatfruitsalad345]

This isn't working for me for some reason. I'm trying to find the inverse of 5 (mod 16) which using Euclid's becomes 16 = 3(5) + 1. The actual inverse is 13 but I don't see how to get 13 from that.

[@eatfruitsalad345]

Actually, I figured it out. When on the second step you get 1 = 16 + (-3)(5), which means that the inverse is -3, or 13. Thanks for the video!

[@RandellHeyman]

Glad you worked it out. It's a common mistake to get thrown by a negative. Other related videos on modular arithmetic, modular exponentiation, fermat's little theorem, Euler's theorem and RSA code on my channel.

[@christiancoder454]

Wonderful explanation. Thank you for your time and help!

[@RandellHeyman]

I've got lots of related videos (eg modular exponentiation made easy, Chinese remainder theorem made easy) on my channel.

[@The_Patbey]

Thanks, great video even in 2020!

[@RandellHeyman]

Thanks for the positive feedback. Interestingly, for quite old videos, my views seem to be increasing this year.

[@thatsthething3218]

Why the hell it is not explained in detail at university? Glad saw this.

[@sandraa1234]

Why did my teacher just skip to teach this bit? Thank you for a good video.

[@RandellHeyman]

Glad it was helpful!

[@cupoftea6196]

this made so much sense!!! thank you!

[@SaiBharatBatchu]

This one video made me to subscribe to your channel :)

[@lalwho]

beautifully explained...

[@91099Babar]

You have done a mistake on the 3rd Step of Extended Euclidean GCD Solution .... it is not -3(11) ... The Step is as follows : Equation available : 1 = 2X6 - 1X11 Step 3 to sub : 6 =17 -1X11 1 = 2X( 17 - 1X11 ) - 1X11 . Now Simplify : 1 = 2X17 - 1X11 - 1X11 1 = 2X17 - 2 X 11 .....How come - 3X11 get in your 3rd Step ???

[@Enceptics]

Very helpful, as always!

[@RandellHeyman]

Thanks for the feedback; much appreciated.

[@snoopdogg7363]

Randell Heyman Are you able to do/explain the CORDIC algorithm? I've always wondered how calculators can compute sin/cos/tan;

[@RandellHeyman]

snoop dogg The usual method for explaining how calculators do trigonometry is that they use Taylor series. I explain this in the video Taylor series made easy. But I think you are correct is saying that small calculators actually use something like the Cordic algorithm.

[@JonathanSebastianS]

I wanna ask for the term of gcd is one, is this term for two problems above or just for modular multiplicative invers?

[@eduardoxenofonte4004]

I didn't get step 2

[@RandellHeyman]

Hi Eduardo, many people have asked me about this step over the years. I will try to upload a video explaining further this afternoon.

[@RandellHeyman]

Hi again. Have a look at kzbin.info/www/bejne/jnurhWudpMitqaM

[@lemonke8132]

Am i missing something or does this simply not work for 4^-1 mod 999? You get 83(4) + 3, but 83 mod 3 is zero. The GCD of 4 and 999 is definitely one though.

[@RandellHeyman]

999=249(4)+3 and then 4=1(3)+1. So gcd(999,4)=1.

[@lemonke8132]

@@RandellHeyman oh snap thanks

[@shloksand2926]

Thanks a lot man ....the video was excellent

[@RandellHeyman]

Thanks. Lots of related videos in my university mathematics playlist, my corona help - discrete mathematics playlist and my corona help - euler's theorem playlist.

[@shloksand2926]

Just what I was looking for

[@shloksand2926]

Randell ,could u also add a proof of Fermats last theorem

[@RandellHeyman]

@@shloksand2926 I have a video intro proof fermat's last theorem. I can do a bit more on elliptic curves and modular forms. That's about as far as I'll go.

[@shloksand2926]

Ok thx

[@ahmedshokry7963]

Really Helpful ! thanks alot

[@AnanthiRamasamy]

A Great Video :) Thanks a lot for sharing

[@alexanderhamilton35]

Why is there no inverse if the gcd isn’t 1? I’m fairly new to modular arithmetic, any explanation would be appreciated :P

[@RandellHeyman]

I'll try to upload a video on thjs question in the next 24 hours.

[@simonarcher4445]

Thanks a bunch.

[@floatingyunsan]

How do I substitute?

[@RandellHeyman]

See my pinned comment.

[@cindylee6249]

Thank you so much! but what if the former number is bigger than the latter number? like 135 mod 61, thanks!

[@RandellHeyman]

Hi, I'll upload an explanation video in the next 5 minutes.

[@cindylee6249]

@@RandellHeyman thank you so much! I'm looking forward to it!

[@gamedit2999]

Here is the video about it: kzbin.info/www/bejne/rZ_XomyeqKaVa5o

[@intensiveadvancedmath5281]

Thank you very much, that's usefull

[@RandellHeyman]

Thanks for commenting.

[@mohammedsamymohammedabdeln2304]

that's pretty easy thanks alot

[@kianpopat9829]

Is it any different to find the multiplicative inverse of 3000 modulo 197, i get the wrong number when i try this with a bigger number modulo a smaller one

[@eduardoxenofonte4004]

you can't work outside the module, if its module 197 you can only work with 0-196

[@Mayzaf14]

Thank you SO much. :)

[@RandellHeyman]

I'm glad it helped.

[@abraxzus1876]

Hi, If it were (197)^-2 instead how would this change? Would it just be solve : 197^2 * d = 1 mod 3000 ?

[@RandellHeyman]

Yes. Then you would use the fact that 197^2 = 2809 modulo 3000. So now solve 2809 d = 1 modulo 3000.

[@levibrian10]

I FUCKING LOVE YOU.

[@sagarakaraavan]

Thanks a lot mate...made my day...

[@mkerm3875]

i will just drop this here

[@dcrock8978]

2:25 you pointed at the wrong line, otherwise nice work

[@RandellHeyman]

Thanks for pointing out the error in my pointing out.

[@johnarchibald9202]

THIS MAN IS MY SAVIOR

[@RandellHeyman]

Good to know :)

[@georges.154]

how are the expressions 1=(triple equation) 533(197)(mod3000) and 197d=1mod3000 the same???? That's what I don't understand. 1mod3000 is just 1. Not 197*533

[@RandellHeyman]

When I write 197d = 1 mod 3000 I really should have written 197d=1 (mod 3000). And also they should have a three line `equal sign' not the normal two lines. But what this means is that 197d is equal to a number that has a remainder of 1 when divided by 3000. If 197d=1 (mod 3000) and 197(533)=1 (mod 3000) then the value of d between 1 and 3000 is 533. Hope that helps.

[@luistan7429]

Hello, I'm trying to find the modular inverse of 7 mod 120 and I get 17 which is I think wrong. I think it should be 103. But using the extended eucledian algorithm, I get 17. Is that correct?

[@RandellHeyman]

It is easy to check if either is correct. 7 x 17 is equivalent to -1 mod 120. So 17 is not the inverse. On the other hand 7 x 103 = 721 = 1 mod 120. So the answer is 103. You must be doing something wrong with the extended Euclidean algorithm. Hope that helps.

[@Alexander25i]

Thanks a lot!

[@dg6546]

extended euclidean algorithm

[@RandellHeyman]

See my video I uploaded 1 hr ago

[@andyjiao3114]

Is 533 the only answer?

[@RandellHeyman]

Any number that is equivalent to 533 modulo 3000 is a valid inverse. For example, 3533 times 197 = 696001 which is equivalent to 1 modulo 3000.

[@andyjiao3114]

+Randell Heyman Thanks

[@91099Babar]

You have done a mistake on the 3rd Step of Extended Euclidean GCD Solution .... it is not -3(11) ... The Step is as follows : Equation available : 1 = 2X6 - 1X11 Step 3 to sub : 6 =17 -1X11 1 = 2X( 17 - 1X11 ) - 1X11 . Now Simplify : 1 = 2X17 - 1X11 - 1X11 1 = 2X17 - 2 X 11 .....How come - 3X11 get in your 3rd Step ???

[@larubiano0]

Thank you dude

[@RandellHeyman]

Thanks for letting me know.

[@ayepyone7398]

Nice explanation

[@karlchami4740]

substitute this to that to this to that to that to this like be clearer!!!!

[@sadimannan7248]

Awesome

[@Summer2monsoon]

u are too good loved ur video hats off :)

[@parvbhardwaj9188]

great!!

[@okoyemildred8720]

This wasn't made easy at all...the part after Euclid's alogrithm 😭😭 please help me

[@okoyemildred8720]

Oh... don't worry, I've seen the other video 😊

[@RandellHeyman]

@@okoyemildred8720 Great. Any further problems...let me know.

[@okoyemildred8720]

@@RandellHeyman i will...thank you so much, you've been of much help to me and my brothers💙

[@nathwhite5119]

thanks!

[@haniakhalidshariff4573]

I DIDNT GET PART 2

[@RandellHeyman]

Have a look at my video Euclid's algorithm made easy. If you still have problems comment again.

[@cs2c_gabardaangelob.88]

thank youu i get it noww,

[@RandellHeyman]

Great. Thanks for commenting.

[@nBodyResearch]

im sorry lol but how can anyone say this is a good explanation?? he just says substitute this line with this line?? like which part do i substitute with what lol

[@RandellHeyman]

Sorry you couldn't understand. There are of course other videos that might be better for you. Otherwise.... You are probably getting stuck around the 2 min mark. On the right hand side I show my workings to express 1 as the difference between multiples of 3000 and 197. From the last line on the left I have 6=1(5)+1. This means that 1=6-1(5). So I write that on the right. Now I want to get rid of that multiple of 5. To do that I look at the second last line on the left. This is 11=1(6)+5. This means that 5=11-1(6). So I can replace 5 in the first line on the right with 11-1(6). So then I get 1=6-1(11-1(6)). This means 1=2(6)-1(11), which is 2nd line on the right. Next I want to replace 2(6). To do this I use the 3rd last line on the left. This continues until I get to the last line on the right side.

[@nBodyResearch]

@@RandellHeyman ahhh cool, thanks

[@91099Babar]

You have done a mistake on the 3rd Step of Extended Euclidean GCD Solution .... it is not -3(11) ... The Step is as follows : Equation available : 1 = 2X6 - 1X11 Step 3 to sub : 6 =17 -1X11 1 = 2X( 17 - 1X11 ) - 1X11 . Now Simplify : 1 = 2X17 - 1X11 - 1X11 1 = 2X17 - 2 X 11 .....How come - 3X11 get in your 3rd Step ???

[@RandellHeyman]

In the second line you should have 1 = 2x17-2x11-1x11.:)

[@91099Babar]

Randell Heyman Ty very much ,few moments later I had corrected as I reviewed the steps .

[@randallhale7775]

Hey man

[@cristianmalvaro3362]

worst method, doesnt work with big numbers

[@RandellHeyman]

+cristianm alvaro Sorry I don't understand your comment. This method will work for big numbers.

[@hearts33d]

paaaaiiiiiiiiiiiiiiiiiiiiiin

[@RandellHeyman]

Watch my other video modular arithmetic made easy and the paaiin should subside a little.

[@pratikmehta6207]

on google (1/197)mod3000 is something like .... 0.00507614213 ...ur ans is like 533... what is correct thing..

[@RandellHeyman]

I think Google has just given you the answer in decimal form that you would work out in lower higher school....nothing to do with modular arithmetic.