I'm really struggling to understand the literal arithmetic being applied to find a complete residue system of modulo $n$. Below is the definition my textbook provides along with an example.
Let $k$ and $n$ be natural numbers. A set $\{a_1,a_2,…,a_k\}$ is called a canonical complete residue system modulo $n$ if every integer is congruent modulo $n$ to exactly one element of the set
I'm struggling to understand how to interpret this definition. Two integers, $a$ and $b$, are "congruent modulo $n$" if they have the same remainder when divided by $n$. So the set $\{a_1,a_2,…,a_k\}$ would be all integers that share a quotient with $b$ divided by $n$?
After I understand the definition, this is a simple example provided by my textbook
Find three residue systems modulo $4$: the canonical complete residue system, one containing negative numbers, and one containing no two consecutive numbers
My first point of confusion is "modulo $4$". $a{\space}mod{\space}n$ is the remainder of Euclidean division of $a$ by $n$. So what is meant by simply "modulo $4$"? What literal arithmetic do I perform to find a complete residue system using "modulo $4$"?
Best Answer
Prelim: The definition is confusing because it is not assuming $k = n$. You will be able to prove $k = n$ later but in mathematics we don't include anything in a definition that we can prove later.
The definition of a complete residue system is a collection of integers $\{a_j\}$ so that for any integer, that integer will be congruent (have the same remainder) with exactly one of those integers.
In Other words, and probably a much more straightforward definiton, For every possible remainder, there will be be exactly one integer with that remainder.
For instance if $n = 7$, the easiest and most obvious complete residue system would be simply $\{0,1,2,3,4,5,6\}$. Every integer will be have remainder $0,1,2,3,4,5,6$ and those are precisely the numbers in there.
Another complete system could be $\{63, 8, 15, -4, 32, 75, 146\}$. If an integer $b$ has remainder $0$ it is congruent to $63$. $63$ represents all the integers with remainder $0$. ANd if $b$ has remainder $8$ then $b$ is congruent to $8$. $8$ represents all the integers with remainder $1$.... And so on.
Every remainder is represented exactly once.
And that is what a complete residue system means. A residue is a representation of one class of remainders (all the integers with remainder $4$ for example are represented by $32\equiv 4 \pmod 7$, for example). And a complete residue system means every residue is represented.
And as there $n$ possible remainders there will be $n$ elements in the system so if the system is $\{a_1, ...., a_k\}$ then $k = n$. (If it were me, I wouldn't even bring up the idea this could be in doubt. It just confuses things the first time you see the definition.)
.....
Okay. To do a completer residue system $\pmod 4$ you need to find a $\{a_1, a_2, ..... , a_k\}$ were for every integer $-6,-5,-4,-3,-2,-1,0,1,2,3,4,5,6,....$ is congruent to exact one of them.
So we need and $a_1\equiv -6\pmod 4$. Well $-6\equiv 2 \pmod 4$ so let's let $a_1 = 2$. And we need something $\equiv -5 \pmod 4$. We $-5\equiv 3 \pmod 4$ and $15 \equiv 3 \pmod 4$ and $15 \equiv -3 \pmod 4$ so lets use $a_2 = 15$.
And we need something $\equiv - 4 \pmod 4$. Well $-4 \equiv 0 \equiv 28\pmod 4$ so let's use $a_3 = 28$. And we need something $\equiv -3\pmod 4$ but $-3\equiv 1 \equiv 48321 \pmod 4$. SO lets let $a_4 = 48321$.
And we need something $\equiv -2\pmod 4$. But $-2 \equiv 2 = a_1$ so we already have it. In fact it looks like we have one of each.
So $\{2, 15,28, 48321\}$ seems to be complete.
If $b$ is an integer we have either $b = 4k$ or $4k + 1$ or $4k + 2$ or $4k + 3$.
If $b = 4k$ then $b \equiv 28\pmod 4$. ANd if $4k + 1$ then $b\equiv 48321$. And if $b = 4k + 2$ then $b \equiv 2\pmod 4$ and if $b= 4k + 3$ then $b\equiv 15\pmod 4$.
So ....
the definition is:
Well, that is true so $\{2, 15,28, 48321\}$ is a complete residue system.
That's all.