What is meant by residue system and residue class in modular arithmetic?

Question

From surfing the net I got to knew that residue class is something related to the set {0,1,....,n-1} for a number n. Similar thing is about residue system.

So, can you help me a little to clear the meaning and confusion?

Answer 1

If $n \geq 1$ is an integer, a complete residue system modulo n is a subset $S \subset \mathbb{Z}$ with the following property:

For every $a \in \mathbb{Z}$, there is a unique element $s \in S$ such that $a-s$ is divisible by $n$.

One can show that $S$ must have exactly $n$ elements. The set $\{0, 1, ... , n-1\}$ is an example of a residue system modulo $n$. For $n = 5$,

$\{0,1,2,3,4\}$

$\{-2,-1,0,1,2\}$

$\{0, 6, 32, -2, -11\}$

$\{100, 99,98,97,51\}$

are all complete residue systems.

Answer 2

Yeah... there's three equivalent ways to look at it.

1) Imagine you have a set $\mathbb Z_n = \{0, 1,........, n-1\}$ and you want to define an addition/subtraction and multiplication on them (forget division for now). So you define $a + b$ as $a+b$ if $a+ b < n$. But what if $a+b \ge n$? Well you just "go around again". You define $a + b$ as "$a + b$ plus or minus however many $n$s it takes to get the answer between $0$ (inclusive) and $n$ (exlusive)$".

You do the same thing for subtraction and multiplication.

(You could sort of do the same thing for division but ... well, I think you can see some confusion that would arise and indeed that opens an area of study. $a/c = b$ means $bc =a$ so if $n = 8$ then $2*6 = 12 = 4$ so $4/2 = 6$. But also $4/2 = 2$ but $6 \ne 2$. Meanwhile $a*b = 5;a\ne1;b\ne 1$ never has any solution so $5/a$ never exists. so you can see that it's a something to be studied. Basically as the integers are not closed under division and $\mathbb Z_n$ may or may not be either, with the additional constraint that $a/b$, if it does exist, might not be unique. But I digress.)

Anyway the notation is $a + b \equiv c \mod n$, which means $a + b =c$ under modulo arithmetic on the set $\mathbb Z_n$.

2) Or we can start by letting $a,b,c \in \mathbb Z$ and defining $a \equiv b \mod n$ means that $a - b = kn \iff a = b + kn$ for some integer $k$.

This results is the same thing as 1) except we can use numbers that are "out of range" in our notation.

3) or we can be technical and slightly abstract.

Let $[x] = \{x + kn| k \in \mathbb Z\} = \{..., x - 2n, x - n, x, x+ n, x + 2n....\}$. That is $[x]$ is a set. This set is the set of all the integers that are "equivalent" to $x$ under "modulo n".

Note: $[x] = [x + n]$ as those are the same classes.

We define $[x]+[y]$ as $[x + y]$ and $[x][y]$ as $[xy]$ and note that it is consistent and well defined and we use notation: $[x] + [y] \equiv [c] \mod n$. Except that brackets are tedious and don't actually mean any thing so we leave them off and just write $x$ and we understand it to "really" mean $\{x, x+n, x+2n....\}$.

In this case, $[x] = \{x +kn\}$ is called an "equivalence class" because it is the set/class of all integers that are equivalent to $x$.

We call $\{[0],[1],.....,[n-1]\}$ a "complete residue system modulo m" because it is a complete set of all the required equivalence classes.

Note: Representatives $[0].... [n-1]$ are only one possible representation.

We could write it as $\{[n], [1], [2-7n],[2+5n]....[n-2], [-1]\}$ and it was still be a complete residue system. Every class is equivalent to one of the values between $0$ and $n$.

=====

Number 2) is the most common way you are likely to see it. It's useful for number theory in that: $n|a$ or "$n$ divides $a$" or "$a$ is a multiple of $n$" or "$n$ is a factor of $a$" is just the same thing as $a \equiv 0 \mod n$.

Likewise saying "$a$ when divided by $n$ has remainder $b$" is the same thing as saying $a \equiv b \mod n$. (Actually that says "$a$ and $b$ have the same remainder when divided by $n$" but that's close enough).

In this case, we are thinking of $a$ and $b$ as being integers or maybe natural numbers and considering their divisibility by $n$.

1) and 3) are more likely to be appeared in abstract algebra when you study group, rings, and fields. In those cases we aren't really thinking of the terms as integers, but as a self contained set by their own right upon which we can do a specialized type of arithmetic.

1) is sort of a breezy little exercise while, 3) is a formal theoretical construction.

But the point is, they are all equivalent and express the same ideas and results.