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
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.
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.
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 🤣😭
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.
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.
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.
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.
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.
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
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 ???
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 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.
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?
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.
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
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.
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 ???
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 ???
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
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.
If you having trouble with step 2 have a look at th-cam.com/video/XJHT8goczsA/w-d-xo.html
I learned more in these four minutes than my college professor taught me in a week... THANK YOU!!!
Short and sweet, very helpful video. Never learned this exactly in class just the definition so this was great.
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
My whole class is thanking you for the explanations!
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.
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.
Glad it helped.
By far the easiest tutorial to follow! Thanks a million!
+Michael Liam Coughlan Glad it helped.
Hi Michael, weird question but wondering what you are doing now five years later?
Hi @@thomasgardner838 I'm contracting as a software engineer :)
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 🤣😭
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!
Great. Thanks for letting me know.
Again, thanks for making these videos. Much easier to understand than my textbook.
Thanks for the positive feedback. Glad it made is easier for you.
thanks for the video, there are many videos on this topic but your video is the easiest one to grab, nice explanation.
Thanks.
Incredibly helpful. Thank you
Really well explained and easy to understand!
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.
I'd be a genius if I'd worked it worked it out first. But Euler largely gets the credit, not me.
Why did my teacher just skip to teach this bit? Thank you for a good video.
Glad it was helpful!
so if the GCD of two numbers is not 1 then there is no multiplicative inverse
John Fernandez That is correct. Well done on working that out from the video :)
John Fernandez Welcome to fascinating world of Ring.
mage davee what are rings in a nutshell
John Fernandez
Are you Familiar with Groups, and if yes what about Fields?
+mage davee I am. Continue?
Why the hell it is not explained in detail at university? Glad saw this.
Wonderful explanation. Thank you for your time and help!
I've got lots of related videos (eg modular exponentiation made easy, Chinese remainder theorem made easy) on my channel.
Thanks for the effort.
Much appreciated!!
I wanna ask for the term of gcd is one, is this term for two problems above or just for modular multiplicative invers?
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.
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!
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.
Wow thank you so much! Great Video!!
Thanks.
Great tutorial, Thank You!
Thanks, great video even in 2020!
Thanks for the positive feedback. Interestingly, for quite old videos, my views seem to be increasing this year.
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.
999=249(4)+3 and then 4=1(3)+1. So gcd(999,4)=1.
@@RandellHeyman oh snap thanks
this made so much sense!!! thank you!
Very helpful, as always!
Thanks for the feedback; much appreciated.
Randell Heyman
Are you able to do/explain the CORDIC algorithm?
I've always wondered how calculators can compute sin/cos/tan;
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.
Why is there no inverse if the gcd isn’t 1? I’m fairly new to modular arithmetic, any explanation would be appreciated :P
I'll try to upload a video on thjs question in the next 24 hours.
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
you can't work outside the module, if its module 197 you can only work with 0-196
THIS MAN IS MY SAVIOR
Good to know :)
How do I substitute?
See my pinned comment.
beautifully explained...
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 ???
Hi, If it were (197)^-2 instead how would this change? Would it just be solve : 197^2 * d = 1 mod 3000 ?
Yes. Then you would use the fact that 197^2 = 2809 modulo 3000. So now solve 2809 d = 1 modulo 3000.
Thanks a lot man ....the video was excellent
Thanks. Lots of related videos in my university mathematics playlist, my corona help - discrete mathematics playlist and my corona help - euler's theorem playlist.
Just what I was looking for
Randell ,could u also add a proof of Fermats last theorem
@@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.
Ok thx
that's pretty easy thanks alot
This one video made me to subscribe to your channel :)
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?
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.
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
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.
I didn't get step 2
Hi Eduardo, many people have asked me about this step over the years. I will try to upload a video explaining further this afternoon.
Hi again. Have a look at th-cam.com/video/XJHT8goczsA/w-d-xo.html
A Great Video :) Thanks a lot for sharing
Really Helpful !
thanks alot
Thanks a lot mate...made my day...
Thank you very much, that's usefull
Thanks for commenting.
Thank you so much!
but what if the former number is bigger than the latter number? like 135 mod 61, thanks!
Hi, I'll upload an explanation video in the next 5 minutes.
@@RandellHeyman thank you so much! I'm looking forward to it!
Here is the video about it: th-cam.com/video/wntq9hsAb58/w-d-xo.html
i will just drop this here
I FUCKING LOVE YOU.
Thank you SO much. :)
I'm glad it helped.
Thanks a bunch.
Is 533 the only answer?
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.
+Randell Heyman Thanks
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 ???
Thanks a lot!
2:25 you pointed at the wrong line, otherwise nice work
Thanks for pointing out the error in my pointing out.
Thank you dude
Thanks for letting me know.
Nice explanation
extended euclidean algorithm
See my video I uploaded 1 hr ago
This wasn't made easy at all...the part after Euclid's alogrithm 😭😭 please help me
Oh... don't worry, I've seen the other video 😊
@@okoyemildred8720 Great. Any further problems...let me know.
@@RandellHeyman i will...thank you so much, you've been of much help to me and my brothers💙
Awesome
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 ???
In the second line you should have 1 = 2x17-2x11-1x11.:)
Randell Heyman
Ty very much ,few moments later I had corrected as I reviewed the steps .
u are too good loved ur video hats off :)
substitute this to that to this to that to that to this like be clearer!!!!
great!!
thanks!
I DIDNT GET PART 2
Have a look at my video Euclid's algorithm made easy. If you still have problems comment again.
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
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.
@@RandellHeyman ahhh cool, thanks
thank youu i get it noww,
Great. Thanks for commenting.
Hey man
worst method, doesnt work with big numbers
+cristianm alvaro Sorry I don't understand your comment. This method will work for big numbers.
on google (1/197)mod3000 is something like .... 0.00507614213 ...ur ans is like 533... what is correct thing..
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.
paaaaiiiiiiiiiiiiiiiiiiiiiin
Watch my other video modular arithmetic made easy and the paaiin should subside a little.