Monday 11 February 2013

Solving a congruence/modular equation : $(((ax) mod M) + b) mod M = (ax + b) mod M$

I've been trying to prove this equation for my homework.



$$(((ax) \bmod M) + b) \mod M = (ax + b) \bmod M$$



We have that $a,x,b,M > 0$, and $a ≡ b \pmod M$






Reading KhanAcademy website, I found the following properties that looked promising.




- Multiplication property :
\[(A * B) mod C = (A mod C * B mod C) mod C\]
- Addition property :
\[(A + B) mod C = (A mod C + B mod C) mod C\]




I tried developping the left side of the Equation :



$(((ax) \bmod M) + b) \bmod M \rightarrow((a \bmod M \cdot x \bmod M) \bmod M + b) \bmod M$ (multiplication property)





And if I develop the right side of the Equation :



$$(ax + b) \bmod M = (ax \bmod M + b \bmod M) \mod M$$ (addition property)




Which gives this after applying the multiplication property :



$$(((a \bmod M \cdot x \bmod M)\bmod M) + b \bmod M) \bmod M$$




So I have



$$((a\bmod M\cdot x \bmod M)\bmod M+b) \bmod M = (((a \bmod M \cdot x \bmod M)\bmod M) + b \bmod M) \bmod M$$






It's almost the answer, but one side has $b \bmod M$ and the other only has $b.$ I've been looking for more congruence properties but I can't seem to find one that would allow me to solve my problem. Have I been tackling this problem from the correct angle? Or did I make a mistake from the beginning (by applying the addition and multiplication properties)?





Any help would be greatly appreciated! Thanks

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}...