Modulo Equivalence Classes

Question

Let $d$ be a fixed positive integer. Define a binary relation $\equiv_d$ on $\mathbb Z$ by $m\equiv_d n$ whenever $m-n$ is divisible by $d$. Determine all the equivalence classes under $\equiv_d$. How many are there? Verify that the equivalence classes form a partition of $\mathbb Z$.

I am trying to figure this out and I am thinking there would be an infinite number of equivalence classes. Whatever $d$ is I can come up with an infinite combinations of $m-n$ is divisible by $d$. As for the Classes being a Partition of $\mathbb Z$, couldn't $m,n$ be non integers? Thanks in advance for any help.

Answer 1

Equivalence Classes

Essential to understanding modulo classes is understand equivalence classes.

For a relation $\sim$ on a set $A$, an equivalence class $[a]$ is defined as all elements $b\in A$ such that $a \sim b$. Using notation, $[a]:=\{b\in A: a\sim b\}$.

There are a few important properties of equivalence classes:

• If $a\sim b$, then $[a]=[b]$.
• If $a\not\sim b$, then $[a]\cap [b] = \emptyset$

You should attempt to prove these two yourself.

Modulo Classes

The relation you defined, $\equiv_d$ on $\mathbb{Z}$, is an equivalence class. To give you some insight into how these classes work, let's examine the simple case of $d=4$. Let's try and find $[0]$ and $[1]$.

Plugging in $n=0$, we get that $m\equiv_4 0$ if $m-0$ is divisible by $4$. Next, plugging in $n=1$, we get that $m\equiv_4 1$ if $m - 1$ is divisible by $4$. So, we have that

• $[0] = \{4k:k\in\mathbb{Z}\}$.
• $[1] = \{4k + 1: k\in\mathbb{Z}\}$.

You should try the following:

1. Find the rest of the equivalence classes. Do these form a partition of $\mathbb{Z}$? Why or why not?

2. Prove that $\equiv_d$ is indeed an equivalence relation on $\mathbb{Z}$.

3. Find the answers to your questions for the general case, after getting comfortable with various values of $d$.