Mostrar que $\gcd(3k+2,5k+3)=1$

Question

Deje $k$ ser un número entero. Mostrar que $$\gcd(3k+2,5k+3)=1$$

Sé que se puede utilizar el algoritmo de Euclides, pero el $k$ es que me molesta. Debo usar la inducción o algo?

Answer 1

Usted puede hacer esto como 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)$$

Como nos vemos a $1$, hemos terminado.

Answer 2

Supongamos que hay un $d \in \Bbb N$ tal que $d|(3k+2)$ $d|(5k+3)$

$\therefore d|\{5(3k+2)\}$ $d|\{3(5k+3)\}$

$\implies d|(15k+10)$ $d|(15k+9)$

$\implies d|\{(15k+10)-(15k+9)\}\implies d|1$.

Ahora, ¿se puede pasar?

Answer 3

Otra manera es usar la regla de Cramer (o eliminación) a resolver por $\,k\,$ $\,1\,$ por debajo de

$$ \begin{eqnarray} \ 5\,k\, +\, 3\cdot 1 &=& i\\ \\ 3\ k\, +\, \ 2\cdot 1 &\ =\ & j\end{eqnarray} \quad\Rightarrow\quad \begin{array}\ k \ = \ \ \ \, 2 \,i\, -\, 3\ j \\\\ \color{#c00}{\bf 1}\ =\, {-3}\ \color{#0a0}i\, +\, 5 \ \color{#0a0}j \end{array} $$

Por lo tanto, por la baja de la ecuación en el lado derecho del sistema: $\ n\mid \color{#c00}{\bf 1}\ $ si $\,\ n\mid \color{#0a0}{i,\,j}$

---

Comentario $\ $ En el mismo camino que nos puede resultar más generalmente

Teorema $\ $ Si $\rm\,(x,y)\overset{A}\mapsto (X,Y)\,$ es lineal, a continuación, $\: \rm\gcd(x,y)\mid \gcd(X,Y)\mid \color{#90f}\Delta \gcd(x,y),\ \ \ \color{#90f}{\Delta := {\rm det}\, A}$

por ejemplo, $ $ en OP hemos $\,\color{#90f}{\Delta =\bf 1}\,$ por lo que la anterior rendimientos $\ \gcd(5k+2,3k+2)\mid\color{#90f}{\bf 1}\cdot\gcd(k,1) = 1$