Sejam
,
coprimo com
, e seja
. Dados inteiros não-negativos
e
, mostre que
Passo 1
O enunciado dá as seguintes informações e pede a seguinte equivalência.
- Dados:
e tal que . - Define-se
como a ordem multiplicativa de módulo , isto é, o menor inteiro positivo tal que
- Dados inteiros não-negativos
e .
Pergunta: mostrar que
Passo 2
Primeiro vou explicar e provar por que existe a ordem
e uma propriedade básica dela.
Definição/observação sobre existência: como
, os restos dos números
ao dividir por
pertencem a um conjunto finito
. Pelo princípio da casa dos pombos, existem índices
tais que
Multiplicando ambos os lados por um inverso de
(que existe porque
) obtemos
Assim existe algum inteiro positivo
com
. Definindo
como o menor desses inteiros positivos,
existe e satisfaz
. Essa
é a ordem
.
Propriedade minimal: pela definição de
como menor expoente positivo com
, se um inteiro positivo
satisfaz
então necessariamente
divide
. Vou provar essa propriedade mais adiante como lema.
Passo 3
Mostro a implicação direta (fácil): se
então
.
Escrevendo a congruência dos expoentes, existe inteiro
tal que
Então, usando propriedades de potências e que
, temos
Isso prova a direção
.
Passo 4
Lema (necessário para a outra direção): se
é um inteiro tal que
, então
divide
.
Prova do lema: aplique o algoritmo da divisão a
por
. Existem inteiros
e
com
tais que
Então
Reduzindo módulo
e usando
e também
, obtemos
Portanto
. Mas
foi escolhido como o menor inteiro positivo com essa propriedade, e
. A única possibilidade compatível é
. Logo
, isto é,
divide
. Isso conclui o lema.
Passo 5
Agora provamos a direção recíproca: se
então
.
Da congruência dada, multiplicamos ambos os lados por o inverso multiplicativo de
módulo
. Justificativa: como
, existe o inverso de
módulo
, e portanto existe também o inverso de
(é
). Multiplicando pela inversa de
obtemos
ou seja
(Nota: aqui
pode ser negativo; a congruência
é interpretada no grupo multiplicativo dos invertíveis módulo
, e a potência com expoente negativo corresponde a usar a potência do inverso. Alternativamente, pode-se tratar separadamente o caso
e
; o ponto essencial é que existe um inteiro
com
.)
Pelo lema do Passo 4, como
, obrigatoriamente
divide
. Logo
Isso prova a direção
.
Passo 6
Juntando os dois sentidos demonstrados nos Passos 3 e 5, obtemos a equivalência desejada: