Use o método das divisões sucessivas para calcular o Máximo Divisor Comum e a Identidade de Bezout para os pares abaixo. Ainda, verifique o mdc encontrado através do Teorema Fundamental da Aritmética, ou seja, através de fatorações.
e) 31 e 14
e) 31 e 14
Passo 1
O enunciado dá os dois números
e
e pede três coisas:
- Calcular o máximo divisor comum (mdc) de
e . - Encontrar a identidade de Bézout, isto é, inteiros
e tais que . - Verificar o mdc encontrado usando fatorações (teorema fundamental da aritmética).
Informações dadas:
- Os dois inteiros são
e . - Não há outras restrições.
Passo 2
Explicando o método das divisões sucessivas (divisão euclidiana): para dois inteiros positivos
existe um quociente
e resto
tais que
Aplicando repetidas divisões (cada vez dividindo o divisor anterior pelo resto) até obter resto zero, o último resto não-nulo é o mdc.
Vamos fazer as divisões com
e
.
Primeira divisão:
pois
e
.
Segunda divisão (dividindo
por
):
pois
e
.
Terceira divisão (dividindo
por
):
pois
e
.
Quarta divisão (dividindo
por
):
Parou-se quando o resto ficou
. O último resto não-nulo é
. Portanto
Passo 3
Agora vamos obter a identidade de Bézout, ou seja, escrever
como combinação inteira de
e
. O truque é reescrever cada resto obtido nas divisões como combinação linear dos dois números e fazer substituições (back-substitution).
Das divisões anteriores extraímos as relações (reorganizando cada uma para escrever o resto):
Substituímos a expressão de
na expressão de
. Usando
:
Agora substituímos a expressão de
(que é
) nessa última linha:
Logo encontramos inteiros
e
tais que
Portanto uma identidade de Bézout é dada por
e
.
Cheque rápido:
e
, e
, está certo.]
Passo 4
Observação sobre todas as soluções: como
, as soluções inteiras da equação
são todas da forma
para qualquer
. (Isto apenas para informação; a identidade particular pedida foi
.)
Passo 5
Verificação através do Teorema Fundamental da Aritmética (fatoração em primos):
-
é primo, então sua fatoração é . -
tem fatoração .
Comparando fatores primos, não há nenhum primo em comum entre
e
. Pelo teorema fundamental da aritmética, o
é o produto dos primos comuns com o menor expoente — aqui não há primos em comum, então o produto é
. Assim a verificação por fatoração confirma que
o que bate com o resultado obtido pelas divisões sucessivas.
Resposta
Identidade de Bézout:
Verificação por fatoração: