Se é primo e se a não é resto quadrático de p , prove que a é raiz primitiva, módulo p .
Passo 1
O enunciado considera um primo de Fermat e um inteiro coprimo com . Queremos mostrar que, se não é resto quadrático módulo , então tem ordem maximal em e, portanto, é raiz primitiva. Lembrando que
ou seja, todo elemento de ( Z/p Z)^times tem ordem um divisor de 2^k.
Passo 2
Pelo Critério de Euler, para é resto quadrático},\ -1\pmod p, & se não é resto quadrático. \end{cases}]
Como e, por hipótese, não é resto quadrático, obtemos
Passo 3
A ordem de a em ( Z/p Z)^times é o menor divisor d de 2^k tal que a^dequiv1pmod p. Se houvesse d<2^k com essa propriedade, então d dividindo 2^k-1 implicaria
a^2^,k-1 =(a^d)^2^,k-1/d equiv1pmod p,
o que contradiz a^2^,k-1equiv-1. Portanto não existe divisor próprio d<2^k com a^dequiv1, e a ordem de a deve ser exatamente 2^k=p-1.
Resposta
a é raiz primitiva módulo p.
Cálculo - Hygino Domingues - Fundamentos de Aritmética - 1ª Edição - Capítulo 3.Exercícios - Ex. 349