Question

(Aritmética: Sistema de numeração decimal – base 10 – resolução de equações diofantinas lineares)

Sejam x, y os menores inteiros positivos tais que

     $(10^9)x-53y=1$

Calcule os valores de x e y.

─────

Obs.: Não é necessário utilizar o algoritmo de Euclides, no entanto, você está livre para escolher o método que julgar mais adequado.​

Answer 1

Usando o algoritmo de Euclides:

$10^9 = 53 \cdot 18.867.924+ 28\\53 = 28 + 25\\28 = 25 + 3\\25 = 3 \cdot 8 + 1$

Logo:

$1 = 25 - 3 \cdot 8\\\\1 = 25 - (28 - 25) \cdot 8\\1 = 25 - (8 \cdot 28 - 8 \cdot 25)\\1 = 25 - 8 \cdot 28 + 8 \cdot 25\\1 = -8 \cdot 28 + 9 \cdot 25\\\\1 = -8 \cdot 28 + 9 (53 - 28)\\1 = -8 \cdot 28 + 9 \cdot 53 - 9 \cdot 28\\1 = -17 \cdot 28 + 9 \cdot 53\\\\1 = -17(10^9 - 53 \cdot 18.867.924) + 9 \cdot 53\\1 = - 17 \cdot 10^9 + 53 \cdot 320.754.708 + 9 \cdot 53\\1 = - 17 \cdot 10^9 + 53 \cdot 320.754.717$

Para deixar no formato da equação inicial:
$1 = 10^9 \cdot (-17) - 53 \cdot (-320.754.717)$

Como a questão deseja os menores inteiros positivos como solução, deve-se somar e subtrair o MMC destes termos à expressão acima, e como estes termos são primos entre si, o MMC é diretamente $10^9 \cdot 53$. Portanto:

$1 = 10^9 \cdot (-17) - 53 \cdot (-320.754.717) + (10^9 \cdot 53) - (10^9 \cdot 53)\\1 = 10^9 \cdot (-17) - 53 \cdot (-320.754.717) + (10^9 \cdot 53) - (-10^9 \cdot (-53))\\1 = 10^9 \cdot (-17 + 53) - 53 \cdot (-320.754.717 + 10^9)\\1 = 10^9 \cdot 36 - 53 \cdot 679.245.283$

$(x, y) = (36, 679.245.283)$