When can we 'divide' in a linear congruence? (Number theory basics)

When can we divide both sides of congruence by the same number?
discrete math, number theory, abstract algebra,

[KFALBEAST]

holy crap dude 110k?! nice!! you've come a long way

[Bermatematika]

IMHO it is better to introduce first the notion of inverse element. Then you can say that when an element has an inverse element then you can divide. In this way you may have a self contained video where you can explain why you need gcd(k, n)=1. Just my two cents :)

[drapsag]

I don't know about English notations but in France we usually write a=b[n] instead of a=b (mod n), that's faster lol.

[matthieub]

Thanks to talk about this subject, I study congruences at school and sometimes it's a bit difficult, so you help me to understand with your videos, thanks and continue you're great !

[darshankrishnaswamy]

Can you please post soon? I can't go this long without your amazing videos.

[namangupta]

I just love the way he speaks "Mod", :-)

[daze-telltaleshtposts]

You are a legend. Clearly explained, straight to the point. Good vid

[darshankrishnaswamy]

Also, can you do some more of those live videos? Those are always fun.

[mathieuj]

Your video entitled "weekly brilliant problem#3, solving integral by symmetry, IIT JEE mains 2015" has over 20k views, and you promised to do the integral in the vid when it reached that number. Can't wait ;)

[ffggddss]

Works iff divisor and modulus are relatively prime.
Note: Whenever you see, a ≡ b (mod n), you should immediately think, a–b = mn, where m is an integer. This is the *definition* of congruence.
That will make this result more obvious.

Fred

[christinerudolph]

Looking forward to your next "This is IT!" videos after your creative break... ;-) Are you planning for some complex analysis? More videos with Dr. Peyam?

[tommyrosendahl]

when will you make another video?? love them to bits!

[Jack-cmch]

Please do proof by induction. Like 3n<2^n

[alanturingtesla]

We want new videos! Almost two weeks since this one.

[_Yeibi_]

Could you show and demostrate the derivative and integral of x!, please? Thank u.

[alexrupsee]

Hey blackpenredpen YAY, I’m a high school math student and I wanted to know: what is 1 / infinitely? Thanks!!!

[vaishnavchincholkar]

sir, can you please make a video on derivation of a formula to find product of all binomial coefficients

[Lu_Ca]

@blackpenredpen I think you are missing a video with the square trick that can be found in the integral of e^(x) * e^-0.5(x^2) / sqrt(2pi)

[christianalbertjahns]

I have general simplification for ka congruence kb (mod n). I don't know whether anyone else has do it (make it patent) but it's quite easy to do so.

By definition, a congruence b (mod n) means there exists at least one integer c which makes a - b = cn. So ka congruence b means there exists at least one integer c which makes ka - kb = cn. Of course, we also can write it as k(a-b) = cn

Let gcd(k, n) = g.
-> ka congruence kb (mod n)
-> There exist an integer c, which makes ka - kb = cn
-> k(a - b) = cn
-> (k/g)(a - b) = c(n/g) (by dividing both side with g, the result is guaranteed to be integer)
-> (k/g)a - (k/g)b = c(n/g)
-> (k/g)a congruence (k/g)b (mod n/g)


Of course, this simplification only helps if gcd(k, n) not equals to 1. If it equals to 1, your method works better.

In the example above: 30 congruence 42 (mod 4)
-> 6*5 congruence 6*7 (mod 4)
-> gcd(6, 4) = 2
-> (6/2)*5 congruence(6/2)*7 (mod 4/2)
-> 3*5 congruence 3*7 (mod 2)
-> 15 congruence 21 (mod 2)

[hc_]

What about dividing the modulo number by gdc(k, n)? Like 30 = 42 (mod 4), 5=7 (mod 2).