Cómo resolver la ecuación de diophantine $8x + 13y = 1571$

Question

Estoy teniendo problemas para resolver la siguiente ecuación diophantine:

$8x + 13y = 1571$

Para todos los otros ejemplos que he trabajado a través de la que he sido capaz de utilizar el algoritmo de euclides y la solución muestra en algún lugar. Que no funciona en este caso, y el $\text{gcd}(8, 13) = 1$, así que yo sé que existe una solución. Entonces, ¿cómo se podría solucionar un problema como este?

Answer 1

Empezar por la solución de la ecuación de $8s+13t=1$. Usted puede hacer esto mediante la inspección, para $s=-8$, $t=5$ obviamente, funciona. O bien puede utilizar la maquinaria del Algoritmo de Euclides.

Así $x_0=(-8)(1571)$, $y_0=(5)(1571)$ es una solución de la ecuación que nos fue dado.

Todas las soluciones de la ecuación están dadas por $x=x_0+13t$, $y=y_0-8t$, donde $t$ rangos de los números enteros.

Nota: no Tenemos necesidad de haber comenzado a partir de una solución de $8s+13t=1$. La única razón por la que lo hicimos de esa manera era conectar la solución con el material que ya se ha cubierto.

Si encontramos alguna solución particular $(x_1,y_1)$ de nuestra ecuación, entonces todas las soluciones están dadas por $x=x_1+13t$, $y=y_1-8t$.

Si usted ha hecho Álgebra Lineal, o Ecuaciones Diferenciales, que se han visto este tipo de cosas antes. Tenemos el general de la solución de nuestra ecuación mediante la toma de una determinada solución, y la adición de la general de la solución de la ecuación homogénea $8x+13y=0$.

Answer 2

La expansión continua de la fracción obtenemos $$\frac{13}8=1+\frac58=1+\frac1{\frac85}=1+\frac1{1+\frac35}$$ $$=1+\frac1{1+\frac1{\frac53}}=1+\frac1{1+\frac1{1+\frac23}}$$ $$=1+\frac1{1+\frac1{1+\frac1{\frac32}}}=1+\frac1{1+\frac1{1+\frac1{1+\frac12}}}$$

Así, la última convergente es $$1+\frac1{1+\frac1{1+\frac1{1}}}=\frac53$$

El uso de los convergentes de la propiedad de la continuación de la fracción, $$ 8\cdot 5-13\cdot3=1$$

Por eso, $$8x+13y=1571(8\cdot 5-13\cdot3)$$

$$8(x-5\cdot1571)=-13(3\cdot1571+y)$$

$$\frac{13(3\cdot1571+y)}8=5\cdot1571-x$ $ , que es un entero

Por eso, $$8\mid 13(3\cdot1571+y)\implies 8\mid (3\cdot1571+y)\text{ as }(8,13)=1$$

$3\cdot1571+y\equiv0\pmod 8\iff 3\cdot3+y\equiv0\pmod 8$ $1571\equiv3\pmod8$

$\implies y\equiv-9\pmod8\equiv7\implies y=8a+7$ para algunos entero $a$

Answer 3

Utilizando el algoritmo de Euclides encontrará $x',y'\in\mathbb Z$ tal que $8x'+13y'=1$. Multiplicando por 1571 llegamos $8(x'\cdot1571)+13(y'\cdot1571)=1571$.
Ahora establezca $x=x'\cdot1571$$y=y'\cdot1571$. Cómo acerca de todas las soluciones?

Answer 4

$\rm 8x\!+\!13y = k = 3\!+\!8j\:\Rightarrow\:mod\ 8\!:\ 13y\equiv 3\:\Rightarrow\:y \equiv \dfrac{3}{13} \equiv \dfrac{3}{{-}3}\equiv -1\:\Rightarrow\: \color{#c00}{y = -1\!+\!8n}$

$$\rm\Rightarrow\ \ \ x\, =\, \dfrac{k\!-\!13\,\color{#c00}y}8\,=\, \dfrac{ 8j\!+\!3 \!-\!13\,(\color{#c00}{-1\!+\!8n})}8\,=\, j\!+\!2\!-\!13n$$

Su caso especial es $\rm\ k = 1571 = 3 + 8\cdot 196,\:$ $\rm\ j = 196,\ $ $\rm\ (x,y) = (198,-1) + n(-13,8)$

Answer 5

Sugerencia: $~8x+(8+5)y=8\cdot196+3\iff8~(x+y-196)+5y=3=8-5.~$ Puede tomar desde aquí ? ;-)