# Proving properties of modular arithmetic by induction

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.

-
It is incorrect that $a\bmod (k+1) = a\bmod k + 1$. For example, take $a=4$, $k=7$. Then $a\bmod k+1 = 4$, but $a\bmod k + 1 = 5$. –  Arturo Magidin Feb 1 '12 at 21:24
Do you have to do this by induction? It can be done directly fairly easily, and I honestly do not see how to do it by induction on the modulus; it is not straightforward to see how to relate remainders modulo $k$ with remainders modulo $k+1$; they can be very different. In fact, for any pair of positive integers $r$ and $s$, $0\leq r,s\lt k$, you can find an integer $a$ such that $a\bmod k = r$ and $a\bmod (k+1) = s$. –  Arturo Magidin Feb 1 '12 at 21:26
@ArturoMagidin The assignment only said prove, but induction happens to be the only method of proving that I know. –  Hunter McMillen Feb 1 '12 at 21:29
If you really need to do it by induction, fix $a$, and do an induction on $b$ (assumed non-negative, you can pick up the negatives easily once you have the positives). –  André Nicolas Feb 1 '12 at 21:32
@Hunter: Surely you know how to prove things directly? For example, do you prove that if $a|b$ and $b|c$, then $a|c$ by inductin? Or using the definition of "divides"? Use the definition here. –  Arturo Magidin Feb 1 '12 at 21:32

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.

-

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...

-
Thank you this was a good start for me. –  Hunter McMillen Feb 2 '12 at 0:56