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