Is $a \sim b$ such that $\gcd(a,b) > 1$ an equivalence relation?

1.1k Views Asked by At

Is $a \sim b$ such that $\gcd(a,b) > 1$ an equivalence relation?

I know that it's reflexive, since $\gcd(a,a) > 1$. It's also symmetric since $\gcd(a,b) > 1$ iff $\gcd(b,a) > 1$.

However, I'm having trouble figuring out whether it's transitive. I reckon so, since if $a$ divides $b$ and $b$ divides $c$, then $a$ must divide $c$. However when I entered in my university's online quiz that it is an equivalence relation, it marked the answer as wrong. Am I incorrect?

2

There are 2 best solutions below

3
On

Hint Check that the transitivity fails with $$a=5,\; b=15,\; c=3$$

0
On

Hint $\ $ For any $\,a,b\,$ there exists $\,c\,$ such that $\,a \sim c,\,\ b\sim c\,$ (e.g. $\,c = ab).\,$ Thus if the relation is transitive then, being symmetric, it is trivial: $\,a\sim c,\,\ c\sim b\,\Rightarrow\, a\sim b,\,$ for all $\,a,b.$

Remark $\ $ In other words, directed sets/preorders are trivial if symmetric.