How to show that $(3k+2,5k+3)=1$ for all $k\in\mathbb{Z}$ I think I'm on the right track, but I can only figure out how to prove for a specific $k$ of my choosing... I don't know how to generalize it for all $k$:

Assume $(3k+2,5k+3)=1$. Therefore, there exists some $x,y\in\mathbb{Z}$ such that $(3k+2)x+(5k+3)y=1$.
\begin{align}
(3k+2)x+(5k+3)y&=3kx+2x+5ky+3y\\
&=3kx+5ky+2x+3y\\
&=k(3x+5y)+2x+3y=1
\end{align}

If I let $k=0$, then $2x+3y=1$, and a particular solution is $(x_0,y_0)=(2,-3)$. But this same $(x,y)$ is not valid for other values of $k$... There does appear to exist upon inspection a solution for any value of $k$, but I'm not sure how to prove it.
 A: $$
5 \cdot (3k+2) ~-~ 3 \cdot (5k+3) = 1 \qquad \forall k
$$
Edit
I'm adding my comment to the answer: in order to remove the $k$s from the linear combination, (multiples of) 5 and 3 as coefficients are the only way. Since they do work, it's done!
A: HINT:
$$5(3k+2)-3(5k+3)=1$$
can you continue?
A: Your approach is right and is invoking Bezout's Identity which says that gcd$(a,b)$ is the smallest positive integer $c$ such that $ax+by=c$ with $x,y \in \mathbb{Z}$.
Therefore if we can show that there is a pair $(x,y)$ such that
$$(3k+2)x+(5k+3)y=1$$
Then we know that gcd$(3k+2,5k+3)=1$.  A quick check shows that $x=5, y = -3$ will do the trick.
A: Another, slightly different, proof goes like this: $\gcd(5k+3,3k+2)$ must divide both the sum and difference of the two, i.e.
$$\gcd(5k+3,3k+2) \mid \gcd(8k+5,2k+1).$$
But $8k+5=4(2k+1)+1$, so the gcd must also divide $1$, proving $\gcd(5k+3,3k+2)=1$.
A: Using the Euclidean algorithm:
\begin{align*}
5k+3&=1\times (3k+2)+(2k+1)\\
3k+2&=1\times (2k+1)+(k+1)\\
2k+1&=1\times (k+1)+k\\
k+1&=1\times k+1\\
k&= 1\times k+0
\end{align*}
Therefore, the GCD of $3k+2$ and $5k+3$ is $1$. Additionally, there exists some $x$ and $y$ such that $(3k+2)x+(5k+3)y=1$. A particular solution is $(x,y)=(5,-3)$.
