Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
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
add comment

4 Answers 4

up vote 3 down vote accepted

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.

share|improve this answer
add comment

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

share|improve this answer
add comment

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.

share|improve this answer
add comment

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

share|improve this answer
    
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.