Ordens e raízes primitivas

Dados $n, a \in {\mathbb{Z} }$ com n > 0 e (a, n) = 1, definimos a ordem de a módulo n, denotada por $\operatorname{ord}_n a$, como sendo o menor inteiro positivo tcom $a^t \equiv 1 \pmod n$. Analogamente, se K for um corpo finito e $a \in K$, $a \ne 0$, definimos a ordem de a em K, denotada por $\operatorname{ord}_K a$, como sendo o menor inteiro positivo tcom $a^t = 1 \in K$; temos $\operatorname{ord}_p a = \operatorname{ord}_{{\mathbb{Z} }/(p)} a$.

Claramente $a^e \equiv a^{e'} \pmod n$se e somente se $e \equiv e' \pmod {\operatorname{ord}_n a}$; pelo teorema de Euler, $\operatorname{ord}_n a\vert\varphi(n)$.

Dizemos que a é uma raiz primitiva módulo n se $\operatorname{ord}_n a = \varphi(n)$. Analogamente, dizemos que a é uma raiz primitiva em K se $\operatorname{ord}_K a = q-1$, onde q = |K| é o número de elementos de K. Por exemplo, 2 é raiz primitiva módulo 5 mas 2 não é raiz primitiva módulo 7 ( $2^3 \equiv 1 \pmod 7$). Também é fácil verificar que não existe raiz primitiva módulo 8 pois se x é ímpar então $x^2 \equiv 1 \pmod 8$. Podemos também dizer que a é raiz primitiva se a função
$$\begin{align}{\mathbb{Z} }/(\varphi(n)) &\to ({\mathbb{Z} }/(n))^\ast \notag\\ r &\mapsto a^r \notag \end{align}$$
ou
$$\begin{align}{\mathbb{Z} }/(q - 1) &\to K^\ast \notag\\ r &\mapsto a^r \notag \end{align}$$
é injetora. Como o domínio e contradomínio são conjuntos finitos com o mesmo número de elementos, a função é injetora se e somente se ela é sobrejetora. Podemos assim dizer que a é uma raiz primitiva módulo nse e somente se para todo $b \in ({\mathbb{Z} }/(n))^\ast$ (ou para todo $b \in K^\ast$) existe r com a^r = b.

Um corolário desta caracterização de raízes primitivas é que se a é raiz primitiva módulo n e m|n então a é raiz primitiva módulo m. O objetivo da próxima seção é caracterizar os valores de n para os quais existe uma raiz primitiva módulo n. Nesta seção mostraremos que todo corpo finito admite raiz primitiva; em particular existe raiz primitiva módulo p para qualquer primo p.

Precisamos primeiro de uma versão do pequeno teorema de Fermat para corpos finitos:

Teorema 2.9: Se K é um corpo finito e q = |K|então a^q - a = 0 para todo $a \in K$.

Dem: Se a = 0 o teorema vale; vamos supor a partir de agora $a \ne 0$. Sejam $b_1, \ldots b_{q-1}$ os elementos não nulos de K. Os elementos $a b_1, \ldots a b_{q-1}$ são todos não nulos e distintos, logo são os próprios $b_1, \ldots b_{q-1}$, apenas permutados. Assim
$$\begin{align}b_1 \cdot b_2 \cdots b_{q-1} &= (a b_1) (a b_2) \cdots (a b_{q-1}) \notag\\ &= a^{q-1} (b_1 \cdot b_2 \cdots b_{q-1}) \notag \end{align}$$
e a^q-1 = 1.          $\blacksquare$

Segue deste teorema que $\operatorname{ord}_K a \vert q-1$, analogamente ao que já sabiamos para ${\mathbb{Z} }/(n)$. A partir do que vimos sobre polinômios temos também que

$$x^q - x = x(x - b_1)\cdots (x - b_{q-1})$$

em K[x].

Teorema 2.10: Se K é um corpo finito então existe raiz primitiva em K.

Dem: Seja d um divisor de q-1: definimos N(d) como o número de elementos de $K^\ast$ de ordem d. Claramente $\sum_{d \vert q-1} N(d) = q-1$.

Se N(d) > 0, seja a_d um elemento de K com $\operatorname{ord}_K a_d = d$: os elementos $1, a_d, a_d^2, \ldots a_d^{d-1}$são raízes do polinômio x^d - 1 = 0. Como este polinômio tem no máximo d raízes, estas são todas as raízes. Assim, os elementos de K de ordem d são precisamente a_d^r, $r \in ({\mathbb{Z} }/(d))^\ast$. Assim os únicos valores possíveis para N(d) são 0 e $\varphi(d)$. Mas como $\sum_{d \vert q-1} N(d) = \sum_{d \vert q-1} \varphi(d) = q-1$, temos $N(d) = \varphi(d)$ para todo d | q-1. Em particular N(q-1) > 0 e existem raízes primitivas.          $\blacksquare$

Apesar de existirem raízes primitivas módulo p para todo primo pnão existe uma fórmula simples para obter uma raiz primitiva. Por outro lado, conjectura-se que todo inteiro que não é um quadrado é raiz primitiva para infinitos valores de p (conjectura de Artin).

Corolário 2.11: Dados $x \in K^\ast$ e um inteiro positivo kexiste $y \in K^\ast$ com y^k = xse e somente se $x^{(q-1)/\operatorname{mdc}(k,q-1)} = 1$, onde q = |K|.

Dem: Se x = y^k então $x^{(q-1)/\operatorname{mdc}(k,q-1)} = (y^{q-1})^{k/\operatorname{mdc}(k,q-1)} = 1$pois y^q-1 = 1. Suponha agora que $x^{(q-1)/\operatorname{mdc}(k,q-1)} = 1$. Sejam a uma raiz primitiva de K e $r \in {\mathbb{Z} }$ com x = a^r. Temos $(a^r)^{(q-1)/\operatorname{mdc}(k,q-1)} = 1$ donde $\operatorname{mdc}(k,q-1) \mid r$e portanto existem inteiros u, v com ku + (q-1)v = r. Assim $x = a^r = a^{ku + (q-1)v} = (a^u)^k \cdot (a^{q-1})^v = y^k$onde y = a^u.          $\blacksquare$