Sejam a e b inteiros primos entre si. Prove que:
ou 3
Passo 1
O enunciado diz: “Sejam
e
inteiros tais que
. Provar que
é igual a
ou a
.
Conteúdo: propriedades do máximo divisor comum e algoritmo de Euclides para combinar combinações lineares de inteiros.
Conteúdo: propriedades do máximo divisor comum e algoritmo de Euclides para combinar combinações lineares de inteiros.
Passo 2
Denote
Como
divide ambas as expressões, ele também divide qualquer combinação linear. Em particular, considere
Fazendo a subtração, obtemos
Logo,
divide
e também divide
.
Passo 3
Como
, qualquer fator comum a
e a
é 1. Portanto
não pode ter nenhum primo divisor comum com
, de modo que todo primo divisor de
deve dividir
e também
.
Se
é um primo tal que
, então
Substituindo
em
, vem
Mas
não pode dividir
(pois senão dividiria
), então
deve dividir
. Concluímos que todo primo divisor de
é
. Logo
Passo 4
Como
é divisor de
, só há as possibilidades
ou
.
Para ver quando ocorre, basta exigir
. De fato, se
então
e
Para ver quando
ou seja, ambos são múltiplos de 3 e
é 3. Caso contrário,
cai para 1.