Para todo inteiro
, prove que
e
são primos entre si se
é ímpar e
se
é par.
Passo 1
O enunciado pede para determinarmos
e mostrarmos que
quando
é ímpar e
quando
é par. Vamos usar propriedades de divisibilidade e o passo-chave do algoritmo de Euclides: se um número divide dois termos, ele também divide qualquer combinação linear deles.
Passo 2
Seja
Como
e
, então
divide qualquer combinação linear, em particular
Logo
Passo 3
Do fato
segue que
Portanto o máximo divisor comum só pode ser 1 ou 2.
Passo 4
Caso
seja ímpar, então
também é ímpar. Assim
não é divisível por 2, enquanto
é par (produto de ímpar por par). Como o único divisor comum possível é 1 ou 2, e 2 não divide
, concluímos
Passo 5
Caso
seja par, então
é par e
também é par. Portanto tanto
quanto
são divisíveis por 2. Como o único divisor comum possível é 1 ou 2, a única opção é
Resposta
Para todo inteiro
:
se é ímpar então
,
e se é par então
.
se
e se