0
$\begingroup$

This question already has an answer here:

Let $a,b \in \mathbb {Z} $ and let $m$ be an integer greater than $2$. I found a counterexample to the equation

$$(a+b)\mathrm {mod} m = a\mathrm {mod} m + b \mathrm {mod} m $$

where $m>2$. But that was only after I thought I had proven that the equation does hold, so I was wondering if someone could point out to me where the flaw is in the following.

If we divide $a $ and $b $ by $m $, then we have by the division algorithm

$$a=mc+x $$ $$b=md+y $$

Adding the equations together renders

$$a+b=me+(x+y) $$

And since $a\mathrm {mod} m + b \mathrm {mod} m= x+y $, then from the third equation, it seemes that the proposition holds.

$\endgroup$

marked as duplicate by Bill Dubuque elementary-number-theory Nov 25 '16 at 23:24

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • 2
    $\begingroup$ What if $x+y$ is greater than $m$? $\endgroup$ – Michael Burr Nov 25 '16 at 23:14
  • 1
    $\begingroup$ You can seperate it, but you need to mod the result. $a+b\mod m=(a\mod m+b\mod m)\mod m$. $\endgroup$ – AlgorithmsX Nov 25 '16 at 23:18
2
$\begingroup$

$a\mod m+b\mod m=x+y$
This part is not always true.

Suppose $x=m-1$ and $y = m-1$

$x+y = 2m-2$

But
$a\mod m+b\mod m$
would actaully be $m-2$.

$\endgroup$
1
$\begingroup$

Actually, the formula should be $$(a+b)\bmod m\equiv (a\bmod m+b\bmod m)\bmod m.$$ That's why computing in the ring $\mathbf Z/m\mathbf Z$ is simpler than computing with congruence classes in $\mathbf Z$.

$\endgroup$

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