# Multiplication of residue classes modulo n

If $\bar{a}$ and $\bar{b}$ are residue classes modulo $n$, it is straightforward to see that $\bar{a} \bar{b} = \overline{ab}$. But given that those classes are sets, does the $=$ mean set equality?

To give a concrete example, let $n=7$. Then $\bar{4}^2=\overline{16}=\bar{2}$. Now, it is again easy to see that the sets $\bar{2}$ and $\overline{16}$ are equal (any element in one of them belongs to the other one and vice-versa), but my question is what about equality of $\bar{4}^2$ and $\overline{16}$? Any element in the former belongs to the latter, but as far as I understand it, the converse does not hold: $23 = 16 + 7 \times 1$ (so $23 \in \overline{16}$), but 23 is a prime so it can't be written as the product of two integers, thus $23 \not\in \bar{4}^2$. So the conclusion seems to be that $\bar{4}^2 \varsubsetneq \overline{16}$. So, is this also the meaning of the $=$ sign in the equality $\bar{a} \bar{b} = \overline{ab}$?

Note that for addition of residue classes, the sets $\bar{a}+\bar{b}$ and $\overline{a+b}$ are indeed equal: if $x \in \bar{a}+\bar{b}$ it follows from the definition that $x \in \overline{a+b}$; conversely if $x \in \overline{a+b}$ then $x = a + b + kn = a + b + (k' + k'')n = a + k'n + b + k''n \Rightarrow x \in \bar{a}+\bar{b}$. The adopted notation suggests that this is also that case for multiplication of residue classes, but as I argue above that does not seem to be the case.

• What makes you think that the fact that 23 is not the product of two integers implies that 23 is not an element of $\bar{4}^2$? – Keshav Srinivasan Mar 28 '14 at 14:20
• Well because the way I interpret a set defined like $\bar{4}^2$ is like being the set of all integers that can be written as a product of two numbers $x$ and $y$ where $x \in \bar{4}$ and $y \in \bar{4}$. I am still trying to make sense of user2425's alternative definition. – wmnorth Mar 28 '14 at 14:49
• What is your definition of $\,\bar a \bar b\,?\ \$ – Bill Dubuque Mar 28 '14 at 15:04
• I'm reading this book, which, in section 1.3, defines $\bar{a}$ and $\bar{b}$ the usual way ($x \in \bar{a} \text{ iff } x \equiv a \pmod{n}$), and resp. for $\bar{b}$. The only "definition" of $\bar{a}\bar{b}$ given is $\bar{a}\bar{b} = \overline{ab}$. But I thought of it more as property, that could be deduced from a definition of $\bar{a}\bar{b}$ like the one implied in my previous answer. Is this not correct? – wmnorth Mar 28 '14 at 15:45
• No, $\bar{a}\bar{b}$ is NOT the set of all integers that are equal to $xy$ where $x \in \bar{a}$ and $y \in \bar{b}$. Rather, it's the set of all integers that are congruent modulo $n$ to $xy$ where $x \in \bar{a}$ and $y \in \bar{b}$. – Keshav Srinivasan Mar 28 '14 at 17:04

## 2 Answers

Perhaps you are a bit confused about the meaning of $\bar 4^2$, $\bar a+\bar b$, etc. Here is the definition for addition, for example:

$\bar a+\bar b$ is the set of numbers which are congruent with $x+y$, where $x$ is any number congruent with $a$ and $y$ is any number congruent with $b$. The point is that no matter which $x$ and $y$ you pick: this will always yield the same result. Hence this definition has no ambiguity.

Taking your example: $23$ does belong to $\bar 4^2$ since is congruent with $4^2$ or $11^2$ or $(4+7k)^2$.

• Can anybody explain the negative vote? – ajotatxe Mar 28 '14 at 14:47

While it is true that $\ \ \bar a \oplus \bar b\, := \, \overline{a+b}\,=\, \{ i+j\ :\ i\in \bar a,\ j\in \bar b\}\,$ the analogy for products is false,
i.e. it is not true that $\,\bar a \otimes \bar b\,:=\, \overline{a \times b}\, =\, \{ i\times j\ :\ i\in \bar a,\ j\in \bar b\}\,$ as the example you gave shows.

Therefore, unlike coset addition, coset multiplication is not an elementwise set-product, since such a set-product need not yield a complete equivalence class.