# Modular arithmetic and equivalence classes

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.

-
Do you know what a relation on a set is. I think that'd help me write an answer. BTW, Is this answer of mine that deals with the the equivalence classes modulo $3$ help you? – user21436 Mar 11 '12 at 23:11
Well, it's too late in here. I'll write an answer tommorrow if this is still on the Unanswered list. – user21436 Mar 11 '12 at 23:12
@KannappanSampath Sorry, but I do not know what a relation on a set is. – user26649 Mar 11 '12 at 23:13
Your definition appears to be from p.26 of Algorithms, by S. Dasgupta, C. H. Papadimitriou, and U. V. Vazirani. Is your knowledge of modular arithmetic based exclusively on the (too) short sketch there (section 1.2)? The more you reveal about your level of knowledge, the more likely you'll receive answers at your level. – Bill Dubuque Mar 11 '12 at 23:40

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.

-
Thank you, I understood it perfectly. – user26649 Mar 11 '12 at 23:26

Given $N$, we will make $N$ "boxes", labeled $0$, $1$, $2,\ldots,N-1$. We will divide all the integers among the boxes as follows: given an integer $a$, divide $a$ by $N$ with remainder; put $a$ in the box corresponding to its remainder.

So, for example, if $N=11$, then we have boxes labeled $0,1,\ldots,10$; in the box labeled $0$ we have all multiples of $11$; in the box labeled $1$ we have all numbers of the form $11k + 1$, with $k\in\mathbb{Z}$; and so on: \begin{align*} {}[0] &= \{\ldots, -22, -11, 0, 11, 22, 33,\ldots\} = \{0+11k\mid k\in\mathbb{Z}\};\\ {}[1] &= \{\ldots, -21, -10, 1, 12, 23, 34, \ldots\} = \{1+11k\mid k\in\mathbb{Z}\};\\ {}[2] &= \{\ldots, -20, -9, 2, 13, 24, 35,\ldots\} = \{2+11k\mid k\in\mathbb{Z}\};\\ &\vdots\\ {}[10] &= \{\ldots,-12, -1, 10, 21, 32, 43,\ldots\} = \{10+11k\mid k\in\mathbb{Z}\}. \end{align*}

Each of this boxes is an "equivalence class": we consider two integers to be "equivalent [modulo $N$]" if they are in the same box. Note that every integer is in some box, and no integer is in more than one box; the boxes partition the integers.

We can then define addition of boxes as follows: to add the box $[a]$ with the box $[b]$, take any number $x\in[a]$, any number $y\in[b]$, add them like you add integers normally, and then find the one and only one box $[c]$ such that $x+y\in[c]$. We define $[a]+[b]$ to be the box $[c]$.

This definition requires that you show that it is "well-defined": the definition of $[a]+[b]$ seems to depend on the numbers $x$ and $y$ that are chosen; we need to show that if you pick a different $x'\in[a]$ and a different $y'\in[b]$, then $x'+y'$ will be in the same box as $x+y$. This can be done directly, or as a consequence of structure that these boxes have and is derived from the general algebraic theory of "congruences".

In a sense, we are dealing with all integers now, because the boxes include all the integers. We can then define a relation on the integers by saying that "$a$ is congruent to $b$ modulo $N$" if and only if $a$ and $b$ are in the same box. We write this $a\equiv b\pmod{N}$. Then what I discussed above says that if $x\equiv x'\pmod{N}$ and $y\equiv y'\pmod{N}$, then $x+y\equiv x'+y'\pmod{N}$.

You can define modular arithmetic as regular arithmetic in terms of the boxes.

-
Am instructive example - one which the OP surely knows - is fraction arithmetic (rationals). Alas, I don't have the time now to elaborate, but perhaps someone else does. – Bill Dubuque Mar 11 '12 at 23:57

To understand equivalence classes, you need to understand equivalence relations.

Let $A$ be any old set. A relation is defined to be any subset $R\subset A\times A$; if $(a,b)\in R$ we would usually write $aRb$. This definition seems kind of silly, and it kind of is, so let's make more assumptions on $R$. We say $R$ is an equivalence relation if it satisfies three axioms:

1) for every $a\in A,\ aRa$ (reflexivity)

2) for every $a,b\in A$, if $aRb$ then $bRa$ (symmetry)

3) for every $a,b,c\in A$, if $aRb$ and $bRc$ then $aRc$ (transitivity)

You can verify that the relation on $\mathbb{Z}$ defined by "$a\equiv_m b$ iff $m|(a-b)$" is an equivalence relation for any $m$

The special thing about equivalence relations is that they partition your set into equivalence classes . If $a\in A$ and $R$ is an equivalence relation on $A$, define the equivalence class $[a]=\{b\in A\ |\ aRb \}$. For example, if $A=\mathbb{Z}$ and $R$ is the familiar relation $\equiv_m$, then the equivalence class of $1$ is simply all integers $a$ such that $a\equiv 1\pmod{m}$, i.e. $[a]=\{1+km\ |\ k\in\mathbb{Z} \}$

-

In very layman's terminology, you can think of an analogy of students in a class(room).

The three conditions for an Equivalence relation can be imagined as such:

Reflexive: Every student is in the same class as himself.

Symmetric: If student A is in the same class as student B, then student B is in the same class as student A.

Transitive: If student A is in the same class as student B, and student B is in the same class as student C, then student A is in the same class as student C.

In the context of modular arithmetic (e.g. modulo 6), one can see that the three conditions hold.

Then the integers in a certain class all have the the same reminder (modulo 6).

So for example, 1,7,13 are all in the same class, denoted by [1], as they all have remainder 1 when divided by 6.

Hope this analogy helps.

-