• Se e são inteiros e onde , então

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

É uma relação de equivalência?
(a) O que é um sistema de congruência linear?
(b) O que diz o Teorema de Wilson?
© O que diz o Teorema de Fermat?
(d) O que diz o Teorema de Euler?
(e) O que diz o Teorema do Resto Chinês?.
(f) Qual a condição necessária e suficiente para que um número seja primo?
a) ( ) A relação de igualdade sobre é uma relação de equivalência.
b) ( ) A relação de igualdade sobre é uma relação de ordem.
c) ( ) A relação de paralelismo definida para retas de uma espaço euclidiano é uma relação de ordem.
d) ( ) A relação de divisibilidade é uma relação de equivalência.
e) ( ) A relação de divisibilidade é uma relação de ordem.
f)()A relação de congruência é uma relação de equivalência.
g) ( ) O conjunto é totalmente ordenado pela relação .
a)
b)
c)
d)