Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

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

2 Answers 2

up vote 2 down vote accepted

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.

share|improve this answer

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

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

Your Answer

 
discard

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.