Mostre que se
e
são inteiros primos entre si, então
ou 2 .
Passo 1
O enunciado pede para mostrar que, dados inteiros
e
tais que
(isto é,
e
são primos entre si), o valor de
é igual a
ou a
. Informações relevantes que temos:
e
são inteiros e
. Não há outras condições adicionais.
Passo 2
Definimos
Vou lembrar um fato básico e muito útil: se um inteiro
divide dois números
e
, então qualquer combinação linear inteira
também é divisível por
. Em notação: se
e
então
para quaisquer inteiros
. Esse é o princípio por trás do algoritmo de Euclides — é a ferramenta que usaremos para reduzir a expressão.
Passo 3
Aplicando o princípio das combinações lineares, usemos a combinação
Como
divide
e também divide
, ele divide essa combinação. Agora fazemos as contas:
Portanto temos
Passo 4
De forma inteiramente análoga, se usarmos a combinação
obtemos
. Logo também vale
Combinando os dois resultados,
divide tanto
quanto
, então
Passo 5
Agora usamos um fato sobre o máximo divisor comum de potências: para quaisquer inteiros
,
Explicando rápido: se
então escrevemos
,
com
. Assim
e
, e o
entre eles é
. No nosso caso
, então
. Portanto da linha anterior obtemos
isto é,
Como
é um divisor positivo de
, concluímos que só há duas possibilidades:
ou
.
Passo 6
Para completar a prova convém mostrar quando cada caso ocorre (isso ajuda a entender e a decorar o resultado).
-
Se
e têm paridades diferentes (ou seja, um é par e o outro é ímpar), então é ímpar. Como já sabemos que só pode ser ou , e não divide um número ímpar, segue que . Exemplo concreto: dá . -
Se
e são ambos ímpares, então é par e, além disso, quadrados de ímpares são congruentes a módulo , então
ou seja,
é par mas não é múltiplo de
. Assim tanto
quanto
são pares, de modo que
; combinando com o fato de que
obtemos
. Exemplo:
dá
.
Esses exemplos confirmam que as duas possibilidades realmente ocorrem e que não há outras.