Define a relation on $\mathbb Z$ by $m\sim n$ if $\gcd(m,n)=m$. Show that this is NOT an equivalence relation 
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$
 A: 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.
A: 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!
A: 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:

*

*Does $a \sim a$? : Reflexive

*Does $a \sim b \implies b \sim a$? : Symmetric

*Does $\{ ~(a \sim b) \wedge (b \sim c) ~\} \implies (a \sim c)$? : Transitive

Use the Lemmas.

*

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


*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$.


*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.
