Discrete Math - 4.4.1 Solving Linear Congruences Using the Inverse

Exploring how to find the inverse of a linear congruence and how to use the inverse to solve the linear congruence.

Video Chapters:
Introduction 0:00
What is a Linear Congruence 0:06
Find the Inverse mod a 1:50
Using the Euclidean Algorithm and Linear Combinations to Solve a Linear Congruence 5:12
Up Next 13:36

Textbook: Rosen, Discrete Mathematics and Its Applications, 7e

[TearZBot]

I was having so much trouble understanding this before watching your video. After watching this video just once, it suddenly made perfect sense to me. You're amazing, thank-you so much.

[benthomas]

Seems to be a small error at 11:51, you meant to say "take -17 times 6".

[lightning_]

Thank you so much, this process was so confusing before and now it makes sense.

[ethanjossi]

Thank you so much! This helped me understand it. Video production quality was extremely well done.

[nitac]

Thank you so much . i finally understand the concept. all other methods were so difficult.

[Treant.]

Thank you! You were the only one I can understood this topic.

[Charlakin]

Fabulous video, this made everything so much more sense!

[gianlucasperti]

Sorry I have some questions:
1)If we have a linear congruence the number of solutions will be GCD(a, n), in our case it's 1 and it has one solution, but should I see it has ONE SET of solutions? Because the solution would be infinite by adding the n value.
2)If I have a GCD =13 how do i represents these sets of solutions?
3)Will we haver have infinite sets of solutions? (I think no because GCD should be equals to infinite but i'm curious)
Thank you

[bluejimmy]

At 2:11, you said that a and m has to be relatively prime. Why does it have to be relatively prime? What happens if a and m are not relatively prime? Does it mean no inverse if a and m are not relatively prime?

[jaydeestrada]

shouldn't it be a*a^-1 is congruent to 1 (mod m), rather than equals!

[ernestodones]

question, is not 6 (mod 37) = 6? therefore after substitution in the initial equation we got 13x=6 and then simply x = 6/13? why can't we just do that?

[sagivalia]

So the solution for the last question can be written as an arithmetic series with d=37?

[abdullahalhashmi]

Finally I understand it, thank you very much.

[sarag.regassa]

This is amazing!! Thank you so muchh!!

[m-qzmi]

its 1=2(37)-9(13) inverse is -9 not -17. I suppose you did some mistake when u were working backwards from the Euclidean algo

[Mauri-]

When it came time for my exam and I implemented step 4 shown at 12:00, my professor ended up taking points off for notation lol. Turns out he expected a congruence symbol rather than an equals sign. ¯\_(ツ)_/¯

[colonelh.s.l.]

Hi, how did you get 3(2) = 5(1) +1 to begin with?

[SortedSand]

Add a video for Theorem 4.5.1 and 4.5.2

[kylecho]

I’d prefer to use extended Euclidean to find gcd and certificate of correctness in one shot

[StarmonYT]

I just- I don’t understand, how can -17 * 13 be 1, thats not how math works, if you multiplied -17 with 13x you’d get -221X, I can’t wrap my head around how we change that