Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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:


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


share|cite|improve this question
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|cite|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
@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


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.