4
$\begingroup$

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

1 Answers 1

5

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

  • 0
    @user1131467 Yes, you can also do it that way using only remainders, though it is clearer using congruences as above.2012-08-07