Is there a way to simplify this expression $(a + b) \% c$

Question

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

Answer 1

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

Answer 2

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