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

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

  • 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', and $b\bmod c=b'$ if and only if $b-b'$ is divisible by $c$, and $0\le b'.

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, 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 and $0\le n, 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, so $a\bmod c=a$, and $(1)$ reduces to $(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