Encontre todas as raízes primitivas de 17 .

Passo 1

O que o problema pede: encontrar todas as raízes primitivas de \,17.
Informações relevantes dadas / a usar:
  • O módulo é primo: p=17.
  • O grupo multiplicativo (\mathbb{Z}/17\mathbb{Z})^\times tem ordem p-1=16.
    Portanto uma "raiz primitiva de \,17" é um elemento de (\mathbb{Z}/17\mathbb{Z})^\times cujo ordem multiplicativa é \,16.

Passo 2

Definição e critério prático.
Uma raiz primitiva modulo \,17 é um elemento a tal que a ordem multiplicativa de a é \,16. Pela propriedade geral, para testar se a gera o grupo basta verificar, para cada primo q que divide 16, que
a^{16/q}\not\equiv 1 \pmod{17}.
Aqui 16=2^4, logo o conjunto dos primos divisores de 16 é \{2\}. Portanto o teste reduz-se a verificar apenas que
a^{8}\not\equiv 1 \pmod{17}.
Se a^{8}\equiv 1 então a ordem de a divide 8 e a não é primitiva; se a^{8}\not\equiv1 então a ordem de a não divide 8 e, como a^{16}\equiv1 por Fermat, a ordem é 16, logo a é primitiva.

Passo 3

Conexão com resíduos quadráticos (ferramenta que simplifica muito).
Pelo critério de Euler, para primo p\) e \(a\) coprimo a \(p\) vale \[a^{(p-1)/2}\equiv\begin{cases}1\pmod p,&\text{se \(a é resíduo quadrático mod }p,\[4pt]-1\pmod p,&se a é não-resíduo quadrático modp.\end{cases}]
Aqui (p-1)/2=8. Então a^{8}\equiv1 se, e só se, a é um resíduo quadrático modulo 17. Consequência importantíssima: os elementos com a^{8}\not\equiv1 são exatamente os resíduos quadráticos NÃO — isto é, os quadráticos não-resíduos. Portanto, para p=17, as raízes primitivas são exatamente os quadráticos não-resíduos módulo 17.]

Passo 4

Contagem esperada (checagem rápida): o número de raízes primitivas modulo um primo p é \varphi(p-1). Aqui \varphi(16)=\varphi(2^4)=2^4-2^3=16-8=8. Logo esperamos encontrar exatamente 8 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 \,17. Basta fazer os quadrados \,k^2\pmod{17} para k=1,\dots,8 (valores a partir de 9 repetem os anteriores):
\begin{aligned} 1^2 &\equiv 1 \pmod{17},\\\\ 2^2 &\equiv 4 \pmod{17},\\\\ 3^2 &\equiv 9 \pmod{17},\\\\ 4^2 &\equiv 16 \pmod{17},\\\\ 5^2 &\equiv 25\equiv 8 \pmod{17},\\\\ 6^2 &\equiv 36\equiv 2 \pmod{17},\\\\ 7^2 &\equiv 49\equiv 15 \pmod{17},\\\\ 8^2 &\equiv 64\equiv 13 \pmod{17}. \end{aligned}
Portanto o conjunto dos resíduos quadráticos modulo 17 é
\{1,2,4,8,9,13,15,16\}.

Passo 6

Obter as raízes primitivas: são os elementos de \{1,\dots,16\} que NÃO aparecem na lista de resíduos quadráticos. Ou seja, os não-resíduos quadráticos são
\{3,5,6,7,10,11,12,14\}.
Pelo raciocínio dos passos anteriores, cada um desses elementos satisfaz a^{8}\not\equiv1\pmod{17}, logo tem ordem 16 e é raiz primitiva modulo 17. (Para checar um exemplo: 3^{8}\equiv 16\equiv -1\pmod{17}, então 3^{8}\not\equiv1 e 3^{16}\equiv1; assim \,3 tem ordem 16.)

Resposta

\{3,5,6,7,10,11,12,14\}

Exercícios relacionados