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 apologise for this question, as it is no doubt very simple, but I've never been very confident with proofs. Our lecturer today (in a course related to maths but not mathematical itself) was playing with doing the modulus of powers, and used the above fact - $(x.y)\; mod\; m\; ==\; ((x\; mod\; m).y)\; mod\; m$ - to show a quick way to do it. She mentioned offhand that the proof was short and easy, and that we should try it. Well, I did. And I'm not really sure that what I've done is mathematically sound. So I'd very much appreciate it if anyone could give me some help with how to do this proof correctly - googling for it turned up many pages which just state it as simple fact. I would not call my proof short or easy, so I reckon I've just got completely the wrong end of the stick.

My proof:

When considering any number, denoted n, in regards to another number m, we can write it as $n_b$ + $n_r$, where the former is some multiple of m, and the latter is the remainder when you take n mod m.

If we expand the original formula, $(x.y)\; mod\; m$ like this, we get $((x_b + x_r)(y_b + y_r))\; mod\; m$. This then expands to $(x_b y_b + x_b y_r + x_r y_b + x_r y_r)\; mod\; m$. The first three terms in the brackets are all some multiple of m, and so when they are taken modulus m they are 0. The final term we do not know, so we are left with: $(x_r y_r)\; mod\; m$.

Now we can consider the left hand side. $((x\; mod\; m).y)\; mod\; m$ is equivalent to $((x_r).y)\; mod\; m$. Expanding y gives us: $((x_r)(y_b + y_r))\; mod\; m$. Multiplying out then gives $(x_r y_b + x_r y_r)\; mod\; m$. As before, the first term in the brackets are multiples of m and so are 0 when taken mod m, and the last one we do not know, so we are left with: $(x_r y_r)\; mod\; m$.

Since both the LHS and RHS boil down to the same thing, the equality holds.

share|improve this question
add comment

2 Answers 2

Below are proofs of the product rule proof expressed in both divisibility and congruence form, using the standard notation: $\rm\ \ a\ |\ b \ :=\ a\,$ divides $\rm\, b\:,\;$ and $\rm\ \; a\equiv b\ \ (mod\ m)\: \iff\: m\:|\:a-b$

$\begin{eqnarray} \rm {\bf Lemma}\ \ &\rm m\ \ |&\rm\ \, X-x\quad\ and &&\rm m\ |\: Y-y \ \Rightarrow\ m\:|\!\!&&\rm XY - \: xy\\ \\ \rm {\bf Proof}\ \ \ \ \ &\rm m\ \ |&\rm (X-\color{#C00}x)\:\color{#C00}Y\ \ \ + &&\rm\, \color{#C00}x\ (\color{#C00}Y-y)\ \ \ = &&\rm XY - \: xy \\ \\ \rm {\bf Lemma}\ \ & &\rm\ \, X\equiv x\quad\ \ and &&\rm\quad\ \ Y\equiv y \ \ \ \ \Rightarrow\ &&\rm XY\equiv xy\\ \\ \rm {\bf Proof}\ \ \ \ \ &0\equiv& \rm (X-\color{#C00}x)\:\color{#C00}Y\ \ \ + &&\rm\, \color{#C00}x\ (\color{#C00}Y-y)\ \ \ \equiv &&\rm XY - \: xy \\ \end{eqnarray}$

Note how the congruence notation eliminates cumbersome manipulation of relations (divisibility). Indeed, the relations are replaced by a generalized equality (congruence) which, being compatible with multiplication (as above) and addition (similar proof), enables us to exploit our well-honed intuition manipulating integer equations - which immediately generalizes to manipulating congruences (mod m). When you study abstract algebra you'll learn that this is a very special case of a quotient or residue ring. This product rule arises in many analogous contexts, e.g. see my post on the product rule for derivatives.

share|improve this answer
1  
Could the person who downvoted please explain? If something is not clear then please ask questions and I am happy to elaborate. –  Bill Dubuque Sep 24 '10 at 15:21
    
+1. It might be worth explicitly noting that $m|X-x\Leftrightarrow X\equiv x\;(\mod m)$. –  Isaac Sep 24 '10 at 15:27
    
@Isaac: Thanks for the tip, I've explicitly noted that. –  Bill Dubuque Sep 24 '10 at 16:06
add comment

I guess you already know how to prove that (s+t) mod m = ((s mod m)+(t mod m)) mod m. If not, you should first prove it, because you are using it in your proof. Other than this, your proof is correct except for a tiny point that you have not stated what yb and yr are.

I call your proof easy, but slightly verbose. Most importantly, you do not have to break y into yb and yr.

share|improve this answer
    
Thank you for your note about $y_b$ and $y_r$. I have edited the definition to be more general. I also am having trouble proving the addition bit - I can write it in words quite easily but struggle to do it mathematically (Adding s and t gives you a number that is $(s_b + s_r + t_b + t_r)$, which is a number that is $s_r + t_r$ bigger than a modulus of m. Since $s_r + t_r$ may be bigger than m, we need to take it mod m again. The right hand side boils down to the same thing, and so etc etc.) –  Andrew Sep 24 '10 at 12:21
    
@Andrew: Your argument about addition is basically correct, except that when you stated “$s_r+t_r$ bigger than a modulus of m,” you probably meant “$s_r+t_r$ plus some multiple of m.” It takes some practice to write an proof in a concise way, though. The biggest source of verbosity here is that you are trying to prove an equation and motivate it at the same time. You do not always have to motivate the formula to prove. (more) –  Tsuyoshi Ito Sep 24 '10 at 12:38
    
@Andrew: (cont’d) Namely, you do not have to explain why “we need to take it mod m again” in a proof; all you have to do is to prove that a given formula is correct. (Thinking about why we have to take mod m again is a good thing, but it is often better not to mix this consideration with a proof.) –  Tsuyoshi Ito Sep 24 '10 at 12:39
    
Sorry, yes, I meant to say that $s_r + t_r$ may be bigger than m (we know that individually they are smaller, but their sum may be bigger) and so they must be taken modular m to get the correct answer. I will try and work on the difference between proving and motivation. Thank you for your help. I am just glad I had the correct understanding of the proof in general. –  Andrew Sep 24 '10 at 12:41
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.