- 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?
(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
.
b) ( ) A relação de igualdade sobre
c) ( ) A relação de paralelismo definida para retas de uma espaço
d) ( ) A relação de divisibilidade
e) ( ) A relação de divisibilidade
f)()A relação de congruência
g) ( ) O conjunto
a)
b)
c)
d)
b)
c)
d)