Problema del Algoritmo Euclidiano $475x+2018y=1$

Question

Pensé que lo estaba haciendo bien hasta que revisé mi respuesta en línea y obtuve una diferente. Trabajé nuevamente en el problema y obtuve mi respuesta original por segunda vez, así que esto me está preocupando ya que los otros similares que he hecho estaban bien. ¡Por favor avísenme si estoy haciendo algo mal, gracias!

Encuentra $x, y$ contenidos en enteros tal que $475x+2018y=1$, luego encuentra un valor para $475\equiv -1$ (mod $2018$).

Dado que está en la forma $ax+by=1$, sé que el $\gcd(a,b)=1$. Aun así, hice el algoritmo de la división ya que eso me ayuda con la sustitución hacia atrás. Esto es lo que obtuve.

Algoritmo de División:

• $2018=(4\times 475)+118$

• $475=(4\times 118)+3$

• $18=(39\times 3)+1$

Sustitución hacia atrás:

• $1=118-(39\times 3)$

• $1=118-39(475-(4\times 118))$

• $1=(157\times 118)-(39\times 475)$

• $1=157\times (2018-(4\times 475))-(39\times 475)$

• $1=(157\times 2018)-(667\times 475)$

Entonces $x=667$ y $y=157$

La segunda pregunta la respondí a partir de la primera parte que es $475x$ congruente con $1$ (mod $2018$) así que simplemente sería $667$ de la primera parte. Cualquier ayuda es apreciada, ¡gracias!

Answer 1

Lo que te equivocaste es que la tarea te pide encontrar enteros para $475x+2018y=1$, NO $-475x+2018y=1.

Para este tipo de problema, mi respuesta a este problema sería similar a la respuesta que publiqué aquí para el caso $73a+89b=3$, el método principal es seguir estableciendo nuevas variables, así:

• Pon $a=\frac{3-89b}{73}=\frac{3-16b}{73}-b$, entonces $\frac{3-16b}{73} \in \mathbb{Z}$ porque $a,b\in \mathbb{Z}$.

• Pon $c=\frac{3-16b}{73}$, entonces $3-16b=73c$ o $b=\frac{3-73c}{16}=\frac{3-9c}{16}-4c$, entonces $\frac{3-9c}{16} \in \mathbb{Z}$ porque $b,c\in \mathbb{Z}$.

• Pon $d=\frac{3-9c}{16}$, entonces $3-9c=16d$ o $c=\frac{3-16d}{9}=\frac{3-7d}{9}-d$, entonces $\frac{3-7d}{9} \in \mathbb{Z}$ porque $c,d\in \mathbb{Z}$.

• Pon $e=\frac{3-7d}{9}$, entonces $3-7d=9e$ o $d=\frac{3-9e}{7}=\frac{3-2e}{7}-e$, entonces $\frac{3-2e}{7} \in \mathbb{Z}$ porque $d,e\in \mathbb{Z}$.

• Pon $f=\frac{3-2e}{7}$, entonces $3-2e=7f$ o $e=\frac{3-7f}{2}=\frac{1-f}{2}+1-3f$, entonces $\frac{1-f}{2} \in \mathbb{Z}$ porque $e,f\in \mathbb{Z}$.

$e$ sería un entero si y solo si $f=2k+1$ o $f$ impar

$\Rightarrow e=-7k-2$

$\Rightarrow d=9k+3$

$\Rightarrow c=-16k-5$

$\Rightarrow {\begin{cases}a=-89k-28\\b=73k+23\end{cases}}$

Para números mucho más grandes como $475x+2018y=1$, simplemente harías el paso anterior más veces, pero tu método de prueba y error puede ser válido si no has leído mal el problema, la respuesta final debería ser

${\begin{cases}x=-2018k-667\\y=475k+157\end{cases}}$

Answer 2

Tenga en cuenta que a partir de su derivación es

• $x=-667$
• $y= 157$

y

$$-667\equiv1351\equiv475^{-1} \pmod {2018}$$

Answer 3

$$ \frac{ 2018 }{ 475 } = 4 + \frac{ 118 }{ 475 } $$ $$ \frac{ 475 }{ 118 } = 4 + \frac{ 3 }{ 118 } $$ $$ \frac{ 118 }{ 3 } = 39 + \frac{ 1 }{ 3 } $$ $$ \frac{ 3 }{ 1 } = 3 + \frac{ 0 }{ 1 } $$ Tabla de fracción continua simple:
$$ \begin{array}{cccccccccc} & & 4 & & 4 & & 39 & & 3 & \\ \frac{ 0 }{ 1 } & \frac{ 1 }{ 0 } & & \frac{ 4 }{ 1 } & & \frac{ 17 }{ 4 } & & \frac{ 667 }{ 157 } & & \frac{ 2018 }{ 475 } \end{array} $$ $$ $$ $$ 2018 \cdot 157 - 475 \cdot 667 = 1 $$

............