Prove cada uma das seguintes afirmações:
Se a tem ordem hk, módulo n, então a^h tem ordem k, bmod n.

Passo 1

Resumindo o enunciado: temos um elemento a invertível módulo n cuja ordem é hk. Queremos mostrar que o elemento a^h tem ordem exatamente k módulo n. Vamos usar a definição de ordem de um elemento num grupo: é o menor inteiro positivo t tal que o elemento elevado a t seja congruente a 1 módulo n, e também o fato de que, se um elemento elevado a um certo expoente dá 1, então a ordem desse elemento divide esse expoente.

Passo 2

Como a ordem de a é hk, temos
a^hkequiv 1pmodn
Isso implica
(a^h)^k = a^hkequiv 1pmodn,
ou seja, o menor expoente que faz (a^h)^expoenteequiv1 deve dividir k. Logo a ordem de a^h é um divisor de k.

Passo 3

Seja r a ordem de a^h, isto é, r é o menor inteiro positivo tal que
(a^h)^r equiv 1pmodn
Então
a^hr = (a^h)^r equiv 1pmodn
Como a ordem de a é hk, segue que
hk mid hr
Dividindo ambos os lados por h (que é positivo), obtemos
k mid r
Portanto r é um múltiplo de k, mas já vimos que r também divide k. A única possibilidade é
r = k

Resposta

A ordem de a^h módulo n é k.

Exercícios de Livros Relacionados