Prove that congruence mod 7 is an equivalence relation.

Question

I know that an equivalence relation (~), by definition, has to hold 3 properties.

1.) Reflexive

2.) Symmetric

3.) Transitive

Although actually using this proof technique is very confusing to me. I am looking for a detailed explanation and a possible resource such as a website or video that has discrete mathematics explanations. Looking at the 3 properties to an equivalence relation I understand what all of them mean but I don't quite understand how to show the same meaning within another proof.

All help is much appreciated!

Answer 1

I'm not sure if this answers everything, but hopefully this helps.

Equivalence relations are, in a sense, a generalization of equality. So we ask ourselves: what are the defining properties of equality. Well first, we notice that there always holds $x=x$ (reflexivity). Secondly, we have that if $x=y$ then $y=x$ (symmetry). Finally, if $x=y$ and $y=z$ then $x=z$ (transitivity).

Now, I will address your problem more specifically, I am assuming that you are defining "$\sim$" to be such that $x\sim y$ iff there exists a number $n\in\mathbb{Z}$ such that $x = y + 7n$.

Using this definition, it is clear that $x\sim x$. Indeed, picking $n=0$ we see that $x = x + 7\cdot 0$. This shows reflexivity.

For symmetry, suppose that $x \sim y$. Then there exists $n\in \mathbb{Z}$ such that $x = y+7n$. But then, we also have $y = x + 7\cdot (-n)$. Ergo, $y\sim x$.

Finally, suppose that $x\sim y$ and $y\sim z$. Then there exist $n_1, n_2\in\mathbb{Z}$ such that $x = y+7n_1$ and $y = z+7n_2$. It follows that $$ x = y+7n_1 = z+7n_2+7n_1 = z+7(n_1+n_2) $$ which means that $x\sim z$.

I hope this answers at least part of your question!

Answer 2

I would recommend: Return to the definition.

I'll take your example. First we prove the reflexiveness, that is, $a\sim a$. By the definition of the relation $\sim$, $a$ would give the same remainder as $a$ when divided by $7$. Since they are the same number, the remainders are the same.

Second, we prove the symmetric property, $a\sim b\Leftrightarrow b\sim a$. Suppose $a\sim b$, by the definition of $\sim$, $a$ would give the same remainder as $b$ when divided by $7$, that is, $a=7k_1+r$ and $b=7k_2+r$, where $k\in\mathbb Z, r\in\{0,1,2,3,4,5,6\}$. This means that $b$ would give the same remainder as $a$, namely, $r$.

Third, transitiveness, $a\sim b,b\sim c\Rightarrow a\sim c$. Suppose $a\sim b,b\sim c$, by the definition of $\sim$, if $a=7k_1+r_1, b=7k_2+r_2$ and $c=7k_3+r_3$, $a\sim b$ translates to $r_1=r_2$, and $b\sim c$ translates to $r_2=r_3$. Therefore $r_1=r_2=r_3$. So again by definition, this exactly means that $a\sim c$.

I don't know whether this helps. If you elaborate on your question, I may explain clearer.

Answer 3

According to the definition, two integers are related iff they have the same remainder in dividing by $7$

Reflexive: every number and itself have the same remainder in dividing by $7$

Symmetric: If x and y have the same remainder, then y and x have the same remainder.

Transitive: If x and y have the same remainder and y and z have the same remainder then x and z have the same remainder.

Thus it is an equivalence relation.