What are the sets in the partition of the integers arising from congruence modulo 3

i.e. Give a description of each of the congruence classes modulo 3.

I think I understand this but I wanted to verify. In my notes I've read "If $$R$$ is the congruence modulo $$m$$ relation on the set $$\mathbb Z$$ of integers then $$\mathbb Z/m = \{[0], [1],...[m-1]\}$$".

So for $$3$$ we have the classes $$[0],[1],$$ and $$[2]$$. I then described each as follows:

$$[0] = \{0 + 3k\} = \{0,3,6,9,..\}$$

$$[1] = \{1+3k\} = \{1,4,7,10,...\}$$

$$[2] = \{2+3k\} = \{2,5,8,11,...\}$$

Am I correct?

• Where do the negative integers fall? Jan 30, 2020 at 19:17
• No, you are not correct. Where are the negative numbers? $\Bbb Z$ denotes the set of all integers. Then $\Bbb Z/m$ still consists of equivalence classes containing positive and negative numbers. Jan 30, 2020 at 19:17
• That is fine for writing the sets of non-negative integers. If you were to write $\{1,4,7,10,\dots\}$ however, most people would assume that you are implying that these numbers are all positive. To emphasize the fact that you include negative numbers as well, it is better to write it as a two-sided list like $\{\dots,-5,-2,1,4,7,\dots\}$ or to write this in set-builder notation as $\{1+3k~:~k\in\Bbb Z\}$ and leave it at that Jan 30, 2020 at 19:17
• So does the rule Z/m = [0], [1], [m-1] work the other direction such that the equivalence classes are [-2],[-1],[0],[1],[2]? Jan 30, 2020 at 19:19
• You could have written them as $[0],[1],[2]$ as most people do. Or you could have written them as $[10002],[4],[-43]$ if you were so inclined, or you could have written them in many other different ways. The point that we're trying to get across is that when you wrote that $[0]$ was "The set $\{0,3,6,9,\dots\}$" that will be interpreted by most people incorrectly if not wrong in your own mind as well and should have instead been written $\{\dots,-9,-6,-3,0,3,6,9,\dots\}$ so that it is clear that the sequence continues in both directions rather than only in the one direction. Jan 30, 2020 at 19:29

The comments suggest that the main terminology you need is congruence modulo $$n$$. So we have $$a\equiv b\bmod 3 \Longleftrightarrow 3\mid a-b$$ in the ring $$\Bbb Z$$. This has nothing to do with negative or positive numbers. It concerns all integers, i.e, $$-1\equiv 2\equiv 5 \bmod 3$$ for example. In the quotient ring $$R=\Bbb Z/3$$ these become equalities: $$-7=-4=-1=2=5=8$$ in $$R$$, and so on. So in the quotient all these numbers are just treated as one element, namely as $$[2]$$ in your terminology.
Application: The equation $$x^2+y^2=7919$$ has no integer solution.
Proof: Assume it has an integer solution. Then it also has one in the quotient $$R=\Bbb Z/4$$. Here we obtain $$x^2+y^2=3$$, which clearly has no solution there. Contradiction.