Mostre que se
é uma raiz primitiva de
então
é raiz primitiva de
se e somente se
. (sugestão: qual é a ordem multiplicativa módulo
de
?)
Passo 1
O que o enunciado dá e o que pede:
- Dado:
é uma raiz primitiva de . Ou seja, é um gerador do grupo multiplicativo . - Dado:
é um inteiro positivo qualquer. - Pede-se: provar que
é raiz primitiva de se e somente se .
Informações relevantes extraídas do enunciado:
- Pelo fato de
ser raiz primitiva, a ordem multiplicativa de módulo é (onde é a função totiente de Euler). - A questão sugere que a chave é calcular a ordem multiplicativa de
módulo .
Passo 2
Definições e lembretes (explicados com calma):
- Ordem de um elemento: para um inteiro
coprimo com , a ordem de modulo é o menor inteiro positivo tal que . Denotamos por esse . - Raiz primitiva modulo
: é um elemento tal que . Ou seja, gera todo o grupo . -
(ou ): o maior divisor comum entre e .
Comentário amigável: a ideia intuitiva é que elevar um gerador
a uma potência
“salta” pelo ciclo; se esse salto tiver passo coprimo com o comprimento do ciclo, o salto ainda percorre todo o ciclo (fica gerador). Se o passo tiver fator comum com o comprimento, ele fica preso a um subtamanho do ciclo.
Passo 3
Lema central (grupo cíclico): se
tem ordem
em um grupo cíclico, então a ordem de
é
Vou provar este lema passo a passo (essa é a fórmula que vamos aplicar com
e
).
Prova do lema:
- Seja
. Defina . Escreva e com . - Primeiro, mostre que
. De fato,
Logo a ordem de
divide
. Portanto
.
- Agora mostre minimalidade: suponha que
para algum . Isso significa , então divide (pois é a menor potência que dá 1). Escrevendo e obtemos
Como
, segue que
divide
. Assim qualquer
com
é múltiplo de
. Portanto
é o menor expoente positivo com essa propriedade, isto é,
Isso conclui a prova do lema.
Passo 4
Aplicando o lema ao nosso problema:
- Como
é raiz primitiva de , temos . - Pelo lema, a ordem de
módulo é
Passo 5
Concluir a equivalência pedida:
- Se
, então
ou seja,
tem ordem
e portanto é raiz primitiva de
.
- Reciprocamente, se
é raiz primitiva de , então . Pela fórmula,
Dividindo ambos os lados por
(não nulo), obtemos
.
Portanto
é raiz primitiva de
se e somente se
.
Passo 6
Comentário prático e exemplo rápido (para fixar a intuição):
- Intuição: em um ciclo de comprimento
, o elemento caminha com passo . Se o passo e o comprimento são coprimos, o passo gera todo o ciclo; caso contrário gera apenas um subtamanho . - Exemplo concreto: para
temos . Um gerador é . Se então e é também gerador. Se então e tem ordem , não é gerador.