Q5
Seja
um número primo. Mostre que
, para todo
.
Dica: Use que
.
Dica: Use que
Passo 1
O enunciado dá:
-
é um número primo (logo é ímpar e ). -
é um inteiro qualquer, .
O que precisa ser mostrado é a divisibilidade
Também é dado (na dica) que
. Portanto é suficiente mostrar que
é múltiplo de cada um dos fatores
,
e
.
Passo 2
Divisibilidade por
.
Queremos mostrar que
Se
divide
então isso é óbvio, pois
é múltiplo de
e, portanto, múltiplo de
. Suponha então que
. Considere os resíduos
tomados módulo
. Como multiplicar por
é bijetivo em
quando
, esses resíduos são uma permutação de
módulo
. Tomando o produto dos termos em cada lista, obtemos a congruência
O lado esquerdo é
, portanto
Como
(nenhum dos fatores
é múltiplo de
), podemos cancelar
na congruência e obter
o que implica
ou seja,
. (Isto é a forma elementar do Teorema de Fermat.)
Passo 3
Divisibilidade por
.
Como
é primo,
é ímpar. Para qualquer inteiro
há duas possibilidades:
- Se
é par então é par e assim é par. - Se
é ímpar então também é ímpar (produto de ímpares é ímpar) e novamente é par.
Em termos de congruências, isso significa que para todo
logo
.
Passo 4
Divisibilidade por
.
Se
então
trivialmente. Se
então, pelo pequeno teorema de Fermat (ou pelo teorema de Euler com
), temos
Como
é impar, existe
inteiro tal que
. Então
portanto
.
Passo 5
Conclusão combinando os fatores.
Mostramos que
,
e
. Como
,
e
são primos distintos (pois
), eles são dois a dois coprimos. Se
e
são inteiros coprimos e ambos dividem um inteiro
, então
divide
(uma forma simples de ver isto: escreva
; como
e
, segue que
, logo
e
). Aplicando isto sucessivamente obtemos que