Better way to solve systems of linear congruences in general
-
Note: this requires knowledge about modular inverses.
$$x\equiv 3\pmod{4} $$ $$x\equiv 2\pmod{11} $$
Suppose you have the systemwhich was used in the mini-question.
$$4a+3\equiv 2\pmod{11}\implies 4a\equiv -1\pmod{11}\implies 4^{-1}\cdot 4a\equiv -1\cdot 4^{-1}\pmod{11}\implies a\equiv 8\pmod{11}. $$
By CRT (Chinese Remainder Theorem), we know that there is a unique solution modulo \(44\) that satisfies the system. From the first congruence, we see that \(x\) can be expressed as \(4a+3\) where \(a\) is a positive integer.
Substituting this into the second congruence, we getThis means that \(a=11b+8\), where \(b\) is another positive integer. Substituting this into \(x=4a+3\), we get \(x=4(11b+8)+3=44b+35\). Therefore, \(x\equiv 35\pmod{44}\). From this, you would get the answer of \(0\) for the mini-question.
Anyways, I made this post to emphasize a different way to solve systems of linear congruences, which I found from AoPS.
(I usually use this method to solve modular congruences, but if numbers are small enough, I usually end up using guess and check. Also, mods, can you check this?) -
This is a very nice and interesting way to solve modular congruences!
What is this method called?
-
@西瓜 There isn't a name. This method can be used to solve systems of modular congruences in general: bigger numbers, etc.
-
Okay, thanks!
@professionalbronco
