Show that $\gcd(3n,3n+ 2) = 1$ when $n$ is odd

Question

I would like to know why $\gcd(3n,3n+ 2) = 1$ when $n$ is odd.

I tried to use the Euclidean Algorithm, but I got confused: $$ 3n+2 = 3n + 2$$ $$3n = \ ? $$ Thanks!

Answer 1

Do you know that $a$ and $b$ are relative prime iff there exist integers $x$ and $y$ s.t. $ax+by=1$? See burton page $23$ , if you don't.

By that if $n$ is odd, let $n=2k+1$, then $3n=6k+3$ and $3n+2=6k+5$. Now notice that $(3k+2)(6k+3)+(-(3k+1))(6k+5)=1$. $\hspace{8cm}$Q.E.D

Answer 2

Hint: We have (by one step of the Euclidean Algorithm) $$\gcd(3n+2,3n)=\gcd(3n,2).$$

More informally, any common divisor of $3n+2$ and $3n$ is also a divisor of $2$.