1
$\begingroup$

I am trying to prove a property of modular arithmetic, namely: $[(a\bmod n)\times (b\bmod n)]\bmod n = ab\bmod n.$ I have the basis and hypothesis steps down, but I am having trouble with the hypothesis step:

Proof Let $P(n)$ be the predicate $P(n): [(a \bmod n) \times (b \bmod n)] \bmod n = a b \bmod n.$

Basis step: $$\begin{align*} \ [(a \bmod 1) \times (b \bmod 1)] \bmod 1 &= (a b) \bmod 1\\ \ [( 0 )\times ( 0 )] \bmod 1 &= (a b) \bmod 1 &&\text{(any \number is }0\text{ modulo }1\text{)}\\ 0 \bmod 1 &= (a b) \bmod 1\\ 0 &= 0 &&\text{(true for }n=1\text{)} \end{align*}$$

Hypothesis step

(Assume that $P(n)$ is true for some $n=k$): $[(a \bmod k) \times (b \bmod k)] \bmod k = (a b) \bmod k$

Induction Step

(Prove that $P(n)$ is true for some $n = k + 1$) $\begin{align*} \ [(a \bmod (k+1)) \times (b \bmod (k+1))] \bmod (k+1) &= (a b) \bmod (k+1)\\ \ [(a \bmod k) + 1 \times (b \bmod k) + 1] \bmod (k+1) &= (a b) \bmod (k+1)\\ \end{align*}$

I get to here then I can't figure out how to cancel out the 1's on the left hand side.

Any help would be appreciated.

  • 0
    Address $\: n\leq 0 \:$ separately. $\:\:\:$ For $\: 0\lt n \:$, $\:$ express $a$ and $b$ as multiples of $n$ plus members of $\{0,1,2,3,...,n+(-1)\}$. $\:\:\:$ Multiply, expand, and notice that adding multiples of $n$ does not change the result. $\;\;\;\;$2012-02-01

2 Answers 2

2

Let $c = a\bmod n$, true iff $a = jn +c$ for some integer $j$. Similarly $d = b\bmod n$ iff $b = kn +d$ for some integer $k$.

So,

$ab\bmod n = [(jn+c) \times (kn+d)] \bmod n $

$= [(jkn+jd+kc)n + c \times d] \bmod n $

$ = c \times d \bmod n $

$= [(a\bmod n)\times (b\bmod n)]\bmod n$,

which is what you wanted to prove.

4

Note that by the Chinese Remainder Theorem, for any $k\gt 0$, and for any integers $a$ and $b$, there exists an integer $x$ such that $x\bmod k = a\bmod k$ and $x\bmod (k+1) = b\bmod (k+1)$. That is: the remainders of $x$ modulo $k$ and modulo $k+1$ are completely unrelated. So I do not see how you are going to be able to leverage "knowing" the result modulo $k$ into a proof of the result modulo $k+1$, unless you simply prove it directly modulo $k+1$.

So it is really simpler to show that the result holds modulo $n$ directly, for any $n\gt 0$.

Remember that $x\bmod n = r$ if and only if $0\leq r\lt n$ and $x-r$ is a multiple of $n$.

So first show that $ab - (a\bmod n)(b\bmod n)$ is a multiple of $n$. For example, if $a\bmod n = r$ and $b\bmod n = s$, then $a-r$ and $b-s$ are both multiples of $n$; then $(a-r)b$ is a multiple of $n$, and $r(b-s)$ is a multiple of $n$, so...

  • 0
    Thank you this was a good start for me.2012-02-02