Solve a Linear Congruence using Euclid's Algorithm 

On this topic, this is arguably the best explanation. Thank you.

Best with 1.25 speed :)

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! 😊

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.

Thank you for the clear explanation of this. I'm taking a discrete math class currently and the book did not explain very well.

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!

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.

Very Nice. Brilliantly explained, and nice and slow!! Thank you!!

A GREAT explanation, easy to follow while writing what you're saying. Thank you for it, love ya!

this what I call a top notch explanation, thank you

I'am german and i never understand a german Video about Linear Congruence. Now i understand it... Awesome work! :)

Great explanation. Keep up the good work (Y)

Thanks Jay! most useful 14 minutes ever!

Thank you for this video It was just so clear...I got it now.

I love this explanation, thank you very much. Hugs from México!

Which method is the most efficient in solving the linear congruence?

Excellent explanation, the best on here by a long way.

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

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)

Excellent explanation, thank you!

This is the 4th video on this topic and I finally understood it.. thank you

Thank you for posting this! very helpful :)

I love you! seriously you saved me

Your voice is really smooth, i like it!

Finally found the best explanation, thank you very much

Thank you very much. Your video helped me ace an exam.

excellent explaination...slow and steady

You are so helpful, Ma'am! Thank you!

Nicely explained as usual

Very much helpful to students in secondary levels.

Should call it maths with bae

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.

What is the program that you write the equations

wow this really helped me get it! thanks!

Amazing!!! you made the process very simple.

very easy to understand thank you

how to solve the same equations in two variables.can we split the va riables in single variables equations.?

Thank you! I finally understand this topic.

Thank you for this!

Thank you very much for this explanation; it was very helpful. :D

Thank you!!!! so much this was a really clear explanation.

Thank you so much from Belgium

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.

Perfect! Thank you!

absolutely loved it

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

Thanks so much the explanation was on point ☺️

thank you finally, after hours of searching

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! :)

Very helpful, thank you.

Very helpful! Thanks for making this.

thank you Maths with Jay #Respect

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?

Thank you so much! I have been trapped on this for weeks..

omg why do i go to lecture when i can come here. THANK YOU JAY

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!

This is the only explanation of this that makes sense.

What if the left hand side has subtraction or addition like 3x − 5 ≡ 4 (mod 7)?

jay te amo mas que a euclides gracias!!

Thank you!! this was easy to follow. Great voice, patient.

3:08 why is it minus 29??

right at the end, congruent to 1. whats that mean? how does 12(17x) = x?

Great video!

Thank you!, excellent video

Better than my cryptography textbook thanks so much!!

Great explanation

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"

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

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

doing the matrix version of Euclid's algorithm will cut out having to do that back substitution part.

grazie signora inglese e grazie anche alla sua pronuncia grazie alla quale ho capito le congruenze

I have to do 13x+5=6x+15 (mod 20) anything special I have to do to deal with the integer addition?

Outstanding video lecture.

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.

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

so we were using euclids algorithm basically if the a and n are laege odd numbers?

You explain excellent

How did we leave with just only x at the last bit please rep thanks

At 2:46 how did you write 17v=1-29w

Good work.

Wish youtube had a 3x button.😂. Great video though

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

How would you do it for both negative solutions?

Thanks, this helped.

thankyou for this.

How to solve linear congruence questions using maple software?

How does 12 x 17x change to be just x in the last step?

Thank you so much

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.

why didn't you just shift the inverse of 17 to the other side and take the modulo of it?

Well, it's an interesting algorithm, but intuitively, it doesn't feel right unless you have a grasp of the underlying arithmetic. Everybody should try at least once to solve the equivalent Diophantine equation by the usual method - you'll find that the amount of computation is the same, and you'll feel more confident with the Euclidean Algorithm. In this case, we want to solve the Diophantine equation 17x = 29a + 3 where x, a are integers. We proceed by consecutive substitutions, each one of which is an integer. Notice how the denominator reduces in size at each step: x = (29a+3)/17 = a + (12a+3)/17 then let b = (12a+3)/17 which must be an integer if x and a are integers as we require. Then we rearrange: a = (17b-3)/12 = b + (5b-3)/12 then let c = (5b-3)/12 b = (12c+3)/5 = 2c + (2c+3)/5 then let d = (2c+3)/5 c = (5d-3)/2 = 2d - 1 + (d-1)/2 [_For the final step I'll use n as the integer (because e might cause confusion)_] then let n = (d-1)/2 which gives d = 2n+1 Each consecutive integer n will then generate solutions. So we can now substitute for d to get c in terms of n, then express b in terms of n, and a in terms of n and finally x in terms of n: c = (5d-3)/2 = (5(2n+1)-3)/2 = 5n+1 b = (12(5n+1)+3)/5 = 12n+3 a = (17(12n+3)-3)/12 = 17n+4 x = (29(17n+4)+3)/17 = 29n+7 Notice how the arithmetic is equivalent to that presented when following Euclid's Algorithm in the video. The solutions are just the same and you can of course check by trying values of n from 0, 1, 2 ... etc. which will each generate a value for x that when multiplied by 17 and divided by 29 will leave a remainder of 3. Working through this kind of "primitive" method may well have been the basis for Euclid's insight into the deeper properties of congruence arithmetic.

Thank you very much

Very much thanks

Here is what i did 17x ≡3(mod29) -12x ≡3(mod29) -3 and 29 are coprime 4x ≡-1(mod29) 4x ≡28(mod29) 4 and 29 are coprime x ≡7(mod29)

What happen to the 4 during backwards induction? It just seemed to dissappear for no reason.

Thank you (math with jay) 😓👍💯

You don't realize how big of a weight you just lifted off of my shoulders.

Bonjour, Solving such equations are much more simply by the pattern of Ouragh . Indeed for the equation treated in the video this scheme is as following .....29........17........12.........5.........2.........1 ..................-1.........-1.........-2........-2 .................12.........-7..........5........-2.........1 and so we have x is congruent to 12 * 3 [ 29] is x = 7 [29] Cordially.

How we can show that 89 | 2^44 - 1 ????