Encontre todas as raízes primitivas de 17 .
Passo 1
O que o problema pede: encontrar todas as raízes primitivas de
.
Informações relevantes dadas / a usar:
Informações relevantes dadas / a usar:
- O módulo é primo:
. - O grupo multiplicativo
tem ordem .
Portanto uma "raiz primitiva de" é um elemento de cujo ordem multiplicativa é .
Passo 2
Definição e critério prático.
Uma raiz primitiva modulo é um elemento
tal que a ordem multiplicativa de
é
. Pela propriedade geral, para testar se
gera o grupo basta verificar, para cada primo
que divide
, que
Uma raiz primitiva modulo
Aqui
, logo o conjunto dos primos divisores de
é
. Portanto o teste reduz-se a verificar apenas que
Se
então a ordem de
divide
e
não é primitiva; se
então a ordem de
não divide
e, como
por Fermat, a ordem é
, logo
é primitiva.
Passo 3
Conexão com resíduos quadráticos (ferramenta que simplifica muito).
Pelo critério de Euler, para primo
é resíduo quadrático mod }p,\[4pt]-1\pmod p,&se
é não-resíduo quadrático modp.\end{cases}]
Aqui
. Então
se, e só se,
é um resíduo quadrático modulo
. Consequência importantíssima: os elementos com
são exatamente os resíduos quadráticos NÃO — isto é, os quadráticos não-resíduos. Portanto, para
, as raízes primitivas são exatamente os quadráticos não-resíduos módulo
.]
Passo 4
Contagem esperada (checagem rápida): o número de raízes primitivas modulo um primo
é
. Aqui
. Logo esperamos encontrar exatamente
raízes primitivas, o que bate com a quantidade de não-resíduos quadráticos (metade dos elementos).
Passo 5
Calcular explicitamente os resíduos quadráticos modulo
. Basta fazer os quadrados
para
(valores a partir de
repetem os anteriores):
Portanto o conjunto dos resíduos quadráticos modulo
é
Passo 6
Obter as raízes primitivas: são os elementos de
que NÃO aparecem na lista de resíduos quadráticos. Ou seja, os não-resíduos quadráticos são
Pelo raciocínio dos passos anteriores, cada um desses elementos satisfaz
, logo tem ordem
e é raiz primitiva modulo
. (Para checar um exemplo:
, então
e
; assim
tem ordem
.)