5
$\begingroup$

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?

$\endgroup$

2 Answers 2

4
$\begingroup$

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}$.
$\endgroup$
7
  • $\begingroup$ 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)} . $\endgroup$
    – user221458
    Sep 25, 2013 at 11:01
  • $\begingroup$ 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. $\endgroup$
    – Lord_Farin
    Sep 25, 2013 at 11:06
  • $\begingroup$ 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? $\endgroup$
    – user221458
    Sep 25, 2013 at 11:14
  • $\begingroup$ @user221458 I've edited to clarify the probably cause of your confusion. $\endgroup$
    – Lord_Farin
    Sep 25, 2013 at 11:15
  • $\begingroup$ 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? $\endgroup$
    – user221458
    Sep 25, 2013 at 11:21
1
$\begingroup$

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.

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

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .