I completely understand the concept of modulus arithmetic and grasp all the main ideas. The only thing I don’t understand is equivalence classes.
The formal definition is:
Another interpretation is that modular arithmetic deals with all the integers, but divide them into N equivalence classes, each of the form $\{i + kN \mid k \in\mathbb{Z}\}$ for some $i$ between $0$ and $N-1$.
Could someone explain this in layman’s terms with an example possibly? I have absolutely no idea what equivalence classes are.
Best Answer
The notion of an equivalence class always arises when dealing with something called an "equivalence relation." So to explain the former, we'll first discuss the latter.
An equivalence relation is (speaking broadly) a generalized notion of equality. For example, if we are conducting a survey, and we are only concerned with gender, we might say that two people are "equivalent" if they have the same gender. Similarly, in the case of modular arithmetic, we say that two numbers are equivalent if they have the same remainder when divided by some number $n$. So, if we are working mod $4$, we say that $1 \equiv 5$. That does not mean that $1=5$, just that they are equivalent for our purposes.
More formally, an equivalence relationship needs to be reflexive (everything should be equivalent to itself), symmetric (if $A$ is equivalent to $B$, $B$ is equivalent to $A$) and transitive (if $A$ is equivalent to $B$, and $B$ is equivalent to $C$, $A$ is equivalent to $C$). Thus, this generalized notion of equality behaves very similarly to the traditional "$=$".
When we construct an equivalence relationship, one can think of it as putting on a pair of coarse glasses, so that we can no longer distinguish between "equivalent" objects. Thus, mod $4$, it appears to us that $1,5,9,\cdots$ are all the same thing. This entire family of objects that are equivalent is called an equivalence class. When we are working mod $4$, there will be $4$ equivalence classes, one corresponding to all things with remainder $0$, another for all things with remainder $1$, etc. Moreover, when you add two things with remainder $2$, you get something with remainder $0$. Thus, we can say that when working mod $4$, there are only four objects: families of "equivalent" numbers, and we do arithmetic with these families.