Monday, 11 February 2013

Solving a congruence/modular equation : (((ax)modM)+b)modM=(ax+b)modM

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



(((ax)modM)+b)modM=(ax+b)modM



We have that a,x,b,M>0, and ab(modM)






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)modM)+b)modM((amodMxmodM)modM+b)modM (multiplication property)





And if I develop the right side of the Equation :



(ax+b)modM=(axmodM+bmodM)modM

(addition property)




Which gives this after applying the multiplication property :



(((amodMxmodM)modM)+bmodM)modM




So I have



((amodMxmodM)modM+b)modM=(((amodMxmodM)modM)+bmodM)modM






It's almost the answer, but one side has bmodM 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 limhrightarrow0fracsin(ha)h

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