5

I would like to know if the modulo operation has distributivity like this:

$$A+B+C \pmod{M} = (A+B)\pmod{M} +C \pmod{M}$$?

Does the equality hold true?

alkabary
  • 6,214
lopata
  • 319
  • We have $\overline{a}+\overline{b}=\overline{a+b}$, with $\overline{a}=a \bmod m$, and you can iterate this for $a,b,c$. – Dietrich Burde May 21 '15 at 18:36
  • In what you wrote, $A+B$ is atomic, so you'd better have written $D+C\pmod M=D\pmod M+C\pmod M$. And the meaning of such an equation remains ambiguous, see my answer. –  Feb 27 '17 at 17:38

4 Answers4

17

Your notation with $\pmod M$ is not quite appropriate. You normally use it in sentences with the equivalence operator

$$8\equiv 5\pmod3.$$

When used as an operator, the usual syntax holds

$$8\bmod3=5\bmod3=2.$$

This said, your "distributivity rule" doesn't hold because

$$(A+B)\bmod M\ne A\bmod M+B\bmod M$$ in the cases where the RHS exceeds $M-1$. The rule that holds is

$$(A+B)\bmod M=(A\bmod M+B\bmod M)\bmod M$$ which you can also write

$$(A+B)\bmod M\equiv A\bmod M+B\bmod M\pmod M.$$

So, yes, the distributivity law holds "modulo $M$".

7

This is often a point of confusion when talking between computer programmers and mathematicians.

The OP seems to be using modulo as an operator; and that operator is NOT distributive. If we let $\%$ be the the 'modulus' operator (as it is usually denoted in computer languages) then

$$(2 + 2) \% 3 = 1 \neq (2 \%3) + (2 \% 3) = 2 + 2 = 4$$

In mathematical discourse, modulus is not an operator.

Chas Brown
  • 1,660
  • Modulus (or modulo) is also an operator. LaTeX defines \mod as well as \bmod. –  Feb 27 '17 at 17:26
3

If I understand your question, then it does hold. Addition and multiplication is association under modulos.

One way to see this is to note that $a \equiv b$ (mod $n$) means that $a$ and $b$ have the same remainder when dividing by $n$. Now the remainder of $a + b + c$ by division by $n$ is the same as the remainder of $a+b$ plus the remainder of $c$ (take this sum mod $n$).

One way you can state this algebraically is to let $[a]$ denote the equivalence class of all $b$ such that $a \equiv b$ (mod $n$). The equivalence relation is $a\sim b$ if $a\equiv b$ (mod $n$). Then in this case you indeed have that $[a+b + c] = [a+b] +[c]$. In fact this is usually taken as the definition of how to add these equivalence classes.

Thomas
  • 43,555
0

In fact, Distribution Properties for module M holds for addition, subtraction and multiplication for integers.

Check this section for examples:

https://en.wikipedia.org/wiki/Modular_arithmetic#Integers_modulo_n

cpchung
  • 101