[Math] Is this relation an equivalence relation? Check the solution please.

discrete mathematicsrelations

Define a relation R on the set {$2, 3, 4, … $}, as follows.
$(x, y)$ ∈ R if and only if $x$ and $y$ have a common factor greater than $1$.

Is this relation reflexive? Is it symmetric? Is it transitive?

Is this an equivalence relation? Justify your arguments.

My Attempt:

1) It is reflexive, since the set begins at $2$ and $(x,x)$ will always be a common factor of itself, which is greater than $1$.

2)It is symmetric, because order doesn't matter. (I do not know how I should show this formally though)

3) Not transitive as $(2,6)$ and $(6,9)$ have GCF's $> 1$ but $(2,9)$ does not.

Therefore this is not an equivalence relation.

Best Answer

You are correct. For symmetric, $(x, y) \in R \Rightarrow \gcd(x,y) > 1 \Rightarrow (y, x) \in R$

Related Question