# 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$

 - Multiplication property :
$(A * B) mod C = (A mod C * B mod C) mod C$
$(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

Observe that $(a \bmod M) \bmod M = a \bmod M$

• Thanks for pointing it out! – Robert Jul 19 '18 at 3:22

$(((ax)\bmod M) +b)\bmod M\equiv ((ax)\bmod M)\bmod M +(b\bmod M)$ then use debanjana's hint.

• Thanks for the tip! I think I got the answer! – Robert Jul 19 '18 at 3:23

It should be a basic property that you have proven and know like the back of your hand that

1) $(a\circ b)\mod M = ((a\mod M)\circ (b\mod M))\mod M$ if $\circ$ is addition multiplication or subtraction.

Pf: If $a = a' + kM; 0\le a' < M;$ and $b=b' + jM; 0\le b' < M$ then

if $a'+b' = c + lM; a'-b' = d + vM; a'*b' = g + wM$ then

$a+ b = (a'+b') + (j+k)M = c + (l+j+k)M$ so $(a+b)\mod M = c = (a'+b')\mod M$.

$a - b = (a'-b') + (j-k)M = d + (v+j-k)M$ so $(a-b)\mod M =c= (a'-b')\mod M$.

$ab = a'b' + (j + k)M + jkM^2 = g + wM + (j+k + jkM)M= g+(w+j+k+jkM)M$ so $(ab)\mod M = c= (a'b')\mod M$.

2) And even more basic and obvious $(a \mod M) \mod M= a\mod M$.

Pf: If $a = a' + kM$ so $a\mod M =a'$ then $a' = a' + 0*M$ so $a' \mod M = a'$.

..... So

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

And $((ax\mod M) + b )\mod M = (((ax \mod M) \mod M) + b\mod M)\mod M= ((ax \mod M) +(b\mod M)) \mod M$.