Is $R$ an equivalence relation on $\mathbb Z^+$: $\;x\,R\,y \;\text{ if and only if}\;\gcd(x,y)\neq 1.$

905 Views Asked by At

Let $\,R\,$ be a relation $R: \{(x, y) \mid \gcd(x, y) \neq 1\}$ defined on the set of positive integers. So $$\;x\,R\,y \;\;\text{ if and only if}\;\;\gcd(x,y)\neq 1.$$

I need to figure out if is this relation reflexive? Symmetric? Transitive?

2

There are 2 best solutions below

3
On BEST ANSWER

Reflexivity fails:
There's exactly one case for which reflexivity fails:
We need for all $x \in \mathbb Z^+$ that $\gcd(x, x) \neq 1$. It is true that for all $x \in \mathbb Z^+$, ${\bf x \neq 1,}$ that $\gcd(x, x) = x \neq 1$. But for ${\bf x = 1}$, we have that $\gcd(x, x) = \gcd(1, 1) = 1$. Because of that one counterexample, the relation itself is not reflexive.

It is symmetric,
because for any two positive integers, $x,\, y,\;\;\gcd(x, y) = \gcd(y, x)$. So for any $x, y \in \mathbb Z^+$, if $\gcd(x, y) \neq 1,\;$ then it follows that $\gcd(x, y) = \gcd(y, x) \neq 1$

Transitivity fails.
Again, we need only one counterexample to show this. Say $x = 3$, $y = 6$, and $z = 4$.
Then $\gcd(x,y) = \gcd(3, 6) = 3 \neq 1,$ and $\gcd(y, z) = \gcd (6, 4) = 2 \neq 1$, but $\gcd(x, z) = \gcd(3, 4) = 1.$

0
On

its not reflexive because $$\gcd(x,x)=x $$ but its Symmetric :$$gcd(x,y)\neq1 \iff gcd(y,x)\neq1$$

its not Transitive because :$gcd(2,6)\neq1$$gcd(6,3)\neq1$ but$gcd(2,3)=1$