4
$\begingroup$

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?

$\endgroup$
6
$\begingroup$

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.

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

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?

$\endgroup$
1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.