Show that
$\gcd(3k+2,5k+3)=1$ 
Let $k$ be an integer. Show that
  $$\gcd(3k+2,5k+3)=1$$

I know that I can use the Euclidean algorithm, but the $k$ is bugging me. Should I use induction or something?
 A: You can do it just like normal. 
$$ 5k+3 = 1(3k+2) + (2k+1)$$
$$ 3k+2 = 1(2k+1) + (k+1)$$
$$ 2k+1 = 1(k+1) + (k)$$
$$ k+1 = 1(k) + (1)$$
Since we see $1$, we're done.
A: Suppose, there is a $d \in \Bbb N$ such that $d|(3k+2)$  and $d|(5k+3)$
$\therefore d|\{5(3k+2)\}$ and $d|\{3(5k+3)\}$
$\implies d|(15k+10)$ and $d|(15k+9)$
$\implies d|\{(15k+10)-(15k+9)\}\implies d|1$. 
Now, do you get it?
A: Another way is to use Cramer's rule (or elimination) to solve for $\,k\,$ and $\,1\,$ below
$$ \begin{eqnarray} \ 5\,k\, +\, 3\cdot 1 &=& i\\[.3em]  3\ k\, + \ 2\cdot 1 &\ =\ & j\end{eqnarray}
\quad\Rightarrow\quad \begin{array}\  k \  = \ \ \ \,  2
\,i\, -\, 3\ j \\[.3em]  \color{#c00}{\bf 1}\ =\,  {-3}\ \color{#0a0}i\, +\, 5 \ \color{#0a0}j \end{array} $$
Therefore, by the lower equation in the RHS system: $\ n\mid \color{#c00}{\bf 1}\ $ if $\,\ n\mid \color{#0a0}{i,\,j} = 5k\!+\!3,3k\!+\!2$ 

Remark $\ $ In the same way we can prove more generally
Theorem  $\ $ If $\rm\,(x,y)\overset{A}\mapsto (X,Y)\,$ is linear then $\: \rm\gcd(x,y)\mid \gcd(X,Y)\mid \color{#90f}\Delta \gcd(x,y),\ \ \ \color{#90f}{\Delta := {\rm det}\, A}$
e.g. $ $ in OP we have $\,\color{#90f}{\Delta =\bf  1}\,$ so the above yields  $\ \gcd(5k+2,3k+2)\mid\color{#90f}{\bf 1}\cdot\gcd(k,1) = 1$
using the map $\ (k,1)\mapsto (5k+3,3k+2)\ $ i.e.
$$ (k,\,1)\,\mapsto\, (k,\,1)\,\underbrace{\begin{bmatrix}5 & 3\\ 3 &2\end{bmatrix}}_{\large \det A\, =\, \color{#90f}{\bf 1}} =\, (5k+2,\,3k+2)$$
