Mostre que se g é uma raiz primitiva de m então g^{k} é raiz primitiva de m se e somente se \operatorname{mdc}(k, \varphi(m))=1. (sugestão: qual é a ordem multiplicativa módulo m de g^{k} ?)

Passo 1

O que o enunciado dá e o que pede:
  • Dado: g é uma raiz primitiva de m. Ou seja, g é um gerador do grupo multiplicativo (\mathbb{Z}/m\mathbb{Z})^\times.
  • Dado: k é um inteiro positivo qualquer.
  • Pede-se: provar que g^{k} é raiz primitiva de m se e somente se \operatorname{mdc}\big(k,\varphi(m)\big)=1.
Informações relevantes extraídas do enunciado:
  • Pelo fato de g ser raiz primitiva, a ordem multiplicativa de g módulo m é \varphi(m) (onde \varphi é a função totiente de Euler).
  • A questão sugere que a chave é calcular a ordem multiplicativa de g^{k} módulo m.

Passo 2

Definições e lembretes (explicados com calma):
  • Ordem de um elemento: para um inteiro a coprimo com m, a ordem de a modulo m é o menor inteiro positivo n tal que a^{n}\equiv 1\pmod{m}. Denotamos por \operatorname{ord}_m(a) esse n.
  • Raiz primitiva modulo m: é um elemento g tal que \operatorname{ord}_m(g)=\varphi(m). Ou seja, gera todo o grupo (\mathbb{Z}/m\mathbb{Z})^\times.
  • \operatorname{mdc}(x,y) (ou \gcd(x,y)): o maior divisor comum entre x e y.
Comentário amigável: a ideia intuitiva é que elevar um gerador g a uma potência k “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 a tem ordem n em um grupo cíclico, então a ordem de a^{k} é
\operatorname{ord}(a^{k})=\frac{n}{\operatorname{mdc}(n,k)}.
Vou provar este lema passo a passo (essa é a fórmula que vamos aplicar com a=g e n=\varphi(m)).
Prova do lema:
  • Seja n=\operatorname{ord}(a). Defina d=\operatorname{mdc}(n,k). Escreva n=d n' e k=d k' com \operatorname{mdc}(n',k')=1.
  • Primeiro, mostre que (a^{k})^{n'}=1. De fato,
(a^{k})^{n'}=a^{k n'}=a^{(d k') n'}=a^{k' (d n')}=a^{k' n}= (a^{n})^{k'}=1^{k'}=1.
Logo a ordem de a^{k} divide n'. Portanto \operatorname{ord}(a^{k})\le n'.
  • Agora mostre minimalidade: suponha que (a^{k})^{t}=1 para algum t\in\mathbb{Z}_{>0}. Isso significa a^{k t}=1, então n divide k t (pois n é a menor potência que dá 1). Escrevendo n=d n' e k=d k' obtemos
d n' \mid d k' t \quad\Rightarrow\quad n' \mid k' t.
Como \operatorname{mdc}(n',k')=1, segue que n' divide t. Assim qualquer t com (a^{k})^{t}=1 é múltiplo de n'. Portanto n' é o menor expoente positivo com essa propriedade, isto é,
\operatorname{ord}(a^{k})=n'=\frac{n}{d}=\frac{n}{\operatorname{mdc}(n,k)}.
Isso conclui a prova do lema.

Passo 4

Aplicando o lema ao nosso problema:
  • Como g é raiz primitiva de m, temos \operatorname{ord}_m(g)=\varphi(m).
  • Pelo lema, a ordem de g^{k} módulo m é
\operatorname{ord}_m(g^{k})=\frac{\varphi(m)}{\operatorname{mdc}\big(\varphi(m),k\big)}.

Passo 5

Concluir a equivalência pedida:
  • Se \operatorname{mdc}\big(k,\varphi(m)\big)=1, então
\operatorname{ord}_m(g^{k})=\frac{\varphi(m)}{1}=\varphi(m),
ou seja, g^{k} tem ordem \varphi(m) e portanto é raiz primitiva de m.
  • Reciprocamente, se g^{k} é raiz primitiva de m, então \operatorname{ord}_m(g^{k})=\varphi(m). Pela fórmula,
\varphi(m)=\operatorname{ord}_m(g^{k})=\frac{\varphi(m)}{\operatorname{mdc}\big(\varphi(m),k\big)}.
Dividindo ambos os lados por \varphi(m) (não nulo), obtemos \operatorname{mdc}\big(\varphi(m),k\big)=1.
Portanto g^{k} é raiz primitiva de m se e somente se \operatorname{mdc}\big(k,\varphi(m)\big)=1.

Passo 6

Comentário prático e exemplo rápido (para fixar a intuição):
  • Intuição: em um ciclo de comprimento n, o elemento a^k caminha com passo k. Se o passo e o comprimento são coprimos, o passo gera todo o ciclo; caso contrário gera apenas um subtamanho n/\operatorname{mdc}(n,k).
  • Exemplo concreto: para m=7 temos \varphi(7)=6. Um gerador é g=3. Se k=5 então \operatorname{mdc}(5,6)=1 e 3^{5} é também gerador. Se k=2 então \operatorname{mdc}(2,6)=2 e 3^{2} tem ordem 6/2=3, não é gerador.

Resposta

g^{k} é raiz primitiva de m se e somente se \operatorname{mdc}\big(k,\varphi(m)\big)=1.

Exercícios relacionados