Solve a Linear Congruence using Euclid's Algorithm
How to solve 17x ≡ 3 (mod 29) using Euclid's Algorithm. If you want to see how Bézout's Identity works, see • Bézout's Identity, usi...
0:00 A linear congruence...
0:30 ....is not an equation, but...
1:18 Multiplicative inverse
4:40 Euclid's Algorithm
5:58 Make the remainder the subject in each line
7:10 Backwards substitution
12:20 Multiply both sides of congruence by the multiplicative inverse
13:20 Check
Пікірлер: 361
On this topic, this is arguably the best explanation. Thank you.
@MathsWithJay
7 жыл бұрын
Brilliant! Thank you very much
@deandrelab4584
3 жыл бұрын
can someone explain to me how the 4 is removed?
I searched so long for a proper explanation to this topic and you literally made me understand one week of college classes in 15 minutes! Keep up the good work and thank you kindly! 😊
@MathsWithJay
7 жыл бұрын
Excellent. So glad that you found this useful!
Best with 1.25 speed :)
@MathsWithJay
8 жыл бұрын
+Moontego :)
@randomworksstudios9241
6 жыл бұрын
Better than best with 2.00 speed, a whiteboard, and lots of pausing.
@geraldillo
4 жыл бұрын
Very likely, it took Euclid a bit longer than 15 minutes to invent this brilliant algorithm. I am thankful that I can learn his algorithm in under 15 minutes, thoroughly explained and easy to understand. Thanks you for that, Math with Jay.
@MathsWithJay
4 жыл бұрын
My pleasure, geraldillo
@y.z.6517
4 жыл бұрын
@@geraldillo "it took Euclid a bit longer than 15 minutes to invent this brilliant algorithm." Citation? It took ~15 minutes to run through 1 example. Presumably, he needed longer to come up with a general solution, check it, and prove it?
Thank you so much! It always baffles me that teachers such as yourself can explain things this clearly and concisely, whilst others would take weeks to convey the same message.
@MathsWithJay
Жыл бұрын
You're very welcome!
Thank you for the clear explanation of this. I'm taking a discrete math class currently and the book did not explain very well.
@MathsWithJay
7 жыл бұрын
Thanks a lot for your useful feedback.
Precisely explained; my Discrete Mathematics professor is basically useless. I'll be finding myself in this channel quite often through out the rest of the semester.
@MathsWithJay
7 жыл бұрын
Welcome to Maths with Jay!
@jonathanharoun5247
4 жыл бұрын
I didn't learn this in Discrete Math.
Damn! I searched every playlist, saw nearly every video on this topic, and when I watched this one. I knew something extraordinary struck my mind! The question was solved!! A HUGE THANKS to you. The way you taught and explained each process is mesmerizing! I got each and every step so easily that I won't be forgetting it for a decade or such!
@MathsWithJay
2 жыл бұрын
@Prashant: Thank you so much for this lovely feedback. It's great to know that you found this video so useful.
Very Nice. Brilliantly explained, and nice and slow!! Thank you!!
@MathsWithJay
7 жыл бұрын
Thank you, Lewis. Glad you found it useful!
Which method is the most efficient in solving the linear congruence?
A GREAT explanation, easy to follow while writing what you're saying. Thank you for it, love ya!
@MathsWithJay
8 жыл бұрын
+Islam Elshobokshy Thank you so much for your positive feedback. It's great to know that you found this so useful. Jay
12:36 Im so confused how 12*17x = x?? I understand thats what weve found for Bezut, but I just dont get how this works to isolate x? Is there some implicit thing we must assume about the 12? Because outright 12*17x could never give x.
@MathsWithJay
3 жыл бұрын
We found that 12*17=1 on the LHS of the screen
What is the program that you write the equations
how to solve the same equations in two variables.can we split the va riables in single variables equations.?
I'am german and i never understand a german Video about Linear Congruence. Now i understand it... Awesome work! :)
@MathsWithJay
3 жыл бұрын
Glad to hear that! I speak a little German, but not enough to explain maths!
this what I call a top notch explanation, thank you
@MathsWithJay
7 жыл бұрын
Thank you so much for your positive feedback
Thanks Jay! most useful 14 minutes ever!
@MathsWithJay
6 жыл бұрын
Thank you!
Thank you for this video It was just so clear...I got it now.
@MathsWithJay
6 жыл бұрын
Thank you!
Great explanation. Keep up the good work (Y)
@MathsWithJay
8 жыл бұрын
+Siddhant Sharma Thank you for your positive feedback; it is much appreciated. Jay
I dont even study in English but couldn't find an Explanation in my language. Thanks so much for uploading this. Finally understood why we can Change it into a linear equation!!
@MathsWithJay
6 жыл бұрын
Thank you! What is your language?
@kathleesi
6 жыл бұрын
German :)
@MathsWithJay
6 жыл бұрын
Danke!
This is the 4th video on this topic and I finally understood it.. thank you
@MathsWithJay
8 ай бұрын
You're very welcome!
this does not work on every linear congruent right? I mean.... I tried the method yes, but I also used the "Linear Congruence Calculator" and they have different results, idk why and idk which is correct or not.
I love this explanation, thank you very much. Hugs from México!
@MathsWithJay
6 жыл бұрын
@Goa: Many thanks! Greetings to México from London!
I have one more question, I am doing a RSA encryption problem. and I want to know how to solve bigger number modular without fast modulation. For ex: 2015^17 mod (3233) how would I break down the number and exponentials?
@MathsWithJay
5 жыл бұрын
@ImDHML: One way to start on a similar example: If we want 2018^19 (mod 3104), this would be congruent to (-1086)^19 (mod 3104), then it might help to write 1086 as 2x3x181, ...
Excellent explanation, the best on here by a long way.
@MathsWithJay
3 жыл бұрын
Glad you think so!
What if the left hand side has subtraction or addition like 3x − 5 ≡ 4 (mod 7)?
@MathsWithJay
2 жыл бұрын
You can treat it like a normal equation, so add 5 to both sides
I can't find the word to explain how good this video was! Thank you so much! (I'm not english sorry for my mistakes)
@MathsWithJay
4 жыл бұрын
@Simone: Thank you very much! Your English is very good.
Your voice is really smooth, i like it!
Should call it maths with bae
Thank you for posting this! very helpful :)
@MathsWithJay
7 жыл бұрын
Many thanks for your feedback. It is really appreciated.
omg why do i go to lecture when i can come here. THANK YOU JAY
@MathsWithJay
7 жыл бұрын
Thanks a lot :)
Your video was amazing thank you very much! Just one quick question, let's say that in the end, the result was x congruent 14 (mod 19). Would x be equal to 14 or 5 (as 19-14= 5 but it is not arranged in that order)?
@MathsWithJay
6 жыл бұрын
Thank you for your feedback, Aimee. You can add or subtract multiples of 19 from 14, so the best answer is 14, but 14 - 19 = -5 is also an answer. 5 is not congruent to 14 (mod 19).
Thanks for the explanation. Do we have to do one of these in the MST125 exam by any chance? As I may just run out of time! :)
@MathsWithJay
Жыл бұрын
The more practice you get, the faster you will be!
right at the end, congruent to 1. whats that mean? how does 12(17x) = x?
@MathsWithJay
4 жыл бұрын
@Colin: Multiply 12 by 17...this gives 204....divide by 29....what is the remainder?
Finally found the best explanation, thank you very much
@MathsWithJay
3 жыл бұрын
You are welcome!
Thank you very much. Your video helped me ace an exam.
@MathsWithJay
5 жыл бұрын
@Splunchy: Excellent. Thank you for letting us know.
Excellent explanation, thank you!
@MathsWithJay
6 жыл бұрын
Thank you very much!
Exceptional video! I like how each step is mentioned, by far the best video I've seen. @3:07 in the video I believe the side equation should read: 17v = 1 + 29w --> 17v - 29w = 1. Otherwise, the equation doesn't equate to 1.
@MathsWithJay
7 ай бұрын
Thank you for your feedback. We have 17v = 1 - 29w ...but a different sign in front of the 29w just means that we would find w has a different sign.
I have to do 13x+5=6x+15 (mod 20) anything special I have to do to deal with the integer addition?
@MathsWithJay
6 жыл бұрын
I could have started with 20x + 1 ≡ 3x + 4, and then subtracted 3x and 1 from both sides. I could check the answer in 20x + 1 ≡ 3x + 4..and see that it works.
I love you! seriously you saved me
@MathsWithJay
5 жыл бұрын
@Muhammad: Thank you!
excellent explaination...slow and steady
@MathsWithJay
7 жыл бұрын
Thank you; it's good to know that you've found this useful.
You are so helpful, Ma'am! Thank you!
@MathsWithJay
2 жыл бұрын
@Jen, you are so welcome!
Nicely explained as usual
@MathsWithJay
6 жыл бұрын
Thank you for your positive feedback.
3:08 why is it minus 29??
@MathsWithJay
3 жыл бұрын
It could be plus or minus...if you try it with plus, w will end up having the opposite sign
In less than 15 minutes, you've managed to explain what my professor failed to in 50. Thank you.
@MathsWithJay
5 жыл бұрын
@Caleb: Thank you!
thank you finally, after hours of searching
@MathsWithJay
2 жыл бұрын
Glad I could help
Hi I want to ask what steps would be taken if the result of v after using the extended algorithm was a negative integer. would you still proceed using the outlined steps??
@MathsWithJay
7 жыл бұрын
It's easier to answer this kind of question if you give an example. If you are not sure if the method works, try it, then check the answer at the end.
@donsunnyj
7 жыл бұрын
thanks for your response here is the problem I was trying to solve 56x is congruent to 100 mod 236.
@MathsWithJay
7 жыл бұрын
The first stage here is to divide through by the common factor. Then v will will be negative, so x will also be negative, but you can then add on a positive multiple of the mod so that your final answer is a small positive value. You can then check that it solves the given congruence. What do you get for v?
@donsunnyj
7 жыл бұрын
thanks for your help thus far these the values i got for v and w : v=-21 and w=5. so i'm confused on how to proceed from there because of the presence of the negative sign.
@MathsWithJay
7 жыл бұрын
You are doing fine: you now know that 14x is congruent to 25 (mod 59), and 1 = 5x59 - 21x14, so (-21) multiplying both sides of your linear congruence gives x= -525. Add 9x59 to this to get a small x value. Or if you don't like (-21), you could add 59 to it to get 38 and use that instead....then you'd get 950 before subtracting a multiple of 59. Both methods give the same value for x...and check this in your original congruence.
Very much helpful to students in secondary levels.
@MathsWithJay
5 жыл бұрын
@GajendraPrasad Das: Thank you! What age are those students and in which country?
why didn't you just shift the inverse of 17 to the other side and take the modulo of it?
At 2:46 how did you write 17v=1-29w
@icgaming9280
4 жыл бұрын
I don’t understand that too
@MathsWithJay
4 жыл бұрын
Think about what mod 29 means...
so we were using euclids algorithm basically if the a and n are laege odd numbers?
@MathsWithJay
2 жыл бұрын
or do you mean prime?
Amazing!!! you made the process very simple.
@MathsWithJay
7 жыл бұрын
Great to have your feedback. Thank you.
Great video, but just one question(I'm dumb), as the result of x congruent 7(mod 29), wouldn't that means x-7=29k?(k is a random number that representing the times of 29), I'm kinda confused cuz the way you check the result is kinda like taking "x=7" instead of "x congruent 7"
@MathsWithJay
3 жыл бұрын
If you have an answer of 7, then 7 plus or minus a multiple of 29 should work too
@seno3863
3 жыл бұрын
@@MathsWithJay Got to say I'm surprised by the fact that there's actually a reply for a video that existed for so long, I'm really grateful, ty!
How did we leave with just only x at the last bit please rep thanks
@MathsWithJay
5 жыл бұрын
@Ian: At what time in the video please
when you said 17v is congruent to 1 (mod 29), is that true because 29 is prime, in other words if it was 17x is congruent to 3 (mod 30), would it still be correct to write 17v is congruent to 1 (mod 30)?
@MathsWithJay
8 жыл бұрын
17v is congruent to 1 (mod 29) because we worked out that 17x12 - 7x29 = 1. If you want to use mod 30, you need to start at the beginning again, using 30 instead of 29.
absolutely loved it
@MathsWithJay
Жыл бұрын
Thank you!
very nice :) .. but what if i have something like 21x=11mod3 (by = i means to congruent) so (21,3) dos not divide 1 . but this linear congruent is a part of Chinese remainder theorem problem..
@MathsWithJay
8 жыл бұрын
Do you really mean mod 3? If so, 21 is congruent to 0, and 11 is not, so there is no possible value for x.
Thank you very much for this explanation; it was very helpful. :D
@MathsWithJay
4 жыл бұрын
You're very welcome!
wow this really helped me get it! thanks!
@MathsWithJay
4 жыл бұрын
@S L: Thank you!
very easy to understand thank you
@MathsWithJay
5 жыл бұрын
@Fadhil Sugiharto: Excellent! Thank you!
Thank you so much! I have been trapped on this for weeks..
@MathsWithJay
3 жыл бұрын
Glad I could help!
Thank you! I finally understand this topic.
@MathsWithJay
3 жыл бұрын
You are welcome!
How does 12 x 17x change to be just x in the last step?
@MathsWithJay
Жыл бұрын
We are rearranging the previous line where there was a 1 on the LHS.
How would you do it for both negative solutions?
@MathsWithJay
4 жыл бұрын
Do you have an example in mind?
@aqsayounus6236
4 жыл бұрын
Maths with Jay it doesn’t exactly have two negative solutions, but solving 5x congruent to 9mod8 gave me v = -3 and w = 2, so I’m a bit confused how to solve the last part (the part after we calculate v and w ) and how to check the answer if the v is negative
@MathsWithJay
4 жыл бұрын
You could make v positive by adding on 8 because you are using mod 8. (You could also make the question simpler by subtracting 8 from 9) Both should give the same answer.
Thank you so much from Belgium
@MathsWithJay
6 жыл бұрын
Thank you!
Thank you!!!! so much this was a really clear explanation.
@MathsWithJay
3 жыл бұрын
Glad it was helpful!
How to solve linear congruence questions using maple software?
@MathsWithJay
4 жыл бұрын
www.maplesoft.com/support/help/Maple/view.aspx?path=Task%2FSolveEqnModuloN
OK. I am lost at the last step. How did you go from X is congruent to 36 (Mod29) to Xi s congruent to 7 (Mod29)? Please show steps when responding. Thank you.
@J3FFR3Y08
4 жыл бұрын
36-29 = 7
Thank you for this!
@MathsWithJay
4 жыл бұрын
@tader: Thank you!
Better than my cryptography textbook thanks so much!!
@MathsWithJay
3 жыл бұрын
Wow, thanks!
What happened to 12 at 9.54?
@MathsWithJay
4 жыл бұрын
We replace it by 29 - 17 from the top line
Thank you!! this was easy to follow. Great voice, patient.
@MathsWithJay
5 жыл бұрын
@Patricia: Thank you so much!
Thanks so much the explanation was on point ☺️
@MathsWithJay
2 жыл бұрын
You’re welcome 😊
Very helpful, thank you.
@MathsWithJay
4 жыл бұрын
@Amphiaraos: Thank you!
How we can show that 89 | 2^44 - 1 ????
@MathsWithJay
2 жыл бұрын
Is that a congruence?
You explain excellent
@MathsWithJay
3 жыл бұрын
Glad you think so!
doing the matrix version of Euclid's algorithm will cut out having to do that back substitution part.
Great video!
@MathsWithJay
2 жыл бұрын
Thank you!
Very helpful! Thanks for making this.
@MathsWithJay
8 жыл бұрын
And thanks for your feedback; it is appreciated.
Perfect! Thank you!
@MathsWithJay
6 жыл бұрын
Thank you Andrei...and guess what? I also have a samson go mic! Fabulous isn't it?!
@asdgqgqwe
6 жыл бұрын
Agree! It's a steal for the money you pay ! Please keep posting videos, you are really making an impact in many peoples lives! Studying these days will either make or break your career.
Wow! God bless you. My class was moved to an online class due to COVID-19 and I have been struggling so much with this because nobody thoroughly explains it like you just did. Thank you so much.
@MathsWithJay
4 жыл бұрын
Thank you very much Paula-Dee Cameron! It's great to know that this is still so useful!
Good work.
@MathsWithJay
4 жыл бұрын
Thanks! You may also like: kzread.info/dash/bejne/rH16x8qscquoaNI.html
I was stuck with why the multiplication if x*n becomes just x, but now I understand why, I just couldn't see it because my professor thinks it's obvious matter. Thank you!
@MathsWithJay
2 жыл бұрын
You're very welcome!
This is the only explanation of this that makes sense.
@MathsWithJay
7 жыл бұрын
Thanks for letting us know.
Outstanding video lecture.
@MathsWithJay
3 жыл бұрын
Glad you liked it!
What happen to the 4 during backwards induction? It just seemed to dissappear for no reason.
@MathsWithJay
6 жыл бұрын
Where is the 4?
@koleth1
6 жыл бұрын
9:27, when it says "5-2x12+4x5"
@MathsWithJay
6 жыл бұрын
Oh yes, I see where it is. What happens is that 5 + 4 x 5 = 5 x 5.
@koleth1
6 жыл бұрын
ah ok. understood thanks.
thank you Maths with Jay #Respect
@MathsWithJay
6 жыл бұрын
Many thanks Reuben!
Great explanation
@MathsWithJay
5 жыл бұрын
@Zeke Kwok: Thank you!
Thank you!, excellent video
@MathsWithJay
3 жыл бұрын
Glad it helped!
Can also solve with 17x-3 = 29k. Try different values of k, i.e. 0,1,2,... until you get an integer solution for x. With k=4, then x=7. Much easier for small values of k. Otherwise, not practical without a computer.
You just healed my headache
@MathsWithJay
3 жыл бұрын
A new medication for headache?!
@jaunathang
3 жыл бұрын
Yep! It's called "explaining complex concepts with few clear steps instead of throwing a bunch of formulas and hoping your students will figure it out". Altought, you can't find it in drug stores. It's quite rare...
@MathsWithJay
3 жыл бұрын
Thank you!
How 17v = 1 +- 29w?? And why we take -29?? Please respond
@MathsWithJay
Жыл бұрын
At what time in the video?
What if x is a negative number after the linear combination?
@MathsWithJay
5 жыл бұрын
@magenta: Just add a multiple of 29 to make it positive
@magentabottoms1834
5 жыл бұрын
Maths with Jay makes sense thank you!!
what if I had to solve 3x + 2 = 3 (mod 5)? I'm getting confused on + 2 part, Please help
@MathsWithJay
5 жыл бұрын
@ImDHML: Start by subtracting 2 from both sides.
@patelav21
5 жыл бұрын
@@MathsWithJay does that mean it will be 3x = 3(mod 5) - 2 or 3x = 3 - 2(mod 5)? ty for replying
@MathsWithJay
5 жыл бұрын
3 - 2, so 1 (mod 5) Try putting a number in for x, so if x is 4 for example, 3x is congruent to 12, so congruent to 2 mod 5 and 3x + 2 would be congruent to 4, then you can see what happens when you add or subtract 2 from both sides
jay te amo mas que a euclides gracias!!
@MathsWithJay
6 жыл бұрын
Gracias!
What happened to the 4 from 4x5?
@MathsWithJay
5 жыл бұрын
@Haval Mohammed: At what time in the video?
@Haval.M5
5 жыл бұрын
@@MathsWithJay sorry I realized after what happened with it. But timestamp at 8:40. Thanks for a great explanation!
@MathsWithJay
5 жыл бұрын
@Haval Mohammed: OK...Thank you!
help me i don't understand where the 7 come from
@MathsWithJay
5 жыл бұрын
At what time in the video?
Wish youtube had a 3x button.😂. Great video though
@MathsWithJay
5 жыл бұрын
@ANKIT BATCHALI: Thank you! Recent videos are faster.
Where did the 4 go?
@MathsWithJay
2 жыл бұрын
At what time in the video?
grazie signora inglese e grazie anche alla sua pronuncia grazie alla quale ho capito le congruenze
@MathsWithJay
7 жыл бұрын
Grazie
Thanks, this helped.
@MathsWithJay
4 жыл бұрын
@Ismail Wahdan: Thank you!