Mostre que
é par se
.
Passo 1
O enunciado pede: mostrar que
é par sempre que
.
Informações dadas (definição que usaremos): é a função totiente de Euler, isto é, o número de inteiros
tais que
e
. Não precisamos de nenhuma outra informação externa ao enunciado.
Informações dadas (definição que usaremos):
Passo 2
Ideia principal (explicada de forma simples): vou emparelhar cada inteiro
com
. Para que esse emparelhamento seja válido para contar os elementos coprimos a
, preciso verificar duas coisas:
- se
então (ou seja, também é coprimo a ); - para
não acontece de ser congruente a módulo (ou seja, o par tem sempre dois elementos distintos).
Se as duas coisas forem verdadeiras, então os números coprimos ase organizam em pares de elementos distintos, logo o total é par.
Passo 3
Prova de que
. Isto é um fato simples de propriedades de máximo divisor comum: para inteiros
,
Explicação passo a passo: qualquer divisor comum de
e
divide também
e
; e qualquer divisor comum de
e
divide
. Portanto os conjuntos de divisores comuns coincidem e os máximos coincidem. Consequência imediata: se
então
. Logo o emparelhamento leva um número coprimo a outro número coprimo.
Passo 4
Mostrar que, para
, não existem pontos fixos do emparelhamento (isto é, não há
com
). Se
então
, isto é,
divide
. Mas se também
então qualquer divisor comum de
e
é 1, logo a divisibilidade
implica
. Assim
seria
ou
. Para
isso é impossível. Portanto, quando
,
para todo
com
. Em palavras: o par
sempre contém dois elementos distintos.
Passo 5
Conclusão combinando os fatos: o conjunto dos inteiros
com
e
é fechado pelo mapa
(pela Passo 3) e esse mapa é uma involução sem pontos fixos quando
(pela Passo 4). Logo os elementos coprimos a
se dividem em pares disjuntos de tamanho
. Assim o número total desses elementos,
, é soma de vários
's, isto é, um número par.