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

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.

• Thanks for you took time to answer my question Nitin! – user3704516 Oct 27 '16 at 15:05

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?

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