# Distributivity mod an integer

Let $a,b,c,m \in \mathbb{Z}$, is it always the case that $$a((b+c) \text{ mod } q) \text{ mod } q = (ab \text{ mod } q + ac \text{ mod } q) \text{ mod } q$$

-
Thanks, do you have any reference? –  Li-thi Sep 14 '11 at 22:04
No reference, sorry, but I've extended my comment to an answer that contains an argument in lieu of authority. –  Henning Makholm Sep 14 '11 at 22:06

Yes. When doing modular arithmetic you can take the modulus as often or seldom as you want to before you reach the final result, as long as you only do addition, subtraction and multiplication, and always end with a modulus. So your equation is equivalent to $a(b+c)\equiv ab+ac \pmod q$.

The formal justification for this is that when you're doing computations in $\mathbb Z/q\mathbb Z$, you can use any representative for each residue class you want for each operation, and the "mod $q$" just exchanges one representative for another for the same class. Only the final "mod $q$" is important; it ensures that if you have the same residue class on both sides, you will get the same representatives.

-

Note that the result can be shown by brute force, so to speak, without any group theory.

Let $n = a((b+c) \text{ mod } q) \text{ mod } q$; then $a((b+c) \text{ mod } q) = n + dq$ for some integer $d$. Similarly, $b+c = (b+c) \text{ mod } q + eq$ for some integer $e$, so \begin{align*}a(b+c) &= a[(b+c)\text{ mod }q+eq]\\ &=n+(d+ae)q. \end{align*}

Now let $m = (ab \text{ mod } q + ac \text{ mod } q) \text{ mod } q$. Then $ab \text{ mod } q + ac \text{ mod } q = m + fq$ for some integer $f$. Similarly, $ab = ab \text{ mod } q +gq$ and $ac = ac \text{ mod } q +hq$ for some integers $g$ and $h$, so \begin{align*}ab+ac &= (ab \text{ mod }q+gq)+(ac \text{ mod }q + hq)\\ &=(ab \text{ mod }q + ac \text{ mod }q) + (g+h)q\\ &=m+(f+g+h)q. \end{align*}

Then \begin{align*}n-m &= [a(b+c)-(d+ae)q] - [ab+ac-(f+g+h)q]\\ &=[a(b+c)-(ab+ac)]-[(d+ae)q-(f+g+h)q]\\ &=(f+g+h-d-ae)q, \end{align*} so $q \mid (n-m)$. But $0 \le m,n < q$ by the definition of the mod function, so $\vert n-m\vert < q$, and we must have $n-m=0$, i.e., $n=m$.

-

HINT \quad \rm\begin{align} x\ -\ y\ q\ \ mod\ q\ \ &=\ \ \rm x\ \ mod\ q\quad\ \ for\ all\ integers\ x,\:y \\ \rm \Rightarrow\quad a\ (b + c\ -\ n\:q)\: \ mod\ q\ \ &=\rm\ \ (ab\ -\ j\ q\ +\ ac\ -\ k\:q)\:\ mod\ q \\ \rm \Rightarrow\quad a\ (b + c\ mod\ q)\: \ mod\ q\ \ &=\rm\ \ (ab\ mod\ q\ +\ ac\ mod\ q)\:\ mod\ q \end{align}

since both sides equal $\rm\:\ ab+ac\ \ mod\ q\:\$ by the first identity. Notice that we have invoked above three times the basic identity $\rm\: m\ mod\ q\ =\ m - i\ q\$ for some integer $\rm\:i\:.\:$

If you have knowledge of congruence arithmetic then you may find it of interest to reformulate the above using such. This will yield a much more conceptual view of the essence of the matter.

-
All the normal distributive, commutative and associative laws of $\mathbb{Z}$ are preserved modulo any $q$; this can be seen as how the factor ring $\text{ }\mathbb{Z}_q$ "inherits" the nice arithmetical properties of the base ring $\mathbb{Z}$.
If you put \text{ } (with a space) before glitchy ascended markup it will make it look normal (at least I think it works in general). –  anon Sep 15 '11 at 2:39