3
$\begingroup$

I am having an expression of the form $ (a+b) \% c $ where a,b,c are positive integers greater than or equal to zero (natural numbers). $\%$ indicates modulo operation.

Also, there is a restriction on $a$ i.e. $ 0\le a < c $.

Is there a way to simplify this expression. for example, Can we say that $ (a + b) \% c $ = $ a + (b \% c) $ ? Is this always true and if yes, then how to prove it?

Or are there other ways to simplify it? $b$, $c$ can be any natural numbers.

Edit#1: In general then can we also say that it is true for (a + b + ...) \% c and (a.b)\%c (which is (a+a+a+....b times) \% c)?

  • 3
    Not quite: what's true is that $$(a+b)\bmod c=\Big(a+(b\bmod c)\Big)\bmod c\;.$$2012-05-03
  • 0
    @BrianM.Scott: Thanks! I think this identity will also be helpful. But is there a way to prove it?2012-05-03
  • 0
    It follows pretty easily from basic [modular arithmetic](http://en.wikipedia.org/wiki/Modular_arithmetic); are you familiar with the meaning of $a\equiv b\pmod m$?2012-05-03
  • 0
    Thank you for the pointers! I will look into it!2012-05-03
  • 0
    @maths-help-seeker: You don't need to post the new question as comments on every answer as well as in the main question! Also, the question is not very well-posed. Can we also say that _what_ is true? (I'm pretty sure I know what you mean, but it's good to learn to ask questions well.)2012-05-04
  • 0
    @TaraB: you are right! I will remember this for the future.2012-05-04

2 Answers 2

1

The modulo operator $a\mapsto a\%c$ sends $\Bbb Z\to\{0,1,\cdots,c-1\}.$ (This is the domain and range.)

Now, is $\%c$ an additive function? That is, does $(a+b)\%c=a\%c+b\%c$? Notice we would have to have the latter two add to a number $

Notice that $(x\pm c)\%=x\%c$ for any $x$. That is, it is a periodic function. Moreover, if we subtract the remainder $x\%c$ from $x$ we will end up with a multiple of $c$. Symmetrically, if we subtract this multiple of $c$ from $x$ we obtain the remainder $x\%c$! So, if this "multiple of $c$" is $nc$ for $x=a$ and then $mc$ for $x=b$, by the periodicity condition we have

$$(a+b)\%c=(a-nc+b-mc)\%c=(a\%c+b\%c)\%c=(a+b\%c)\%c.$$

Remember that $a$ is already in the range of $\%c$ so $a\%c=a$. This is the best we can say at this level of generality on the variable $b$. We cannot remove the final $\%c$; remember our $b=1,a=c-1$ example. (This is a rather longwinded reasoning process that more or less mirrors the perhaps more efficient deduction possible using modular arithmetic and basic elementary number theory.)


Yes, it is true that $$(a_1+\cdots+a_n)\%c=(a_1\%c+\cdots+a_n\%c)\%c \tag{$*$}$$

This can be proven just as with the $n=2$ case. Use modular reduction to say that

$$a_i=m_ic+a_i\%c$$

for each $i=1,\cdots,n$. Then by periodicity we have

$$(a_1+\cdots+a_n)\%=\big((a_1-m_ic)+\cdots+(a_n-m_nc)\big)\%c=(a_1\%c+\cdots+a_n\%c)\%c \tag{$\circ$}.$$

Using this, we have

$$(\underbrace{a+\cdots+a}_b)\%c=\big(\underbrace{a\%c+\cdots+a\%c}_b)\%c=\big(b\cdot(a\%c)\big)\%c. \tag{$\bullet$}$$

By setting each $a_i=a$ and $n=b$ in the formula $(\circ)$.

Furthermore, setting $b=\ell c+b\%c$, by periodicity again we have

$$\big(b\cdot(a\%c)\big)\%c=\big(b(a\%c)-\ell(a\%c)c\big)\%c=\big((b-\ell c)(a\%c)\big)\%c=\big((b\%c)(a\%c)\big)\%c.$$

  • 0
    In general then can we also say that it is true for (a + b + ...)\% c and (a.b)\%c (which is (a+a+a+....b times)%c)?2012-05-04
  • 0
    @maths-help-seeker I've added some more to the answer.2012-05-04
  • 1
    The key ideas to remember are that the argument of the $\%c$ function can be augmented by any multiple of $c$, and any $x$ differs from $x\%c$ by a multiple of $c$.2012-05-04
2

$(a+b)\bmod c=n$ if and only if $(a+b)-n$ is divisible by $c$, and $0\le n: $n$ is the smallest non-negative integer that has the same remainder as $a+b$ on division by $c$. Similarly $a\bmod c=a'$ if and only if $a-a'$ is divisible by $c$, and $0\le a'

I claim that $a'+b'$ and $n$ have the same remainder when divided by $c$. Since $a-a'$ is divisible by $c$, there is an integer $i$ such that $a-a'=ci$. Similarly, there are integers $j$ and $k$ such that $b-b'=cj$ and $(a+b)-n=k'$. This implies that

$$\begin{align*} (a'+b')-n&=(a'+b')-(a+b)+(a+b)-n\\ &=(a'-a)+(b'-b)+\Big((a+b)-n\Big)\\ &=-ci-cj+ck\\ &=c(k-i-j)\;, \end{align*}$$

so $(a'+b')-n$ is a multiple of $c$, and therefore $a'+b'$ and $n$ have the same remainder on division by $c$. They might not be equal, however, because $a'+b'$ might be bigger than $n$: we know that $0\le n$$(a+b)\bmod c=\Big((a\bmod c)+(b\bmod c)\Big)\bmod c\;.\tag{1}$$ In your case $0\le a$$(a+b)\bmod c=\Big((a+(b\bmod c)\Big)\bmod c;.$$

  • 0
    :In general then can we also say that it is true for (a + b + ...)\% c and (a.b)\%c (which is (a+a+a+....b times)%c)?2012-05-04