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 a≡b(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→((amodM⋅xmodM)modM+b)modM (multiplication property)
And if I develop the right side of the Equation :
(ax+b)modM=(axmodM+bmodM)modM
Which gives this after applying the multiplication property :
(((amodM⋅xmodM)modM)+bmodM)modM
So I have
((amodM⋅xmodM)modM+b)modM=(((amodM⋅xmodM)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