2
$\begingroup$

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

  • 0
    No reference, sorry, but I've extended my comment to an answer that contains an argument in lieu of authority.2011-09-14

4 Answers 4

3

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.

1

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

  • 0
    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).2011-09-15
1

$\begin{align}{\bf Hint}\qquad\qquad \rm (x - y\ q)\ \ mod\ q\ \ &=\ \ \rm x\ \ mod\ q\quad\ \ for\ all\ integers\ x,\:y \\ \rm \Rightarrow\quad a\ (b + \color{#c00}{c\, -\, n\:q)}\: \ mod\ q\ \ &=\rm\ \ (\color{#0a0}{ab\ -\ j\ q}\ +\ \color{#b0f}{ac\ -\ k\:q)}\:\ mod\ q \\ \rm \Rightarrow\quad a\ (b + \color{#c00}{c\ mod\ q})\: \ mod\ q\ \ &=\rm\ \ (\color{#0a0}{ab\ mod\ q}\ +\ \color{#b0f}{ac\ mod\ q)}\:\ mod\ q \end{align}$

The first $\Rightarrow$ follows since both sides equal $\rm\:\ ab+ac\ \ mod\ q\:\ $ by the first identity, and the 2nd arrow uses ($3$ times) that $\rm\: m\ mod\ q\ =\ m - i\ q\ $ for some integer $\rm\:i\,$ (in the colored terms).

If you know congruence arithmetic then you may find it more insightful to reformulate the above using $\ x\equiv y\pmod{\!q}\iff x\bmod q\, =\, y\bmod q,\,$ and the Congruence Sum, Product Rules. This yields a more conceptual view of the essence of the matter, one that will be algebraically reified when you learn how to view $\,\Bbb Z\bmod q\,$ as a ring (the quotient/residue ring $\,\Bbb Z/q)$.

1

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