# Is $x = y \mod 7$ for a set of integers an equivalence relation?

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?

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}$.
• I am still not able to get it. For example if A = { 1,2,7,14,15} then i am able to find the relation R= {(1,1),(2,2),(0,7),(0,0),(0,14),(1,15)} . Sep 25, 2013 at 11:01
• Yes, those are certainly in $R$. Now $(0,7) \in R$ means that $7 \mid (0-7)$ ($\mid$ denotes "divides); does $7 \mid (7-0)$? Does it divide $(14-14)$? $(15-15)$? $(15-1)$? Try to complete the list. Sep 25, 2013 at 11:06
• I still can't understand. Is the R given by me complete or incomplete? (0,7) is in R because 0 is the remainder when 7 is divided by 7. Similarly (0,14) is in R because 14/7 = 2 and remainder is 0. But I am not able to find any order pair such as (7,7) or (14,14) . Then how is it reflexive? Sep 25, 2013 at 11:14
• @user221458 I've edited to clarify the probably cause of your confusion. Sep 25, 2013 at 11:15
• ok. Now i can understand that x=y(mod 7) is not equal to x = (y%7). But I still cant understand the meaning of x=y(mod 7). Can u clarify giving an example? Sep 25, 2013 at 11:21

It would be an equivalence relation if x - y is always divisible by 7.
In this case taking x = 7 we'd get x - y = 7n for some integer n and hence $x = 7 \equiv$ 0 mod 7 and $y = x - 7n = 7 - 7n = 7(1-n) \equiv$ 0 mod 7.
Hence x $\equiv$ y.
In general taking x = a mod 7, since x - y is divisible by 7, x - y = 7n for some integer n.
Hence y = x - 7n $\equiv$ a mod 7 - 7n $\equiv$ a mod 7.

If it's not always the case that x - y is divisible by 7, it's not an equivalence relation.
In this case there exists an x and a y such that there's no integer n for which x - y = 7n.
Thus x = a mod 7 and there's no integer n such tha y = x - 7n $\equiv$ a mod 7 - 7n $\equiv$ a mod 7.
Hence x isn't eqivalent to y mod 7.

• is x = y (mod 7) and x ≡ y (mod 7) same or different? Sep 25, 2013 at 11:06
• @user221458 It's the same. Sep 25, 2013 at 11:06
• $\equiv$ means 'is equivalent to' which means it's an equivalence relation. Sep 25, 2013 at 11:24