# 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.

-

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.

-

$$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!

-

HINT:

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

can you continue?

-
I'm not sure I see where the $5$ and $-3$ came from. –  agent154 Oct 4 '13 at 13:47
OK, I see how the math works out, but I don't see how you came up with those numbers. What procedure did you use? –  agent154 Oct 4 '13 at 13:48
we want x and y such that the k's get eliminated –  ILUA Oct 4 '13 at 13:49
In general, Euclid's algorithm can work, for finding the greatest common divisor. –  Berci Oct 4 '13 at 13:49
@Berci I had considered that, but I couldn't figure out how to use it with the variables... –  agent154 Oct 4 '13 at 13:50

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$.

-

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)$.

-