Sejam
inteiros não nulos que são relativamente primos entre si. Mostre que
para todo
.
Passo 1
O que o enunciado dá e o que pede (peguei tudo do enunciado):
- Dados:
e são inteiros não nulos e relativamente primos entre si. Ou seja,
- Pedido: mostrar que para todo inteiro
com vale
Passo 2
Lembrete dos conceitos que vou usar (explicadinho, passo a passo):
- Definição:
é o maior inteiro positivo que divide simultaneamente e . Dizer que e são relativamente primos é a mesma coisa que dizer . - Observação útil (forma prática de trabalhar com
): se existe um primo que divide ambos e , então divide qualquer divisor comum de e . Em particular, se quisermos provar que , basta mostrar que não existe primo que divida simultaneamente e .
Passo 3
Uma ferramenta que vou usar (leve e explicada): lema de Euclides sobre primos
- Lema (Euclides): se
é primo e divide o produto , então divide ou divide . - Por que isso é verdade (prova curta): suponha
primo e . Se não divide , então . Pelo Teorema de Bézout (resultado padrão obtido pelo algoritmo de Euclides) existem inteiros tais que
Multiplicando por
obtemos
Como
divide
e
divide
(hipótese),
divide o lado esquerdo inteiro, logo
divide
. Assim, se
não divide
então divide
; portanto
ou
. Isso é exatamente o lema.
Passo 4
Estratégia do prova principal (por contradição via primos comuns):
- Vou provar que não existe primo
que divida simultaneamente e . Se conseguir isso, então . - Suponha, para contradizer, que exista um primo
tal que e .
Passo 5
Usar o lema para deduzir que
divide
e
:
- Do fato
note que . Aplicando o lema de Euclides a obtemos que ou . - Se
já está ótimo. Se não, então . Repetindo o argumento (aplicando o lema novamente a ) obtemos que ou . Continuando esse processo, depois de no máximo aplicações encontramos que . - Portanto, a partir de
segue necessariamente . - O mesmo raciocínio dá que, a partir de
, segue .
Passo 6
Concluir a contradição e terminar a prova:
- Do passo anterior, se
divide e então divide e simultaneamente. - Mas isso contradiz a hipótese de que
e são relativamente primos, isto é, . Portanto a suposição de existência de tal primo é falsa. - Conclui-se que não existe primo que divida simultaneamente
e . Logo o único divisor comum possível é , e assim
para todo
.