System of congruences, modular arithmetic 

You can already reduce the first step. 15l =2 (mod 7) equivalent to l = 2 (mod 7) (since 15 = 2 * 7 + 1). Mod equations are linear. This means you can reduce factors and addends with the module. Not exponents, though. Also, while you can't divide (in general), you can multiply, and you can find a multiplicative inverse if the number you start with is relatively prime to the module. So if the second equation had simplified to 3k = 4 (mod 5), for such small modules, you can just try it out, and see that 2*3 = 6 = 1 (mod 5) (for larger modules you may need the extended Euclidean algorithm). So you can multiply both sides with 2 instead of dividing by 3 (which leads to k = 3).

Yes we know the rules, this was to provide a proof without skipping steps on how this is true: "15l =2 (mod 7) equivalent to l = 2 (mod 7) (since 15 = 2 * 7 + 1)."

zach p Yes I skipped many steps and didn't label any of them with Axioms. The purpose was a proof of the statement without skipping steps around the mod magic going on rather than a step by step guide through the axioms. I've taken a course which specifically required each step to be outlined and labeled like you mentioned and you quickly get used to it: 15L = 2 (mod 7) "Assumption" => 15L = 7k + 2 for any k in the integers, "by definition of mod" Choose k = 2T where T is an integer (2 and T are integers => 2T is an integer "closure") => 15L = 7(2T) + 2 "Substitution" => 15L = (7*2)T + 2 "Associative multiplication" => 15L = 14T + 2 "Multiplication" => 15L - 14L = (14T + 2) - 14L "Subtraction on both side" => L15 - 14L = (14T + 2) - 14L "Commutative multiplication" => L15 - L14 = (14T + 2) - 14L "Commutative multiplication" => L(15 - 14) = (14T + 2) - 14L "Factorize" => L*1 = (14T + 2) - 14L "Subtraction" => L = (14T + 2) - 14L "Multiplication" => L = (2 + 14T) - 14L "Commutative addition" => L = 2 + (14T - 14L) "Associative addition" => L = (14T - 14L) + 2 "Commutative addition" => L = (7*2T - 14L) + 2 "Multiplication" => L = ((7*2)T - (7*2)L) + 2 "Multiplication" => L = (7*(2T) - (7*2)L) + 2 "Commutative multiplication" => L = (7*(2T) - 7*(2L)) + 2 "Commutative multiplication" => L = 7(2T - 2L) + 2 "Factorize" Let H = (2T - 2L), then H is an integer since: 2 and T are integers => 2T is an integer "closure" 2 and L are integers => 2L is an integer "closure" 2T and 2L are integers => 2T - 2L is an integer "closure" => L = 7H + 2 "Substitution" => L = 2 (mod 7) "Definition of mod"

You don’t have to do that mess, and can just use modular substitution. Since 15 ≡ 1 (mod 7), 15 can be substituted with 1.

Not Your Average Nothing As I mentioned before, this is to show the magic behind: "Since 15 ≡ 1 (mod 7), 15 can be substituted with 1."

Thanks

Thanks , i was struggling in that

what are the |'s?

@@felixfong2667 l was the letter he used in the video, it's a variable like x

Thanks alot :)

Darshan Krishnaswamy thank you!!!!

Do you have any specific problem that you would like me to work out?

Tufan thank you!!

I had a similar solution: cong 1 mod 3 means "1 more than some multiple of 3" and cong 4 mod 5 and cong 6 mod 7 both mean "1 less than some multiple of 5, and 1 less than some mult of 7". We can merge the last 2 equations into cong 34 mod 35 (1 less than some multiple of BOTH 5 AND 7), then check if 35-2 is cong 0 mod 3, in this case we got the correct answer at 1st try! So just add 1 to 33 and x = 34

Jo Hi thank you!!!!!!!!!

Amerendra Kumar thank you!!!

Yay!!!

Happy to help : )

You're welcome!

I don't know which part you didn't understand but the most important part is this. We add 3 things together, ax5x7 + bx3x7 + cx3x5. Why? Because whatever values we choose for a b c, the first term is 0 mod 5 and 0 mod 7 etc. This means that looking at solving for 1 mod 3 we only have to worry about the value of a and we are not messing up the other requirements. Therefore ax5x7=1 mod 3 35a=1 mod 3 2a=1 mod 3 a=2 Let me know if you need more clarification. Once you understamd why it works it becomes easy to remember as well.

The Chinese Remainder Theorem is best proven in Abstract Algebra. It becomes equivalent to finding an explicit isomorphism between certain groups, which is surprisingly straight forward.

Soumya Chandrakar yay!!!! Thank you!!

Do a course on number theory.

: )

"Division in modular arithmetic" is known as the "Cancellation Law" in algebra where ax≡ay implies that x≡y as long as a!≡0. I endorse +VeryEvilPettingZoo for having an excellent set of propositions derived from the very foundations of ring theory.

nice

nice

Niklas Maier thank you!!

Tudi Gaming yay!! Thank yoy

A-Level Further Maths?

A shortcut to CRT!

Try the same with the bases 113, 181 and 197

Great! 15k + 4 = 7l +6 gives 15k - 7l = 2 which is a Bézout identity meaning that gcd(k, l) = 2. So smallest k and l would be 2 and 4.

You can't always. If it says x is congruent to 1(mod 2) and also x is congruent to 2(mod 4) there can be no solution. However something like x is congruent to 1(mod 2) and x is congruent to 1(mod 4), you can just use x ict 1(mod 4).