Sejam
. Mostre que:
Se
e
são primos entre si, então
ou 2.
Se
Passo 1
O enunciado nos dá os números inteiros
(o
não é usado na prova) e afirma que
e
são primos entre si, ou seja,
. O que precisamos mostrar é que o máximo divisor comum de
e
só pode ser
ou
. Em outras palavras, provar que
é igual a
ou igual a
.
Informações relevantes dadas:
-
. -
.
O que é pedido:
- Mostrar que
é ou .
Passo 2
Definimos
. Pela definição de máximo divisor comum, temos que
é um inteiro positivo e que
Aqui estou usando a notação
para indicar “
divide
”.
Passo 3
Usando que
divide ambos
e
, podemos formar combinações lineares dessas duas quantidades. Em particular, somando e subtraindo:
Como
divide
e também
, ele deve dividir qualquer combinação inteira dessas duas quantidades. Logo
(Comentário didático rápido: a propriedade usada é simples: se
e
, então para quaisquer inteiros
vale
. Aqui usamos
e
.)
Passo 4
Agora vamos analisar os possíveis divisores primos de
. Seja
um primo que divide
. Então, por
e
, temos
e
.
- Se
for um primo ímpar (ou seja, ), então não divide . Assim, de segue , e de segue . Portanto dividiria simultaneamente e , o que contradiz .
Logo nenhum primo ímpar pode dividir
. Assim todos os primos que dividem
devem ser
. Consequentemente,
é uma potência de
; existe
tal que
Passo 5
Falta restringir o expoente
. Suponha, por contradição, que
. Isso significa que
, então
e
. Somando essas duas divisibilidades obtemos
, isto é,
, logo
é par. Subtraindo obtemos
, logo
, então
também é par. Mas se
e
são ambos pares, então
, contradizendo
.
Portanto não pode ocorrer
. Logo
só pode ser
ou
, isto é,
só pode ser
ou
. (Em linguagem de divisibilidade, isso equivale a escrever
.)
Passo 6
Comentário final (didático e prático): quando
e
têm paridades diferentes (um é par e o outro ímpar), então
e
são ímpares e o gcd será
. Quando
e
são ambos ímpares (único caso em que podem ser coprimos e ter mesma paridade), então
e
são pares e o gcd será
. Isso mostra também que os dois valores possíveis,
e
, realmente ocorrem em exemplos concretos.