Very simple question, but what is the proof that x.y mod m == ((x mod m).y) mod m?

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.

Solution 1:

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.

Solution 2:

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 y_b and y_r are.

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