Mostre que se
e
são primos entre si, então também são primos entre si os seguintes pares de inteiros:
e
Passo 1
O enunciado dá que os inteiros
e
são primos entre si, ou seja,
A tarefa é mostrar que os inteiros
e
também são primos entre si, isto é, provar que
Informações relevantes:
e
são inteiros quaisquer e não têm nenhum fator primo em comum.
Passo 2
Vou provar a afirmação por contradição examinando possíveis divisores primos comuns a
e
. A ideia é: se um primo
divide
e
, então
divide
e
; isso contradiz
. Para justificar a passagem "se
então
" vou usar o lema de Euclides (uma ferramenta básica): se
é primo e
então
ou
.
Passo 3
Prova curta do lema de Euclides (porque é o passo técnico que vamos usar). Suponha que
é primo e que
. Se
já está ok. Caso contrário,
não divide
, logo
. Pelo lema de Bézout existe inteiros
e
tais que
Multiplicando ambos os lados por
obtemos
Como
temos
; e claramente
. Portanto
divide a soma
, ou seja
. Assim mostramos que, quando
é primo e
, então
ou
. Isso termina a prova do lema.
Passo 4
Agora aplique o lema ao nosso problema. Suponha que exista um primo
que divide tanto
quanto
. Então
Como
, pelo lema de Euclides, de
segue que
. Analogamente, de
segue que
.
Passo 5
Portanto se um primo
divide simultaneamente
e
então
divide simultaneamente
e
. Mas isso contradiz a hipótese inicial de que
, pois não pode existir primo comum a
e
. Logo não existe primo
que divida ambos
e
— isto significa que
e
não têm nenhum fator primo em comum.
Se não existe nenhum primo comum a e
, então o máximo divisor comum é
. Portanto concluímos que
Se não existe nenhum primo comum a
ou seja,
e
são primos entre si.