Question

(Aritmética: Algoritmo de Euclides – equações diofantinas lineares a duas variáveis)

Encontre os menores valores inteiros positivos para x e y que satisfazem a equação

     65x − 47y = 1.

Dica: Use o algoritmo de Euclides.​

Answer 1

$65x - 47y = 1$

Escrita dos números no formato xq + r:

$65 = 47+ 18\\47 = 18 \cdot 2 + 11\\18 = 11 + 7\\11 = 7 + 4\\7 = 4 + 3\\4 = 3 + 1$

Preparando o 3 para eliminação:

$1 = 4 - 3$

Preparando o 4 para eliminação:

$1 = 4 - (7 - 4)\\1 = 4 - 7 + 4\\1 = 2 \cdot 4 - 7$

Preparando o 7 para eliminação:

$1 = 2 \cdot (11 - 7) - 7\\1 = 2 \cdot 11 + 2 \cdot (-7) - 7\\1 = 2 \cdot 11 + 3 \cdot (-7)\\1 = 2 \cdot 11 - 3 \cdot 7$

Preparando o 11 para eliminação:

$1 = 2 \cdot 11 - 3 \cdot (18 - 11)\\1 = 2 \cdot 11 - 3 \cdot 18 - 3 \cdot (-11)\\1 = 2 \cdot 11 - 3 \cdot 18 + 3 \cdot 11\\1 = 5 \cdot 11 - 3 \cdot 18$

Preparando o 18 para eliminação:

$1 = 5 \cdot (-18 \cdot 2 + 47) - 3 \cdot 18\\1 = 5 \cdot (-18 \cdot 2) + 5 \cdot 47 - 3 \cdot 18\\1 = 5 \cdot (-18 \cdot 2) + 5 \cdot 47 - 3 \cdot 18\\1 = -10 \cdot 18 + 5 \cdot 47 - 3 \cdot 18\\1 = -13 \cdot 18 + 5 \cdot 47$

Simplificando após eliminar o 18:

$1 = -13 \cdot (65 - 47) + 5 \cdot 47\\1 = -13 \cdot 65 - 13 \cdot (-47) + 5 \cdot 47\\1 = -13 \cdot 65 + 13 \cdot 47 + 5 \cdot 47\\1 = -13 \cdot 65 + 18 \cdot 47\\1 = -13 \cdot 65 - 18 \cdot (-47)$

Na última linha deixei o 47 negativo para que fique no formato da equação inicial.

Como a atividade solicita uma solução positiva, adicionamos e subtraímos o MMC de 65 e 47 (que, como são primos entre si, é $65 \cdot 47$):

$1 = -13 \cdot 65 - 18 \cdot (-47) + 65 \cdot 47 - 65 \cdot 47\\1 = -13 \cdot 65 - 18 \cdot (-47) + 65 \cdot 47 + 65 \cdot (-47)\\1 = 65(-13 + 47) - 47(-18 + 65)\\1 = 65 \cdot 34 - 47 \cdot 47$

Portanto:

$(x, y) = (34, 47)$