Thank you for explaining it so well. I hate it when some other mathematicians just show off by being cryptic, its so frustrating. Your tutorial was a tiny tad slower but made it so much easier to follow and learn. Thanks.
The thing is that mathematicians use symbolic representations and formulas to summarize stuff in a compact way - but that's terrible for explanation. They should refrain from doing that and instead explain things in a human-friendly way!
Can I just say thank you on behalf of everyone at QMUL taking the Algorithms and Complexity module. This has really come in useful with trying to understand RSA encryption!
I've been looking for a video like this for weeks. After another seemingly fruitless search, I prayed and just stumbled on your well explanatory video. Thank you very much.
This makes sense now! I decrypted an affine cipher, but afterwards, I couldn’t figure out how I got -5 as the inverse of 5 or how it worked. After watching this video, I worked it out and got -5 again. Apparently, I’m just the type of person to use actual math successfully by accident.
Thank you so much for this! I have a discrete final coming up and it's the videos on niche topics like this that are really getting me through. You teach it so well too, thank you so much for putting your effort and time into videos like these.
doing Bsc mathematics and computer science in pure maths section (number theory).... this tutorial has really really improved me.... i have not only understood linear congruence but also cryptology... nice and God bless you
Thank you. Not every number in a mod field will necessarily have an inverse. For example 2 (mod 4) does not have and inverse since 2*0 = 0 (mod 4) .... 2*1 = 2 (mod 4) ... 2*2 = 0 (mod 4) ...2*3 = 2 (mod 4) ... none of these results produce 1 (mod 4) and you have checked 2*0 , 2*1 ,..., 2*(n-2) , 2*(n-1) where n is the mod.
If that is the case, I would guess that you simplified a little early. When doing this process, it is important to leave terms as multiples of two numbers, so that one of the numbers can be replaced by an equation above. I hope that helps. :)
Learn Math Tutorials I like how you solved for the remainder values first in the video, then went and did the Reverse Eulcidean Algo (REA) This method is different from every other method I have seen demonstrated (where they do the REA and computer the replacement values on-the-fly). I think you way will keep me organized better, thanks for making the video.
This is a great instructional video ... I still need to clean up some details in my understanding ... but this question: Is there a check you can do to verify the answer ? I’m trying to do 27^-1 (mod 292) compared to 363 ( mod 392) ... or, am I thinking about this wrong ?
1001 = 200(5) + 1 Rewrite as 1 = 1001 + 200(-5) (mod 1001) Note that 1001 (mod 1001) = 0 and also (-5) (mod 1001) = 996 since 1001 - 5 = 996 then we have 1 = 0 + 200(996) therefore 1 = 200(996) (mod 1001) Then 996 is the inverse of 200 (mod 1001) You can check the result by looking at 996(200) = 199200 = 199(1001) + 1 (mod 1001) and anything times the mod is 0 so we get 996(200) = 1 (mod 1001) I tried to format this nicely but it gets all jumbled together when I post it as a comment.
Thanks a lot , it was very helpful. Could you please make more videos on modular arithmetic algorithms . It would really help me a lot. Thanks once again :)
Great tutorial! All this can be avoided by using matrix multiplication which is a faster and easier route to get the multiplicative inverse of 27 mod 392. It is always good to know both ways of course, but like I said, great tutorial! Maybe I should do a tutorial on how to do it using matrices...
So for example if we did the EEA and came up with a number that was between 0 and 392 then that would be the answer, we wouldn't have to do anything else to it?
hey any chance you can make a playlist of these so we know which order to go it? just watched the positive mod change vid and im pretty sure next should be the negative mod but its this? which i dont think should be next?
I hope you’ll answer this question right away. Badly needed. We’re going to report this topic this coming Thursday. May I know why do we need to get the multiplicative inverse of the given? just like in the example. Why do we need to get the inverse of 27 (mod 392) and it should be congruent to 1 mod 392?
@@marksahlgreen9584 make sure you add both 7(1) and 7(8) together it will be 7(9), in the last step it will be 1=7 + 31(-2) +7(8). 4years old but I hope this helps :)
When you didn't explain why you replaced -29 with 363 I lost you, I mean it's unique to this question only. in other problems how will we know what to replace or we should even replace or not? You must have explained it a bit.
In the step where you calculated 363 by subtracting 29 from 392 (392-29=363) does the negative come from the -29? So if 29 were positive would you add 29 to 392?
Logan Koester He found the answer to be -29. That is a valid answer, but you will often be asked to find the positive inverse. -29 and 363 are essentially the same number under mod 392.
Pretty nice tutorial, even after all these years. Sir am wondering, if we had had a positive number instead of a negative one at + 27(-29)...., would we have still subtracted it from 392 or added it instead?
2 (or any other even number) don't have inverse in mod 392 (or any other even number). If x would be a inverse then 2*x= y*392 + 1. 2*x must be even and y*392+1 must be odd.
this seems to be somewhat lacking in explanations into why you're doing things. i can follow along, but why we are doing each step seems to be not mentioned.
He basically found the gcd of 392 and 27. Then he used the steps to build up Bezout identity. This identity is the key to solve the problem. A little refresh: Euclidian algorithm says that if a and b are two positive integers and a=b*q+r Then gcd(a,b)=gcd(b,r). We use the division algorithm until we find 0 as a remainder (in this case he skipped this part). Notice we found that gcd(392,27)=1 which is very important. Next we have Bezout theorem. It says that if gcd(a,b)=d then we can find integers r and s such that a*r+b*s=d. Using the steps from the euclidian algorithm we can build up this identity. Finally we use this identity to solve the problem. Why is it important to have 1 as the gcd? Because if the gcd(a,b)≠1 then b has no inverse mod a.
Can someone explain to me what's the practical use of modular arithmetic if we don't count encryption which is used automatically and with a very large numbers?
It did help to explain what the textbook had in written words and figures...but it is still difficult because you still have to go through all the numbers on the Euclidean algorithm to get to the bottom of this. So imagine if you have a gcd(80, 98) it would be endless!!
Nice video! I just wish you hadn't chosen an example where the quotient and remainder of the first division are both 14s. And then we have two 1's later on as well.
Thank you for explaining it so well. I hate it when some other mathematicians just show off by being cryptic, its so frustrating. Your tutorial was a tiny tad slower but made it so much easier to follow and learn. Thanks.
The thing is that mathematicians use symbolic representations and formulas to summarize stuff in a compact way - but that's terrible for explanation. They should refrain from doing that and instead explain things in a human-friendly way!
@@nahiyanalamgir7056 Suffering from this right now in my Cryptography class, absolutely soul-sucking explanations in this class
Been searching all night for this to learn chinese remainder theorem for tomorrows network security exam. This one is a LIFESAVER
This was amazing. Way better step by step explanation than my professor. THANK YOU!!
Can I just say thank you on behalf of everyone at QMUL taking the Algorithms and Complexity module. This has really come in useful with trying to understand RSA encryption!
Same, had to learn this topic to understand RSA encryption!
man rsa encryption is 8th grade math
I've been looking for a video like this for weeks. After another seemingly fruitless search, I prayed and just stumbled on your well explanatory video. Thank you very much.
This makes sense now! I decrypted an affine cipher, but afterwards, I couldn’t figure out how I got -5 as the inverse of 5 or how it worked. After watching this video, I worked it out and got -5 again. Apparently, I’m just the type of person to use actual math successfully by accident.
Thank God! I have an exam tomorrow and I've never really understood how to use the algorithm to find aninverse. I like u.
Thank you so much for this! I have a discrete final coming up and it's the videos on niche topics like this that are really getting me through. You teach it so well too, thank you so much for putting your effort and time into videos like these.
doing Bsc mathematics and computer science in pure maths section (number theory).... this tutorial has really really improved me.... i have not only understood linear congruence but also cryptology... nice and God bless you
The best explanation on the youtube I found so far. Thank you
THANK-YOU!!! So intuitive when shown this way. My proff skipped a bunch of steps and it went right over my head. Much appreciated!
Absolutely amazing tutorial! Preparing for my exam, I couldn't find a good explanation anywhere! You really saved my bacon!
after 10 years. Thank you. Was going crazy :')
Thanks so much THIS IS EXACTLY WHAT WAS MISSING IN OTHER VIDEOS MUCH APPRECIATION!!!!
very very thanks.. i am strugling with inverse. you solved the problem very efficiently .......
Excellent video clearly demonstrating how to calculate the inverse of a number(mod n). Very grateful for this video!
RESPEK!
Every other TH-cam tutorial should do future students of this a favor and take off their videos.
Most clear and concise.
Respek once again
this is the best explanation ever. thumps up man.
Thanks you very much sir, wish you continues success
Thank you so much! I feel confident doing these kinds of problems now!
The best explanation for modular multiplicative inverse.. Thanks much!
This really helped a lot. Feeling much more prepared for my exam now
Thank you. Not every number in a mod field will necessarily have an inverse. For example 2 (mod 4) does not have and inverse since 2*0 = 0 (mod 4) .... 2*1 = 2 (mod 4) ... 2*2 = 0 (mod 4) ...2*3 = 2 (mod 4) ... none of these results produce 1 (mod 4) and you have checked 2*0 , 2*1 ,..., 2*(n-2) , 2*(n-1) where n is the mod.
If that is the case, I would guess that you simplified a little early. When doing this process, it is important to leave terms as multiples of two numbers, so that one of the numbers can be replaced by an equation above. I hope that helps. :)
Thank you so much for making this understandable and easy to follow. Life saver!!
boss tnx now I can explain it very well to my students.there are lots of video related to this bt this clearly explains the topic.nice...
you had explained in very clear manner thanks sir...
thank you so much. I spend a day to find the solution for d equal to negative. Superb.
Your explanations on this topic is so on point. Thanks alot
awesome video dude, love how you used the different colour schemes to segregrate some of the concepts behind what was going on!
Having an exam coming next week. You saved me. HUGE THANKS
I should've found this video first! It was very clear, thank you.
Thank You so much! I spent an hour with my teacher today and I think now I finally got the idea:)
Great explanation! Way better than my lecture at uni
great video!!!!! You explain it in a structured way which is essential for a topic as such. Thanks!
Excellent explanation which is useful in understanding RSA algorithm.
5 Star rating for this video!
r u mad ..... :P :P
Very nice video, good use of colours. Excellent explanation of the Euclidean algorithm leaving no steps out. Well done.
Thank you! This was the best explanation of EA and EEA I've been through. I still have no idea why tf this thing exists though
Studying for my final and couldn't figure this out for the life of me. Your explanation was great. Thank you
Very nice video, my lecturer just expected us to guess how to do this! Thanks :)
Thank you so much! best guy on youtube for this tutorial!
Thanks sooooo much.
awesome explanation! looking forward to check out the rest of the videos. :)
Learn Math Tutorials I like how you solved for the remainder values first in the video, then went and did the Reverse Eulcidean Algo (REA) This method is different from every other method I have seen demonstrated (where they do the REA and computer the replacement values on-the-fly). I think you way will keep me organized better, thanks for making the video.
Great video, helped me understand how to deal with negative numbers in Bezout's theorem.
thank you, well explained video
better than my indian lecturer will ever explain it with her annoying accent, thank you good sir, and this definitely warrants a subscribe
Thanks man! Came in handy with Abstract Algebra
This is a great instructional video ... I still need to clean up some details in my understanding ... but this question: Is there a check you can do to verify the answer ? I’m trying to do 27^-1 (mod 292) compared to 363 ( mod 392) ... or, am I thinking about this wrong ?
Thanks you!! it is really helpful for me to understand.
wow thank you for making this. it helped a ton!
this was very good, exactly what i was looking for
Excellent, thanks for the video.
amazing explanation! saved me a lot of time!
Thank you for the explanation, you say me a lot of theory
1001 = 200(5) + 1 Rewrite as 1 = 1001 + 200(-5) (mod 1001) Note that 1001 (mod 1001) = 0 and also (-5) (mod 1001) = 996 since 1001 - 5 = 996 then we have 1 = 0 + 200(996) therefore 1 = 200(996) (mod 1001) Then 996 is the inverse of 200 (mod 1001) You can check the result by looking at 996(200) = 199200 = 199(1001) + 1 (mod 1001) and anything times the mod is 0 so we get 996(200) = 1 (mod 1001) I tried to format this nicely but it gets all jumbled together when I post it as a comment.
Thanks a lot , it was very helpful. Could you please make more videos on modular arithmetic
algorithms . It would really help me a lot. Thanks once again :)
Dude you have helped alot😇😇😇😇😇😇😇
Thank you so much! While reading my book I was completely lost! You made this so simple to follow and understand. Thanks again!
what if i am left with a constant on the left at the end
Just what I needed, thanks a lot man
Wonderful tutorial!!
very clear explanation, thanks!
Great tutorial! All this can be avoided by using matrix multiplication which is a faster and easier route to get the multiplicative inverse of 27 mod 392. It is always good to know both ways of course, but like I said, great tutorial! Maybe I should do a tutorial on how to do it using matrices...
+Gabriel Sotolongo Im curious to how you do it with matrices! haha
+Jack Binding it is really easy, I could make a video an upload it if you like, anyways there is none here in TH-cam of that type.
+Gabriel Sotolongo if you do decide to make one defo tell me! Haha
+Jack Binding I will try to make the video today (no promises) ;)
haha, im grateful if you upload it any time man! I've just not seen anything modulo been solved with matrices so im just curious!
very helpful video, are the equal signs at the end supposed to be congruence signs?
Great explanation!
Thank you so much this is so useful great job!
So for example if we did the EEA and came up with a number that was between 0 and 392 then that would be the answer, we wouldn't have to do anything else to it?
hey any chance you can make a playlist of these so we know which order to go it? just watched the positive mod change vid and im pretty sure next should be the negative mod but its this? which i dont think should be next?
Very helpful. Thanks for making
I hope you’ll answer this question right away. Badly needed. We’re going to report this topic this coming Thursday.
May I know why do we need to get the multiplicative inverse of the given? just like in the example. Why do we need to get the inverse of 27 (mod 392) and it should be congruent to 1 mod 392?
Thanks a lot. Searching the answer for asymmetric key cryptography
Well explain, good example, thank you very much that helps so much
Sir. It was a brilliant tutorial ...
Just wondering if I have learnt this well or not. Is 7 inverse mod 31 = 9 ? Please advice.
Debajyoti Biswas Yes! Good Job! :)
I am sitting with this exact same calculation, and I can't make it to be 9 >_
Yeah bro. I've also go it :)
@@marksahlgreen9584 make sure you add both 7(1) and 7(8) together it will be 7(9), in the last step it will be 1=7 + 31(-2) +7(8). 4years old but I hope this helps :)
When you didn't explain why you replaced -29 with 363 I lost you, I mean it's unique to this question only. in other problems how will we know what to replace or we should even replace or not? You must have explained it a bit.
29+363 = 392. u can check out his -ve number modulo video
Clear cut explanation.
What should I do , if there is natural number in the givens, not number with -1 degree?
In the step where you calculated 363 by subtracting 29 from 392 (392-29=363) does the negative come from the -29? So if 29 were positive would you add 29 to 392?
Logan Koester He found the answer to be -29. That is a valid answer, but you will often be asked to find the positive inverse. -29 and 363 are essentially the same number under mod 392.
Pretty nice tutorial, even after all these years. Sir am wondering, if we had had a positive number instead of a negative one at + 27(-29)...., would we have still subtracted it from 392 or added it instead?
Feysal Imraan
27 (mod n > 27) = 27
So you leave the 27 as is.
very good expatiation thank you
So easy to understand ty
best explanation
great thanks for the explanation!
This is very helpful
thank you sooo much .. u r the best
Great tutorial! :)
so nice explanation .
Thanks. You helped me alot
is there an easier way? to find x? or the inverse of mod? please let me know
How would you take the inverse of 2 (or any other even number) in mod 392?
2 (or any other even number) don't have inverse in mod 392 (or any other even number).
If x would be a inverse then 2*x= y*392 + 1. 2*x must be even and y*392+1 must be odd.
Is my thinking correct that you can only find an inverse if the gcd(a,n) = 1 where a = 1 (mod n)
this seems to be somewhat lacking in explanations into why you're doing things. i can follow along, but why we are doing each step seems to be not mentioned.
Agreed
He basically found the gcd of 392 and 27. Then he used the steps to build up Bezout identity.
This identity is the key to solve the problem.
A little refresh:
Euclidian algorithm says that if a and b are two positive integers and
a=b*q+r
Then gcd(a,b)=gcd(b,r).
We use the division algorithm until we find 0 as a remainder (in this case he skipped this part).
Notice we found that gcd(392,27)=1 which is very important.
Next we have Bezout theorem.
It says that if gcd(a,b)=d then we can find integers r and s such that
a*r+b*s=d.
Using the steps from the euclidian algorithm we can build up this identity.
Finally we use this identity to solve the problem.
Why is it important to have 1 as the gcd?
Because if the gcd(a,b)≠1 then b has no inverse mod a.
Can someone explain to me what's the practical use of modular arithmetic if we don't count encryption which is used automatically and with a very large numbers?
It did help to explain what the textbook had in written words and figures...but it is still difficult because you still have to go through all the numbers on the Euclidean algorithm to get to the bottom of this. So imagine if you have a gcd(80, 98) it would be endless!!
What happens when the number and n are not coprime? I.e. the GCD is not 1. Would we have to divide by the gcd?
Thank you so much, mate.
Nice video! I just wish you hadn't chosen an example where the quotient and remainder of the first division are both 14s. And then we have two 1's later on as well.
how to calculate multiplicative inverse of 13mod40
that for some reason doesnt work for me. I end up with12x12+10=1 mod 17 which does not help at all