Encontrar inteiros
e
tais que
Passo 1
Beleza, o problema pede para a gente encontrar inteiros
e
tais que
Isso é uma equação diofantina linear, que cai na matéria de Teoria dos Números. Para resolver, a ferramenta principal é o Algoritmo de Euclides Estendido, que serve para calcular o mdc de dois números e, de quebra, escrever esse mdc como combinação linear deles. Aqui a gente vai precisar:
- Calcular o
com o Algoritmo de Euclides. - Fazer a “volta” (back-substitution) para achar coeficientes
e .
Passo 2
Primeiro, vamos achar o
com o Algoritmo de Euclides “normal” e anotar restos:
Como o último resto não-nulo é 1, temos
. Ou seja, existe solução para
.
Passo 3
Agora, a parte do Euclides Estendido: a gente “volta” expressando 1 como combinação linear de 128 e 43.
Da segunda linha:
Da segunda linha:
Mas da primeira linha temos
Substituindo
na expressão de 1:
Ou seja, conseguimos
Resposta
Uma solução é