I am having trouble forming the proof for the following:
Let m>0. We can define operation * on the equivalence classes of m as follows:
[a]m*[b]m=[a*b]m (The m's are subscripts)
As an example, we are given the proof for the "+" operation:
[a]m+[b]m=[a+b]m
Proof: We have to show the fns we've claimed to define are well-defined. Suppose a1≡a2 (congruent mod m) and b1≡b2 (congruent mod m). We have to show a1+b1≡a2+b2 (congruent mod m).
By assumption m|a1−a2, and m|b1−b2. Therefore m|(a1−a2)+(b1−b2), which after reorganizing the right-hand side gives m|(a1+b1)−(a2+b2), i.e., a1+b1≡ma2+b2, as required.
I understand what "congruent mod m" means, but I'm unsure what an equivalence class and equivalence relation are. Based on the given example, what I thought so far was I need to find steps that will lead to m|(a1*b1)-(a2*b2).
Best Answer
What you're looking at here is the algebraic way of defining modular arithmetic.
You start with the integers, $\mathbb{Z}$. And then, you define an equivalence relation: a way of declaring numbers 'equivalent' or 'not equivalent'. An equivalence relation must satisfy a few properties: it has to be symmetric ($a\equiv b$ if and only if $b\equiv a$), it must be reflexive ($a\equiv a$ for all $a$), and it must be transitive ($a\equiv b$ and $b\equiv c$ implies $a\equiv c$). An equivalence relation breaks a set up into subsets of elements that are all mutually equivalent.
In this case, your equivalence relation is "differ by a multiple of $m$": $a\equiv b\pmod m$ means that $a-b=km$ for some $k\in\mathbb{Z}$. This breaks $\mathbb{Z}$ up into $m$ equivalence classes: $\{0,m,2m,\ldots\}$, $\{1,m+1,2m+1,\ldots\}$, and so on up through $\{m-1,m+m-1,2m+m-1,\ldots\}$.
We usually represent this equivalence classes by something like $[a]$, where $a$ is some specific member of the class.
Now, here's where it gets interesting. You can certainly try to define $[a]\cdot[b]=[a\cdot b]$. But, what would happen if you had chosen a different representative for the equivalence classes? After all, $[a+m]=[a]$ and $[b+2m]=[b]$. If we had chosen $a+m$ and $b+2m$ as our representatives, our 'rule' (we haven't yet proved it is a function) would give us $[(a+m)(b+2m)]$. To declare this a function, it has to be the case that (among other things) $[(a+m)(b+2m)]=[ab]$.
For instance, if $m=5$, is it necessarily true that the equivalence class containing $2\cdot3$ is the same as the equivalence class containing $7\cdot13$? In order for this operation to be well-defined, you must get the same equivalence class back no matter which representative you choose.
So, what you are asked to show is this: if $a_1\equiv a_2\pmod{m}$ and $b_1\equiv b_2\pmod{m}$, is it necessarily true that $a_1b_1\equiv a_2b_2\pmod{m}$?
This boils down, of course, to exactly what you said you need to show: that $a_1b_1-a_2b_2$ is divisible by $m$.
As a first step, note that $a_1\equiv a_2\pmod{m}$ means there is a number $k$ so that $a_2=a_1+km$. Similarly, there is $h$ so that $b_2=b_1+hm$. Try plugging those into $a_1b_1-a_2b_2$, and see if you can find a way to show it is divisible by $m$.