Monday, 21 May 2018

abstract algebra - How to solve system of equations with mod?



I'm trying to solve for a and b:
5(4a+b)mod
I tried looking it up online, and the thing that seemed most similar was the Chinese remainder theorem; however, I couldn't find an instance where it fit something more like what I want to solve. A simple explanation or a reference to one would be most appreciated.




With my (limited) knowledge of algebra, I figured out that x\ \textrm{mod}\ 26 = x - 26\lfloor\frac{x}{26}\rfloor, so I tried substituting that into my equations:
5=(4a+b)-26\left\lfloor\frac{4a+b}{26}\right\rfloor\quad\text{and}\quad 22=(7a+b)-26\left\lfloor\frac{7a+b}{26}\right\rfloor.



And I figured I could do something with that since I got rid of the mod, but... I have never solved an equation with a floor function before.


Answer



Well, mod is easier to handle. We have only m numbers \pmod m: 0,1,\dots,m-1 and already m\equiv 0 (also, -1\equiv m-1), it goes in a cycle just like the hours in a day \pmod{12}.



Precisely, a\equiv b \pmod m means \ m|(a-b), and the arithmetic operations such as +,-,\cdot are very friendly with it, \equiv acts just like an equation.



You can try to solve it, like b\equiv 22-7a \pmod{26}, then substitute it back to the other, 5\equiv -3a+22 , so 3a\equiv 17, but \pmod{26} this 17 can be substituted by -9 for example (because 17\equiv -9 \pmod{26}), and 3 is coprime to 26 so one can divide by 3.



No comments:

Post a Comment

real analysis - How to find lim_{hrightarrow 0}frac{sin(ha)}{h}

How to find \lim_{h\rightarrow 0}\frac{\sin(ha)}{h} without lhopital rule? I know when I use lhopital I easy get $$ \lim_{h\rightarrow 0}...