• Se a e b são inteiros e a = q b + r onde q, r in Z, então
m d c(a, b) = m d c(b, r)

Passo 1

Neste exercício, queremos mostrar que se e são inteiros e , onde e também são inteiros, então o máximo divisor comum (mdc) de e é igual ao mdc de e . Para resolver isso, vamos utilizar conceitos básicos de máximo divisor comum e o algoritmo de divisão.

Passo 2

Primeiro, vamos relembrar o que é o máximo divisor comum. O mdc de dois números é o maior número que divide os dois sem deixar resto. Por exemplo, o mdc de 12 e 18 é 6, pois 6 é o maior número que divide tanto 12 quanto 18 sem deixar resto.

Passo 3

Agora, analisamos a equação dada: . Essa é a forma do algoritmo de divisão, onde:
  • é o dividendo,
  • é o divisor,
  • é o quociente,
  • é o resto.
Aqui, é menor que e não negativo.

Passo 4

Queremos provar que . Para isso, vamos mostrar que qualquer divisor comum de e também é divisor comum de e , e vice-versa.

Passo 5

Primeiro, suponha que é um divisor comum de e . Isso significa que:
  • divide ( | )
  • divide ( | )
Como , podemos reescrever como:
Como divide tanto quanto , ele também divide :
[ d ) |
Portanto, é um divisor comum de e .

Passo 6

Agora, suponha que é um divisor comum de e . Isso significa que:
  • divide ( | )
  • divide ( | )
Usando novamente a equação , sabemos que divide porque é uma combinação linear de e , que ambos são divisíveis por :
[ d ) |
Portanto, é um divisor comum de e .

Passo 7

Como mostramos que os divisores comuns de e são os mesmos que os divisores comuns de e , isso significa que os conjuntos de divisores comuns são iguais. Portanto, os máximos desses conjuntos também são iguais.

Resposta

Assim, concluímos que:

Exercícios relacionados