Se
mdc
, ache dois inteiros
e
de maneira que
Passo 1
O enunciado pede para encontrar dois inteiros
e
tais que
sendo
.
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.
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
, temos
Aplicando o algoritmo de Euclides em bloco:
Portanto
.
Passo 3
Usamos o algoritmo extendido para escrever
Fazendo a volta (back-substitution) obtemos
pois
Passo 4
Voltando à equação original
note que isso equivale a
Comparando com
, temos
e
. Logo