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

Passo 1

O enunciado dá os dois números 31 e 14 e pede três coisas:
  • Calcular o máximo divisor comum (mdc) de 31 e 14.
  • Encontrar a identidade de Bézout, isto é, inteiros x e y tais que 31x+14y=\gcd(31,14).
  • Verificar o mdc encontrado usando fatorações (teorema fundamental da aritmética).
Informações dadas:
  • Os dois inteiros são 31 e 14.
  • Não há outras restrições.

Passo 2

Explicando o método das divisões sucessivas (divisão euclidiana): para dois inteiros positivos a>b existe um quociente q e resto r tais que
a=bq+r,\qquad 0\le r<b.
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 31 e 14.
Primeira divisão:
31=14\cdot2+3,
pois 14\cdot2=28 e 31-28=3.
Segunda divisão (dividindo 14 por 3):
14=3\cdot4+2,
pois 3\cdot4=12 e 14-12=2.
Terceira divisão (dividindo 3 por 2):
3=2\cdot1+1,
pois 2\cdot1=2 e 3-2=1.
Quarta divisão (dividindo 2 por 1):
2=1\cdot2+0.
Parou-se quando o resto ficou 0. O último resto não-nulo é 1. Portanto
\gcd(31,14)=1.

Passo 3

Agora vamos obter a identidade de Bézout, ou seja, escrever 1 como combinação inteira de 31 e 14. 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):
\begin{aligned} 3 &= 31 - 14\cdot2,\\[4pt] 2 &= 14 - 3\cdot4,\\[4pt] 1 &= 3 - 2\cdot1. \end{aligned}
Substituímos a expressão de 2 na expressão de 1. Usando 2=14-3\cdot4:
\begin{aligned} 1 &= 3 - 1\cdot2\\\ &= 3 - 1\cdot(14 - 3\cdot4)\\\ &= 3 - 14 + 3\cdot4\\\ &= 3\cdot5 - 14. \end{aligned}
Agora substituímos a expressão de 3 (que é 3=31-14\cdot2) nessa última linha:
\begin{aligned} 1 &= (31 - 14\cdot2)\cdot5 - 14\\\ &= 31\cdot5 - 14\cdot10 - 14\\\ &= 31\cdot5 - 14\cdot11. \end{aligned}
Logo encontramos inteiros x e y tais que
31\cdot5 + 14\cdot(-11) = 1.
Portanto uma identidade de Bézout é dada por x=5 e y=-11.
Cheque rápido: 31\cdot5=155 e 14\cdot11=154, e 155-154=1, está certo.]

Passo 4

Observação sobre todas as soluções: como \gcd(31,14)=1, as soluções inteiras da equação 31x+14y=1 são todas da forma
x=5+14t,\qquad y=-11-31t,
para qualquer t\in\mathbb{Z}. (Isto apenas para informação; a identidade particular pedida foi x=5,y=-11.)

Passo 5

Verificação através do Teorema Fundamental da Aritmética (fatoração em primos):
  • 31 é primo, então sua fatoração é 31=31.
  • 14 tem fatoração 14=2\cdot7.
Comparando fatores primos, não há nenhum primo em comum entre 31 e 14. Pelo teorema fundamental da aritmética, o \gcd é o produto dos primos comuns com o menor expoente — aqui não há primos em comum, então o produto é 1. Assim a verificação por fatoração confirma que
\gcd(31,14)=1,
o que bate com o resultado obtido pelas divisões sucessivas.

Resposta

\gcd(31,14)=1
Identidade de Bézout: 31\cdot5 + 14\cdot(-11)=1
Verificação por fatoração: 31 é primo e 14=2\cdot7; não há fatores primos comuns, logo \gcd(31,14)=1.

Exercícios relacionados