[Math] Is $x = y \mod 7$ for a set of integers an equivalence relation

discrete mathematicsequivalence-relations

Equivalence relation is the relation which is reflexive, symmetric and transitive. I have read somewhere that modulo operator defines an equivalence relation. But for this relationship I cant find $(7,7)$. If $y=7$ then $x=0$ (because $7$ is completely divisible by itself). Then how can it be reflexive? and how can it be an equivalence relation?

Best Answer

What is meant by "modulo operator is an equivalence relation" is the following:

We define that $x$ is congruent to $y$ modulo $n$, denoted $x \equiv y \pmod n$, if $n$ is a divisor of $x - y$.

This definition states in a mathematically precise way that $x \equiv y \pmod n$ if $x$ and $y$ have the same remainder modulo $n$.

Can you now prove that this $\equiv \pmod n$ is an equivalence relation? It is a good exercise to familiarise yourself with the concept.


Edit: It just occurred to me that you may be subconsciously bracketing the expression $x \equiv y \pmod 7$ in an unintended way. What is meant is:

$$(x \equiv y) \pmod 7$$

as opposed to:

$$x = (y \mathrel\% 7)$$

where $\%$ is the remainder operation. The former will be an equivalence relation. The latter won't, for $(7,7) \notin R$. I hope that clears the air for you.

The first notation $x \equiv y \pmod 7$ can alternatively be read as:

$$(x \mathrel\% 7) = (y \mathrel\% 7)$$


Edit 2: A few worked examples to get familiar with the $\equiv$ notation.

  • $7 \equiv 14 \pmod 7$? By definition, this holds if $7 \mid (7 -14)$. Since $7-14 = -7$, we conclude $7 \equiv 14 \pmod 7$.
  • $23 \equiv 8 \pmod 6$? This holds if $6 \mid (23-8)$. Since $6 \nmid 15$, we conclude $23 \not\equiv 8 \pmod 6$ (that is: "it is not the case that $23 \equiv 8 \pmod 6$").
  • $4 \equiv 4 \pmod{11}$? This holds if $11 \mid (4-4)$. Since $11 \mid 0$, it follows that $4 \equiv 4 \pmod{11}$.