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.

  • $\begingroup$ 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$? $\endgroup$ – Keshav Srinivasan Mar 28 '14 at 14:20
  • $\begingroup$ 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. $\endgroup$ – wmnorth Mar 28 '14 at 14:49
  • $\begingroup$ What is your definition of $\,\bar a \bar b\,?\ \ $ $\endgroup$ – Bill Dubuque Mar 28 '14 at 15:04
  • $\begingroup$ 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? $\endgroup$ – wmnorth Mar 28 '14 at 15:45
  • $\begingroup$ 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}$. $\endgroup$ – Keshav Srinivasan Mar 28 '14 at 17:04

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

  • $\begingroup$ Can anybody explain the negative vote? $\endgroup$ – 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.