# What is the motivation behind defining congruence / residue classes?

I mean instead of partitioning $$\mathbb Z$$ to $$n$$ different sets named residue classes and defining arithmetic operations on them, we can just define

$$\mathbb Z_n = \lbrace 0, 1, 2, ..., n-1 \rbrace$$

As a ring (a field if $$n$$ is prime) closed under binary relations modular addition and multiplication defined as follow,

$$X, Y \in \mathbb Z_n$$ $$(X + Y) = Qn + R$$ $$X +_n Y = R$$ ~ $$(X \cdot Y) = Q'n + R'$$ $$X \cdot_n Y = R'$$

Then other operations like division (if $$\mathbb Z_n$$ is a field), exponentiation etc. can be defined over all other elements. Why is this simply not sufficient and we need to make sure that any element of the $$\mathbb Z_n$$ have to represent all other elements of $$\mathbb Z$$ which yields the same remainder as itself when divided by $$n$$?

In other words why we need residue classes? What makes them more useful than the simple definition i denote above.

• Besides just being a special case of quotient structures in abstract algebra, don't you think that it's natural to say that $k + n\mathbb{Z}$ represents the numbers leaving $k$ as a remainder with respect to division by $n$? (And of course, what you're doing, is equivalent.) – Qi Zhu Jun 19 '19 at 17:25
• Working with the representatives is in general much easier than doing the calculations over the integers and at the end determining the residue. Why should we dispense with this advantage ? – Peter Jun 19 '19 at 17:32
• It's a bit less obvious how to prove things like associativity of multiplication with the definition in terms of canonical representatives, than using the definition in terms of equivalence classes. – Daniel Schepler Jun 19 '19 at 18:03
• Incidentally, personally I prefer to write $\mathbb{Z} / n \mathbb{Z}$ instead of $\mathbb{Z}_n$, due to the possibility of confusing the latter with the notation $\mathbb{Z}_p$ for the $p$-adic integers. – Daniel Schepler Jun 19 '19 at 18:04
• @DanielSchepler Nowadays (due to wide use in cryptography, coding theory etc), the notation $\,\Bbb Z_p\,$ is probably far more commonly used for the quotient than the adic ring. Notation does evolve. – Bill Dubuque Jun 19 '19 at 20:06

In quotient rings of Euclidean domains such as $$\,\Bbb Z\,$$ and polynomial rings $$\,F[x]\,$$ we can choose a least element in each class as a canonical rep ("normal form"), then transport the ring operations to these normal elements - just as you do above in the well-known case $$\,\Bbb Z_n = \Bbb Z/n =$$ integers $$\!\bmod n.$$

However, this is not possible in general quotient rings - where equality may not even be decidable. In this more rarified setting we have only the congruence classes (or cosets) themselves - since there is generally no effective way to choose a canonical rep from each class.

Further, congruence classes often provide greater flexibilty versus being forced to work only with canonical reps, e.g. when computing $$\,9^n\!\pmod{\!10}$$ we can instead choose the more convenient rep $$\, -1\equiv 9,\,$$ yielding the simplification $$\,9^n\equiv (-1)^n.\,$$ For another example, imagine how cumbersome it would be if we could only work with fractions that are reduced to normal form (lowest terms).

• An extreme example of this is the quotient $\mathbb{R} / \mathbb{Q}$, which is where two real numbers are considered to be "congruent" if their difference is a rational number. In that case, there is no explicit way to write a set of canonical representatives and to construct such a set of canonical representatives requires the axiom of choice. – Daniel Schepler Jun 19 '19 at 18:00
• Very nice explanations for the question. These examples are a lot clearer than my try of finding a suitable real life situation. – ThorWittich Jun 19 '19 at 18:17

It it a very natural thing to do. Consider this real life example:

You are in the supermarket buying food. For example you want to have fried rice with lots of vegetables and obviously you also want the dish to look good by having vegetables of different colours. This is your deepest wish right now. Pretend that you are standing in front of the fruits/vegetables in the supermarket.

Let $$X = \lbrace \text{Tomato},\text{Red Pepper},\text{Cucumber},\text{Banana},\text{Lemon} \rbrace$$. Since you are interested in the colours of the objects, it is natural to look at the set of the corresponding colours $$C = \lbrace \text{Red},\text{Green},\text{Yellow} \rbrace$$. So how do we obtain this set?

Define a relation on $$X$$ by $$x \sim y$$ iff $$x$$ and $$y$$ have the same colour. This is clearly an equivalence relation. Thus we get that $$X/\sim$$ is given by $$\lbrace [\text{Red Pepper}],[\text{Cucumber}],[\text{Lemon}] \rbrace$$, which we can identify with the set $$C$$. What we basically did was to get a new perspective on the elements of the set $$X$$ and using a different perspective is somthing we use in life all the time.

So why not look at the set $$C$$ directly? Well... it is not always possible to have canonical reps and in many situations it is a lot better to have the flexibility that choosing new reps give you. Here you would prefer not only to choose the colour but also some rep that fits the dish.

Maybe this helps you.

• You misread the question - see my comment on Kumar's answer. – Bill Dubuque Jun 19 '19 at 17:55
• Well... I tried to answer the question in the last part and the rest was more or less presenting the situation a bit. I agree that this answer might be misleading though. Since it is a real life example one could have obviously also started by only looking at suitable fruits/vegetables for the dish which is why this example most definately is not perfect. – ThorWittich Jun 19 '19 at 17:59
• Thanks for the answer. I completely understand equivalence relations. By the way what i understand to this point is we need residue classes because properties carried out by a specific element of a class (like $2$ and $12$ from $[2]_{10}$) possibly not be true for all of the class. – İbrahim İpek Jun 19 '19 at 18:09
• Also what do you mean with the notation $X / ∼$? I am unfamiliar with this – İbrahim İpek Jun 19 '19 at 18:13
• The first point really is maybe that it is not clear which rep ist the canonical or best one. In my example there might be two vegetables of the same colour that fit the dish. – ThorWittich Jun 19 '19 at 18:13

Sometimes some problems are hard to tackle for the whole $$\mathbb{Z}$$. So, taking the residue classes helps to simplify our problem and we have a smaller set to start the problem. Moreover, In abstract algebra, there are Zero divisors which needs to be eliminated from the discussion as they make a "non-useful class". So, Quotient removes these kinds of classes from our actual discussion.

Moreover, you can refer to any standard number theory and abstract algebra book. They provide extensive motivation for these definitions.

• The question is not about why quotient rings are useful. Rather it asks why construct quotient rings using congruence classes rather than using canonical elements chosen from each class – Bill Dubuque Jun 19 '19 at 17:54
• @BillDubuque Thank You, But I gave an answer with the knowledge I had about the topic. and also, I tried to answer the question in the first line. Maybe you can -1 my answer. – Kumar Jun 19 '19 at 18:01

First point is that, residue classes supplies us with the flexibility of choosing the most convenient element of class for the moment. In other words, sometimes we need different perspectives. As in the example of @Bill Dubuque:

$$9^n \equiv (-1)^n \space(modulo \space 10)$$

Further, any element of a class is "same" with the other from one perspective, that they leave the same remainder when divided by the modulo. They may not be equal, as differently posed congruent triangles aren't equal, but they are still the different representations of "same" no matter what. If we wear the glasses of "equality",

$$5 \ne 15.$$

So they aren't the same, in the perspective that they aren't quantities of the same amount. But if we change them with the glasses of "congruence modulo 10",

$$5 \equiv 15$$

So they are the the same, in the perspective that they leave the same remainders when divided by ten.

Fundamentally, if we notate residue class of $$[X]_M$$ indeed we represent the all quantities of the same form. And this is more convenient for deduction of generalized results about classes modulo $$M$$ and relationships between them.

As an example, when you multiply two integers leaving the remainder $$7$$ when divided by $$12$$, the result will be congruent to $$1$$ in the same modulo.