# Modulus Distributing Over Multiplication?

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

-

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