Define a relation on $\mathbb Z$ by $m\sim n$ if $\gcd(m,n)=m$. Show that this is NOT an equivalence relation

Question

Define a relation on $\mathbb Z$ by specifying that $m\sim n$ if $\gcd(m, n) = m$. Show that this relation is NOT an equivalence relation.

I have shown that it passes the reflexive property and symmetric property, so that means it has to fail the transitive property, but I don't know how to show that.

Reflexive: $\gcd(m,m) = m$

Example: $\gcd(2,2) = 2$

Symmetric: $\gcd(m,n) = m$ and $\gcd (n,m) = m$

Example: $\gcd(2,4) = 2$ and $\gcd (4,2) = 2$

Answer 1

We have $1\sim 2$ because $\gcd(1,2)=1$ but we do not have $2\sim 1$, since $\gcd(2,1)=1\neq 2$. Thus $\sim$ is not symmetric. Hence it is not an equivalence relation.

Answer 2

Examples are NOT proofs- especially when you choose very special examples where m= n!

One of the properties of an "equivalence relation" is that "if a~ b then b~ a". Here you are defining m~ n if and only if "GCD(m,n)= n".

Okay, if m= 6 and n= 2 then GCD(m,n)= GCD(6, 2)= 2= n so 6~ 2.

But if m= 2 and n= 6 then GCD(m, n)= GCD(2, 6)= 2 which is NOT n= 6!

Answer 3

Alternative approach:

Lemma 1: $a,b \in \Bbb{Z_{\neq 0}}, ~a ~| ~b \implies |a| \leq |b|$.

Proof:
$|a| > |b|$ makes it impossible for $a$ to be a divisor of $b$.

Lemma 2: gcd$(m,n) = m \iff m ~| ~n.$

For this Lemma, without loss of generality, assume that $m,n \in \Bbb{Z^+}$. For either $m,n$ not positive, the analysis would be very similar.

$\implies$:
Assume gcd$(m,n) = m$. This implies that the gcd, namely $m$, is a common divisor of both $m$ and $n$. In particular, this implies that $m ~| ~n.$

$\impliedby$:
Assume that $m ~| ~n$. Then, clearly, $m$ is a common divisor of both $m$ and $n$. Further, it must be the greatest common divisor, because for any integer $d$ such that $|d| > |m|$ it is impossible for $d$ to be a divisor of $m$, by Lemma 1. Therefore, for any integer $d > m$, such that $|d| > |m|$, $d$ can not be a common divisor of $(m,n)$.

---

Three questions need to be considered:

1. Does $a \sim a$? : Reflexive
2. Does $a \sim b \implies b \sim a$? : Symmetric
3. Does $\{ ~(a \sim b) \wedge (b \sim c) ~\} \implies (a \sim c)$? : Transitive

Use the Lemmas.

1. $\forall a \in \Bbb{Z} ~$ (including $a = 0$), $a ~| ~a \implies a \sim a.$

2. Given $a,b \in \Bbb{Z_{\neq 0}},$ suppose that $~a \sim b,~$ and $|a| \neq |b|$. Such an occurrence is clearly possible, because any integer $b$, not an element of $\{-1, 0, 1\}$ will have $1$ as a divisor. In this event, by Lemmas 1 and 2, you have that $|a| < |b|$. This implies (again using Lemmas 1 and 2) that it is not the case that $b \sim a$.

3. Given $a,b,c \in \Bbb{Z},$
   $[(a\sim b) \wedge (b\sim c)] \implies \{ ~a ~| ~b \wedge ~b ~| ~c ~\} \implies $
   $a ~| ~c \implies (a \sim c).$

Therefore $(\sim)$ is reflexive and transitive, but not symmetric.