Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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)?

share|improve this question
3  
Not quite: what's true is that $$(a+b)\bmod c=\Big(a+(b\bmod c)\Big)\bmod c\;.$$ –  Brian M. Scott May 3 '12 at 7:34
    
@BrianM.Scott: Thanks! I think this identity will also be helpful. But is there a way to prove it? –  maths-help-seeker May 3 '12 at 7:37
    
It follows pretty easily from basic modular arithmetic; are you familiar with the meaning of $a\equiv b\pmod m$? –  Brian M. Scott May 3 '12 at 7:42
    
Thank you for the pointers! I will look into it! –  maths-help-seeker May 3 '12 at 7:45
    
@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.) –  Tara B May 4 '12 at 9:51

2 Answers 2

up vote 1 down vote accepted

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 $<c$. Also, if $a,b$ are already in $\{0,\cdots,c-1\}$ they are un-affected and we would have $(a+b)\%=a+b$. But the sum of two numbers $<c$ is not necessarily itself less than $c$; what if $a=c-1$ and $b=1$ for instance? Thus it is not additive.

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

share|improve this answer
    
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)? –  maths-help-seeker May 4 '12 at 9:37
    
@maths-help-seeker I've added some more to the answer. –  anon May 4 '12 at 9:53
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$. –  anon May 4 '12 at 9:56

$(a+b)\bmod c=n$ if and only if $(a+b)-n$ is divisible by $c$, and $0\le n<c$: $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'<c$, and $b\bmod c=b'$ if and only if $b-b'$ is divisible by $c$, and $0\le b'<c$.

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<c$, but all we know about $a'+b'$ is that $0\le a'+b'\le 2c-2$, since $0\le a'\le c-1$ and $0\le b'\le b-1$. Thus, $a'+b'$ is either $n$, or $n+c$, but we can't be sure which. If we let $m=(a'+b')\bmod c$, however, then $m$ and $a'+b'$ have the same remainder on division by $c$, so $m$ and $n$ have the same remainder on division by $c$. Moreover, $0\le m<c$ and $0\le n<c$, so $m$ and $n$ must be the same number. We've now shown that in general $$(a+b)\bmod c=\Big((a\bmod c)+(b\bmod c)\Big)\bmod c\;.\tag{1}$$ In your case $0\le a<c$, so $a\bmod c=a$, and $(1)$ reduces to $$(a+b)\bmod c=\Big((a+(b\bmod c)\Big)\bmod c;.$$

share|improve this answer
    
: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)? –  maths-help-seeker May 4 '12 at 9:37

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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