Para cada par de números naturais a e b dados abaixo, ache ( a, b ) e determine números inteiros x e y tais que a x+b y=(a, b).
7325 e 8485

Passo 1

O enunciado dá os dois números naturais \,7325 e \,8485 e pede duas coisas: encontrar o máximo divisor comum \,(7325,8485) e determinar inteiros x e y tais que
7325\cdot x + 8485\cdot y = (7325,8485).
As informações relevantes são apenas os dois números fornecidos; a tarefa é aplicar o algoritmo que calcula o MDC e, em seguida, expressá-lo como combinação linear dos dois números.

Passo 2

Vou usar o Algoritmo de Euclides para calcular o máximo divisor comum (MDC). Lembrete prático do algoritmo: dada uma divisão inteira
A = B\cdot q + r\quad\text{com}\quad 0\le r < B,
temos a propriedade importante
(A,B) = (B,r).
Ou seja, o MDC de A e B é o mesmo que o MDC de B e do resto r. Repetimos esse processo até obter resto zero; o último resto não nulo é o MDC.

Passo 3

Aplicando o Algoritmo de Euclides aos números \,8485 e \,7325:
Primeira divisão:
8485 = 1\cdot 7325 + 1160.
Segunda divisão:
7325 = 6\cdot 1160 + 365.
Terceira divisão:
1160 = 3\cdot 365 + 65.
Quarta divisão:
365 = 5\cdot 65 + 0.
Como o resto ficou 0 na última divisão, o último resto não nulo é \,65. Portanto o MDC é \,65.

Passo 4

Resumo do que encontramos (para fixar): a cadeia de restos foi
1160,\;365,\;65,\;0,
logo
(7325,8485)=65.

Passo 5

Agora precisamos escrever 65 como combinação linear de 7325 e 8485, ou seja, achar inteiros x e y tais que
7325\cdot x + 8485\cdot y = 65.
Para isso usamos o algoritmo extendido de Euclides: voltamos substituindo os restos pelas expressões obtidas nas divisões (back-substitution), reescrevendo cada resto como combinação linear dos dois números originais.

Passo 6

Fazemos a substituição passo a passo a partir da terceira divisão, onde achamos 65:
Da terceira divisão temos
65 = 1160 - 3\cdot 365.
Da segunda divisão temos
365 = 7325 - 6\cdot 1160.
Substituindo essa expressão de 365 em 65:
65 = 1160 - 3\cdot(7325 - 6\cdot 1160).
Desenvolvendo:
65 = 1160 - 3\cdot 7325 + 18\cdot 1160 = 19\cdot 1160 - 3\cdot 7325.
Agora usamos a primeira divisão, que deu
1160 = 8485 - 1\cdot 7325.
Substituindo essa expressão de 1160 na expressão anterior:
65 = 19\cdot(8485 - 7325) - 3\cdot 7325.
Desenvolvendo:
65 = 19\cdot 8485 - 19\cdot 7325 - 3\cdot 7325 = 19\cdot 8485 - 22\cdot 7325.

Passo 7

Interpretando o resultado na forma pedida, temos
7325\cdot(-22) + 8485\cdot 19 = 65.
Portanto uma solução inteira para x e y é x=-22 e y=19. Podemos checar mentalmente: 7325\cdot 22 = 161150 e 8485\cdot 19 = 161215; a diferença é 161215-161150=65, conferindo o cálculo.

Resposta

(7325,8485)=65
x=-22,\;y=19

Exercícios relacionados