0
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Thanks for pointing it out! $\endgroup$ – Robert Jul 19 '18 at 3:22
0
$\begingroup$

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

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

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.