Se d= mdc (-68,42), ache dois inteiros x0 e y0 de maneira que
(-68) x0+42 y0=d

Passo 1

O enunciado pede para encontrar dois inteiros x0 e y0 tais que
(-68),x0 + 42,y0 = d,
sendo d = gcd(-68,42).
Conteúdo: algoritmo de Euclides para calcular o máximo divisor comum e o algoritmo extendido para escrever esse divisor como combinação linear dos números dados.

Passo 2

Como gcd(a,b)=gcd(|a|,|b|), temos
d = gcd(-68,42) = gcd(68,42)
Aplicando o algoritmo de Euclides em bloco:
68 &= 42 cdot 1 + 26, 42 &= 26 cdot 1 + 16, 26 &= 16 cdot 1 + 10, 16 &= 10 cdot 1 + 6, 10 &= 6 cdot 1 + 4, 6 &= 4 cdot 1 + 2, 4 &= 2 cdot 2 + 0
Portanto d = 2.

Passo 3

Usamos o algoritmo extendido para escrever
68,s + 42,t = 2
Fazendo a volta (back-substitution) obtemos
s = -8, t = 13,
pois
68cdot(-8) + 42cdot13 = -544 + 546 = 2

Passo 4

Voltando à equação original
(-68),x0 + 42,y0 = 2,
note que isso equivale a
68cdot(-x0) + 42,y0 = 2
Comparando com 68,s + 42,t = 2, temos -x0=s e y0=t. Logo
x0 = -s = 8, y0 = t = 13

Resposta

x0 = 8, y0 = 13

Exercícios de Livros Relacionados