0

On $\mathbb{N}\times\mathbb{N}$ define the relation $R$, where $((a,b),(c,d)) \in R$ if and only if $\gcd(a,b)=\gcd(c,d)$. Show that $R$ is a equivalence relation.

Reflexivity :

For every $(a,b) \in \mathbb{N}\times\mathbb{N}$ we have $\gcd(a,b)=\gcd(b,a)$ and $\gcd(c,d)= \gcd(d,c)$

so $(a,b)R(a,b)$ and $R$ is reflexive

Symmetry :

Therefore $(c,d)R (d,c)$

Transitivity :

$\gcd(a,b)=x, \gcd(c,d)=y$ AND $\gcd(e,f)=z$. $\gcd(a,b)= \gcd(c,d)$ and $\gcd(c,d)= \gcd(e,f)$ therefore $\gcd(a,b)=\gcd(e,f)$.

I am confused with the transitivity. Is that right ?

Kevin Long
  • 5,159
Adel
  • 1
  • It looks like you're confused about a few things. A minor note is that for reflexivity, you don't have to reorder the pairs. I also don't see why you're checking both $(a,b)$ and $(c,d)$ for reflexivity. You only need to talk about one pair. Recall that symmetry means that if $(a,b)R(c,d)$, then $(c,d)R(a,b)$. Your argument for transitivity is confusingly written, but you seem to have the idea down (the point being that if $(a,b)R(c,d)$ then $x=y$ and if $(c,d)R(e,f)$ then $y=z$, so $x=y=z$. – Kevin Long Apr 18 '18 at 20:53
  • thank you kevin – Adel Apr 18 '18 at 21:38

0 Answers0