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.

Given positive integers a,b,c and k:

Define a function $M: \mathbb{Z^2} \rightarrow \mathbb{Z}$ as

$$M(x,y) = (x \bmod y)$$

i.e. the remainder of integer division

The following is always true:

$$a+b=c \implies M(M(a,k) + M(b,k), k) = M(c,k)$$

Under which values of k is the following true:

$$ab=c \implies M(M(a,k)M(b,k), k) = M(c,k)$$

That is when does mod distribute over multiplication?

The answer is always:

Proof:

Let $a = q_ak + r_a$ and $b = q_bk + r_b$ where $ 0 \le r_a, r_b < k$

$$\begin{align*} c &= ab \\ &= (q_ak + r_a)(q_bk + r_b) \\ &= q_aq_bk^2 + q_ar_bk + q_br_ak + r_ar_b \\ &= (q_aq_bk + q_ar_b + q_br_a)k + r_ar_b \\ \end{align*}$$

$$\begin{align*} M(c,k) &= M((q_aq_bk + q_ar_b + q_br_a)k + r_ar_b,k) \\ &= M(r_ar_b,k) \end{align*}$$

$$\begin{align*} M(M(a,k)M(b,k), k) &=(M(q_ak + r_a,k)M(q_bk + r_b,k)) \\ &= M(r_ar_b, k) \end{align*}$$

QED

share|improve this question

1 Answer 1

up vote 3 down vote accepted

Hint $\rm\ mod\ k\!:\ A\equiv a,\, B\equiv b\:\Rightarrow\: AB\equiv ab,\ $ so $\rm\ AB\, mod\, k\, =\, ab\, mod\, k$

Yours is the special case $\rm\ A = (a\,mod\,k),\,\ B = (b\,mod\,k)$

share|improve this answer
    
So the answer is always. So whats the big deal about having a prime base then? Its just having a modular inverse for everything? –  Andrew Tomazos Aug 3 '12 at 14:33
1  
@user1131467 Yes. A prime modulus (not base) is not needed for this. But it is needed if you desire that there exist multiplicative inverses of all elements $\not\equiv 0.$ –  Bill Dubuque Aug 3 '12 at 14:36
    
I tried to prove the answer and added it to the bottom of my question. –  Andrew Tomazos Aug 7 '12 at 1:06
    
@user1131467 Yes, you can also do it that way using only remainders, though it is clearer using congruences as above. –  Bill Dubuque Aug 7 '12 at 2:37

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.