Modular inverse made easy

แชร์
ฝัง
  • เผยแพร่เมื่อ 20 ม.ค. 2025

ความคิดเห็น • 149

  • @RandellHeyman
    @RandellHeyman  4 ปีที่แล้ว +6

    If you having trouble with step 2 have a look at th-cam.com/video/XJHT8goczsA/w-d-xo.html

  • @st1tch525
    @st1tch525 7 ปีที่แล้ว +29

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

  • @ameliasaidwhat
    @ameliasaidwhat 9 ปีที่แล้ว +14

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

  • @SemihFatihAdem
    @SemihFatihAdem 8 ปีที่แล้ว +10

    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

  • @yann8442
    @yann8442 5 ปีที่แล้ว +2

    My whole class is thanking you for the explanations!

    • @RandellHeyman
      @RandellHeyman  5 ปีที่แล้ว +1

      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.

  • @TayoEXE
    @TayoEXE 6 ปีที่แล้ว +2

    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.

  • @michaelcoughlan7757
    @michaelcoughlan7757 8 ปีที่แล้ว +2

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

    • @RandellHeyman
      @RandellHeyman  8 ปีที่แล้ว

      +Michael Liam Coughlan Glad it helped.

    • @thomasgardner838
      @thomasgardner838 2 ปีที่แล้ว

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

    • @michaelcoughlan7757
      @michaelcoughlan7757 2 ปีที่แล้ว

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

  • @MC-Minority
    @MC-Minority ปีที่แล้ว +1

    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 🤣😭

  • @tombardier
    @tombardier 3 ปีที่แล้ว +2

    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
      @RandellHeyman  3 ปีที่แล้ว +1

      Great. Thanks for letting me know.

  • @DaveandEm2000
    @DaveandEm2000 6 ปีที่แล้ว

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

    • @RandellHeyman
      @RandellHeyman  6 ปีที่แล้ว

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

  • @ravishkumar8422
    @ravishkumar8422 3 ปีที่แล้ว

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

  • @tosscoin2206
    @tosscoin2206 3 ปีที่แล้ว +1

    Incredibly helpful. Thank you

  • @johallyw3
    @johallyw3 8 ปีที่แล้ว +3

    Really well explained and easy to understand!

  • @AmolGautam
    @AmolGautam 5 ปีที่แล้ว

    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
      @RandellHeyman  5 ปีที่แล้ว

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

  • @sandraa1234
    @sandraa1234 ปีที่แล้ว

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

  • @snake1625b
    @snake1625b 9 ปีที่แล้ว +14

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

    • @RandellHeyman
      @RandellHeyman  9 ปีที่แล้ว +6

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

    • @mage1over137
      @mage1over137 9 ปีที่แล้ว +1

      John Fernandez Welcome to fascinating world of Ring.

    • @snake1625b
      @snake1625b 9 ปีที่แล้ว +1

      mage davee what are rings in a nutshell

    • @mage1over137
      @mage1over137 9 ปีที่แล้ว +1

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

    • @lethargicastengah572
      @lethargicastengah572 9 ปีที่แล้ว +1

      +mage davee I am. Continue?

  • @thatsthething3218
    @thatsthething3218 3 ปีที่แล้ว

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

  • @christiancoder454
    @christiancoder454 3 ปีที่แล้ว

    Wonderful explanation. Thank you for your time and help!

    • @RandellHeyman
      @RandellHeyman  3 ปีที่แล้ว +1

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

  • @nikhilmadaan29
    @nikhilmadaan29 7 ปีที่แล้ว +1

    Thanks for the effort.
    Much appreciated!!

  • @JonathanSebastianS
    @JonathanSebastianS 9 หลายเดือนก่อน

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

  • @eatfruitsalad345
    @eatfruitsalad345 5 ปีที่แล้ว +1

    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
      @eatfruitsalad345 5 ปีที่แล้ว +1

      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
      @RandellHeyman  5 ปีที่แล้ว

      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.

  • @melissamarlen1022
    @melissamarlen1022 2 ปีที่แล้ว

    Wow thank you so much! Great Video!!

  • @bulat3226
    @bulat3226 7 ปีที่แล้ว +1

    Great tutorial, Thank You!

  • @The_Patbey
    @The_Patbey 4 ปีที่แล้ว

    Thanks, great video even in 2020!

    • @RandellHeyman
      @RandellHeyman  4 ปีที่แล้ว

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

  • @lemonke8132
    @lemonke8132 2 ปีที่แล้ว

    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
      @RandellHeyman  2 ปีที่แล้ว +1

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

    • @lemonke8132
      @lemonke8132 2 ปีที่แล้ว +1

      @@RandellHeyman oh snap thanks

  • @cupoftea6196
    @cupoftea6196 8 ปีที่แล้ว

    this made so much sense!!! thank you!

  • @Enceptics
    @Enceptics 10 ปีที่แล้ว +1

    Very helpful, as always!

    • @RandellHeyman
      @RandellHeyman  10 ปีที่แล้ว

      Thanks for the feedback; much appreciated.

    • @snoopdogg7363
      @snoopdogg7363 10 ปีที่แล้ว

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

    • @RandellHeyman
      @RandellHeyman  10 ปีที่แล้ว

      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.

  • @alexanderhamilton35
    @alexanderhamilton35 4 ปีที่แล้ว

    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
      @RandellHeyman  4 ปีที่แล้ว

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

  • @kianpopat9829
    @kianpopat9829 4 ปีที่แล้ว

    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
      @eduardoxenofonte4004 4 ปีที่แล้ว

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

  • @johnarchibald9202
    @johnarchibald9202 3 ปีที่แล้ว

    THIS MAN IS MY SAVIOR

  • @floatingyunsan
    @floatingyunsan 3 ปีที่แล้ว

    How do I substitute?

  • @lalwho
    @lalwho 9 ปีที่แล้ว +3

    beautifully explained...

    • @91099Babar
      @91099Babar 8 ปีที่แล้ว

      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 ???

  • @abraxzus1876
    @abraxzus1876 5 ปีที่แล้ว

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

    • @RandellHeyman
      @RandellHeyman  5 ปีที่แล้ว

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

  • @shloksand2926
    @shloksand2926 4 ปีที่แล้ว

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

    • @RandellHeyman
      @RandellHeyman  4 ปีที่แล้ว

      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
      @shloksand2926 4 ปีที่แล้ว

      Just what I was looking for

    • @shloksand2926
      @shloksand2926 4 ปีที่แล้ว

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

    • @RandellHeyman
      @RandellHeyman  4 ปีที่แล้ว

      @@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
      @shloksand2926 4 ปีที่แล้ว

      Ok thx

  • @mohammedsamymohammedabdeln2304
    @mohammedsamymohammedabdeln2304 3 ปีที่แล้ว

    that's pretty easy thanks alot

  • @SaiBharatBatchu
    @SaiBharatBatchu 7 ปีที่แล้ว +1

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

  • @luistan7429
    @luistan7429 8 ปีที่แล้ว

    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
      @RandellHeyman  8 ปีที่แล้ว

      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.

  • @georges.154
    @georges.154 4 ปีที่แล้ว

    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
      @RandellHeyman  4 ปีที่แล้ว

      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.

  • @eduardoxenofonte4004
    @eduardoxenofonte4004 4 ปีที่แล้ว +1

    I didn't get step 2

    • @RandellHeyman
      @RandellHeyman  4 ปีที่แล้ว

      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
      @RandellHeyman  4 ปีที่แล้ว

      Hi again. Have a look at th-cam.com/video/XJHT8goczsA/w-d-xo.html

  • @AnanthiRamasamy
    @AnanthiRamasamy 8 ปีที่แล้ว

    A Great Video :) Thanks a lot for sharing

  • @ahmedshokry7963
    @ahmedshokry7963 10 ปีที่แล้ว

    Really Helpful !
    thanks alot

  • @sagarakaraavan
    @sagarakaraavan 10 ปีที่แล้ว

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

  • @intensiveadvancedmath5281
    @intensiveadvancedmath5281 3 ปีที่แล้ว

    Thank you very much, that's usefull

  • @cindylee6249
    @cindylee6249 4 ปีที่แล้ว

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

    • @RandellHeyman
      @RandellHeyman  4 ปีที่แล้ว

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

    • @cindylee6249
      @cindylee6249 4 ปีที่แล้ว

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

    • @gamedit2999
      @gamedit2999 3 ปีที่แล้ว

      Here is the video about it: th-cam.com/video/wntq9hsAb58/w-d-xo.html

  • @mkerm3875
    @mkerm3875 5 ปีที่แล้ว +1

    i will just drop this here

  • @levibrian10
    @levibrian10 5 ปีที่แล้ว

    I FUCKING LOVE YOU.

  • @Mayzaf14
    @Mayzaf14 7 ปีที่แล้ว

    Thank you SO much. :)

  • @simonarcher4445
    @simonarcher4445 5 ปีที่แล้ว

    Thanks a bunch.

  • @andyjiao3114
    @andyjiao3114 8 ปีที่แล้ว

    Is 533 the only answer?

    • @RandellHeyman
      @RandellHeyman  8 ปีที่แล้ว

      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
      @andyjiao3114 8 ปีที่แล้ว

      +Randell Heyman Thanks

    • @91099Babar
      @91099Babar 8 ปีที่แล้ว

      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 ???

  • @Alexander25i
    @Alexander25i 10 ปีที่แล้ว

    Thanks a lot!

  • @dcrock8978
    @dcrock8978 2 ปีที่แล้ว

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

    • @RandellHeyman
      @RandellHeyman  2 ปีที่แล้ว

      Thanks for pointing out the error in my pointing out.

  • @larubiano0
    @larubiano0 3 ปีที่แล้ว

    Thank you dude

  • @ayepyone7398
    @ayepyone7398 10 ปีที่แล้ว

    Nice explanation

  • @dg6546
    @dg6546 4 ปีที่แล้ว

    extended euclidean algorithm

    • @RandellHeyman
      @RandellHeyman  4 ปีที่แล้ว

      See my video I uploaded 1 hr ago

  • @okoyemildred8720
    @okoyemildred8720 3 ปีที่แล้ว +1

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

    • @okoyemildred8720
      @okoyemildred8720 3 ปีที่แล้ว

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

    • @RandellHeyman
      @RandellHeyman  3 ปีที่แล้ว

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

    • @okoyemildred8720
      @okoyemildred8720 3 ปีที่แล้ว

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

  • @sadimannan7248
    @sadimannan7248 8 ปีที่แล้ว

    Awesome

  • @91099Babar
    @91099Babar 8 ปีที่แล้ว

    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
      @RandellHeyman  8 ปีที่แล้ว

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

    • @91099Babar
      @91099Babar 8 ปีที่แล้ว

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

  • @Summer2monsoon
    @Summer2monsoon 10 ปีที่แล้ว

    u are too good loved ur video hats off :)

  • @karlchami4740
    @karlchami4740 4 ปีที่แล้ว +4

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

  • @parvbhardwaj9188
    @parvbhardwaj9188 8 ปีที่แล้ว

    great!!

  • @nathwhite5119
    @nathwhite5119 10 ปีที่แล้ว

    thanks!

  • @haniakhalidshariff4573
    @haniakhalidshariff4573 3 ปีที่แล้ว

    I DIDNT GET PART 2

    • @RandellHeyman
      @RandellHeyman  3 ปีที่แล้ว +1

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

  • @nBodyResearch
    @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
      @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
      @nBodyResearch ปีที่แล้ว

      @@RandellHeyman ahhh cool, thanks

  • @cs2c_gabardaangelob.88
    @cs2c_gabardaangelob.88 2 ปีที่แล้ว

    thank youu i get it noww,

    • @RandellHeyman
      @RandellHeyman  2 ปีที่แล้ว

      Great. Thanks for commenting.

  • @randallhale7775
    @randallhale7775 3 ปีที่แล้ว

    Hey man

  • @cristianmalvaro3362
    @cristianmalvaro3362 8 ปีที่แล้ว

    worst method, doesnt work with big numbers

    • @RandellHeyman
      @RandellHeyman  8 ปีที่แล้ว +2

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

  • @pratikmehta6207
    @pratikmehta6207 5 ปีที่แล้ว

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

    • @RandellHeyman
      @RandellHeyman  5 ปีที่แล้ว +1

      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.

  • @hearts33d
    @hearts33d 4 ปีที่แล้ว

    paaaaiiiiiiiiiiiiiiiiiiiiiin

    • @RandellHeyman
      @RandellHeyman  4 ปีที่แล้ว +1

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