Mostre que se
e
então
(i)
,
(ii)
.
(i)
(ii)
Passo 1
O enunciado dá as seguintes hipóteses e pede duas coisas.
-
Hipóteses dadas:
-
. -
.
-
-
O que o enunciado pede:
- (i) Mostrar que
. - (ii) Mostrar que
, onde denota a ordem multiplicativa de módulo , isto é, o menor inteiro positivo tal que (quando esse existe).
- (i) Mostrar que
Passo 2
Definições e fatos básicos que vamos usar (explicados de forma simples):
-
Definição de congruência:
significa que divide , isto é, existe com . -
Definição de
: o maior inteiro positivo que divide simultaneamente e . -
Propriedade útil sobre gcd (que vamos provar rapidamente): para todo
, Esta propriedade é natural porque qualquer divisor comum dee divide , e qualquer divisor comum de e divide . -
Ordem multiplicativa: para
com , existe algum tal que . Uma razão rápida para a existência é o Teorema de Euler: se então , onde é a função totiente de Euler; assim a ordem é bem definida como o menor inteiro positivo com essa propriedade. Também usaremos que congruência é compatível com multiplicação e portanto com potências: se então para todo .
Passo 3
Prova de (i): mostrar que
.
- Como
, existe tal que . Aplicando a propriedade mencionada: - Pela hipótese
, segue imediatamente - Comentário didático curto: a igualdade da mdc entre
e decorre do fato de que qualquer divisor comum de e divide , e qualquer divisor comum de e divide ; portanto os conjuntos de divisores comuns são iguais, logo os maiores também.
Passo 4
Preparação para (ii): observar que as ordens
e
existem e que podemos comparar expoentes usando propriedades de congruência.
- Pelo Passo 3 já sabemos
. Assim tanto quanto estão bem definidos como menores inteiros positivos tais que e . - Propriedade útil: se
então, por compatibilidade da congruência com multiplicação, para todo vale (Isto pode ser mostrado por indução em : caso base é dado; passo indutivo usa multiplicação.)
Passo 5
Mostrando que
divide
.
- Seja
. Então, por definição, - Como
, aplicando a propriedade de potências: - Assim
, o que mostra que a ordem de é um divisor de (pois a ordem é o menor expoente positivo que dá ; todo expoente que dá é múltiplo da ordem). Portanto
Passo 6
Mostrando que
divide
(simetria do argumento).
- Pelo mesmo raciocínio trocando os papéis de
e : seja . Então . Usando e compatibilidade das potências obtemos - Logo
.
Passo 7
Concluir (ii) a partir das divisibilidades mútuas.
- Das duas divisibilidades obtidas nos Passos 5 e 6 temos
o que implica que - Observação final: usamos essencialmente que congruência respeita potências e que a ordem é o menor expoente positivo que produz
módulo . Também foi necessário garantir que as ordens existem, o que se dá porque (e assim ) e então existe algum expoente (por exemplo ) que leva à unidade módulo .
Resposta
(i)
(ii)
(ii)