1

It is known that $(a + b) \bmod n = [(a \bmod n) + (b \bmod n)] \bmod n$, but is it possible that the following are also true?

  • $(a + b) \bmod n = [(a \bmod n) + b] \bmod n$
  • $(a + b) \bmod n = [a + (b \bmod n)] \bmod n$

I've been trying all sorts of tests/combinations (of positive integers, mind you) and it always seems to work. For example, with $a = 7, b = 8, n = 6$:

  • $(7 + 8) \bmod 6 = 15 \bmod 6 = 3$
  • $[(7 \bmod 6) + 8] \bmod 6 = [1 + 8] \bmod 6 = 9 \bmod 6 = 3$
  • $[7 + (8 \bmod 6)] \bmod 6 = [7 + 2] \bmod 6 = 9 \bmod 6 = 3$
  • $[(7 \bmod 6) + (8 \bmod 6)] \bmod 6 = [1 + 2] \bmod 6 = 3 \bmod 6 = 3$

I've tried it with a dozen different combinations and it always works out. What I would love to know is: am I wrong? If so, is there a good counter-example? If not, how could the veracity of this property be explained/proved, and how come it never shows up in the usual definition of the distributive property of modulo? It's really bugging me, because I'm sure I'm right, but I can't for the life of me find any documentation on this and/or properly demonstrate my case.

Thanks!

Sil
  • 16,612
QCyrax
  • 13
  • 2
    Yes those observations are correct. – Sil Jul 28 '20 at 14:59
  • @Sil Thank you for confirming my thoughts. Do you have any idea where I could find documentation with an explanation or proof for this particular situation? I've tried a lot of Google searches, but to no avail. – QCyrax Jul 28 '20 at 15:28
  • See my answer, and also the linked answer of Brian, they should give you enough info. It turns out that the first equality you already know can be used quite simply to derive the two others. – Sil Jul 28 '20 at 15:58

2 Answers2

0

As mentioned in comments, this can be shown as in the answer of @BrianM.Scott in Is there a way to simplify this expression $(a + b) \% c$.

However, in your case it seems you take $$(a + b) \bmod n = [(a \bmod n) + (b \bmod n)] \bmod n\tag{*}$$ for granted, so I will show how to use that. Since $(*)$ holds for all integers $b$, we can substitute $b=c \bmod n$. But then $(*)$ gives us $$ (a + (c \bmod n)) \bmod n = [(a \bmod n) + ((c \bmod n) \bmod n)] \bmod n. $$ Since taking remainder by division repeatedly gives the same result, we have $((c \bmod n) \bmod n)=c \bmod n$, and so $$ (a + (c \bmod n)) \bmod n = [(a \bmod n) + (c \bmod n)] \bmod n. $$ But right hand side is again by $(*)$ equal to $(a+c) \bmod n$. Thus we have shown $$ (a + (c \bmod n)) \bmod n = (a+c) \bmod n, $$ which is one of the equalities you have observed (simply substitute $b$ for $c$). We get also the second equality for free, because $+$ is commutative.

Sil
  • 16,612
0

Of course it's true.

Suppose $a \mod n = a'$. That means $0 \le a' < n$ and $a = jn + a'$ for some integer $j$.

Suppose $b \mod n = b'$. That means $0 \le b' < n$ and $b = kn + b'$ for some integer $k$.

And let's suppose $(a'+b') \mod n = R$ so that $a' +b' = mn + R$.

(Note: because $a', b' < n$ that means either $a' +b' < n$ and $m = 0$ and $R = a'+b'$ or that $n \le a' + b' < 2n$ and $m =1$ and $R = (a'+b') - N$.... but none of that is important.)

So let's look at your expressions:

  • $(a+b)\mod n=[(a\mod n)+b]\mod n$

$(a+b) = (jn+a')+(kn+b') = (j+k)n + (a'+b') = (j+k)n + mn + R = (j+k+m)n + R$.

So $(a+b)\mod n = R$.

And $(a\mod n) + b = a' + b = a' + kn + b' = kn + (a' + b') = kn + mn + R = (k+m)n + R$.

So $[(a\mod n) + b]\mod n = R$.

So the above is true

  • $(a+b)\mod n=[a+(b\mod n)]\mod n$

Again $(a+b)\mod n = R$.

And $(a + (b\mod n) = a + b'= jn + a' + b' = jn + mn + R = (j+m)n + R$.

So $[(a+b)\mod n = R$.

fleablood
  • 124,253