Show that GCD is = relative prime

Question

Let $k$ be an integer. Show that $3k + 2$ and $5k + 3$ are relatively prime.

So, I know that I need to prove that GCD is $1$ and I know that one way to do this is $am+bn=1$. However, I don't really see how to do that here.

Answer 1

Eliminate $k$

$$3(5k+3)-5(3k+2)=?$$

Answer 2

You can use the Eucledean algorithm.

$$ 5k+3=1\cdot(3k+2)+2k+1 $$ $$ 3k+1=1\cdot(2k+1)+k $$ $$ 2k+1=2\cdot k+1 $$ $$ k=k\cdot 1+0 $$ and the last non-zero remainder is the greatest common divisor, which is $1$ and hence they are relative primes.