Raízes primitivas em ${\mathbb{Z} }/(n)$

Nesta seção caracterizaremos os inteiros n para os quais existe raiz primitiva módulo n.

Lema 2.12: Sejam p um número primo e $a \in {\mathbb{Z} }$uma raiz primitiva módulo p. Então a ou a' = a + p é raiz primitiva módulo p².

Dem: Pelo binômio de Newton, ${a'}^p = (a+p)^p \equiv a^p \pmod {p^2}$. Sem perda de generalidade, podemos supor $a^p \not\equiv a \pmod {p^2}$ou $a^{p-1} \not\equiv 1 \pmod {p^2}$, donde $\operatorname{ord}_{p^2} a \ne p-1$. Como $p-1 = \operatorname{ord}_p a \mid \operatorname{ord}_{p^2} a \mid \varphi(p^2) = p(p-1)$isto implica em $\operatorname{ord}_{p^2} a = p(p-1)$.          $\blacksquare$

Lema 2.13: Se p é um número primo ímpar e a é raiz primitiva módulo p² então a é raiz primitiva módulo p^k para todo k > 2, $k \in {\mathbb{Z} }$.

Dem: Temos $a^{p-1} \equiv 1 \pmod p$, mas $a^{p-1} \not\equiv 1 \pmod {p^2}$, donde a^p-1 = 1 + b₀ p com $b_0 \not\equiv 0 \pmod p$. Vamos mostrar por indução que a^{pj (p-1)} = 1 + b_j p^j+1com $b_j \equiv b_0 \pmod p$. Podemos escrever
$$\begin{align}a^{p^{j+1} (p-1)} &= (a^{p^j (p-1)})^p \notag\\ &= (1 + b_j p^{j+1... ... p^{(p-1)j + p - 2}) p^{j+2} \notag\\ &= 1 + b_{j+1} p^{j+2} \notag \end{align}$$
com $b_{j+1} \equiv b_j \pmod p$ pois o parêntesis na penúltima linha é da forma 1 + um múltiplo de p. Esta última afirmação segue da positividade dos expoentes de pexceto no caso j = 0; neste caso o expoente do primeiro termo não trivial é zero mas temos $\binom{p}{2} \equiv 0 \pmod p$ pois p > 2(é neste ponto que precisamos da hipótese de p ser ímpar). O lema segue de $a^{(p-1)p^{k-2}} \not\equiv 1 \pmod {p^k}$ por indução, pois teremos $(p-1) p^{k-2} = \operatorname{ord}_{p^{k-1}} a \mid \operatorname{ord}_{p^k} a \mid \varphi(p^k) = (p-1) p^{k-1}$, donde $\operatorname{ord}_{p^k} a = (p-1) p^{k-1}$.          $\blacksquare$

Lema 2.14: Seja n > 1. O número de soluções para a congruência $x^2 \equiv 1 \pmod n$ é:

(a)

1 se n = 2,

(b)

2 se n = 4,

(c)

4 se n = 2^k, k > 2,

(d)

2 se n = p^k, p um primo ímpar,

(e)

2^{m + i} se $n = 2^k p_1^{e_1} \cdots p_m^{e_m}$, onde i = 0 se $k \le 1$, i = 1 se k = 2 e i = 2 se k > 2.

Dem: Os itens (a) e (b) são verificáveis diretamente. As quatro soluções no item (c) são 1, 2^k-1 - 1, 2^k-1 + 1 e 2^k - 1. De fato, é fácil verificar que estes quatro valores são soluções da congruência. Por outro lado, para que a seja solução da congruência devemos ter 2^k | (a+1)(a-1) = a² - 1; portanto a deve ser ímpar. Um dentre a-1 e a+1 deve ser da forma 2b, b ímpar. Assim o outro deve ser múltiplo de 2^k-1, o que diz que a deve ter um dos quatro valores acima. Analogamente para o item (d), apenas um dentre a - 1 e a + 1é múltiplo de p, o que só permite as soluções 1 e n-1.

Para o item (e) usamos os itens anteriores e o teorema chinês dos restos: a é solução da congruência acima se e somente se a satisfaz $a^2 \equiv 1 \pmod {2^k}$ e $a^2 \equiv 1 \pmod {p_i^{e_i}}$ para cada i. Assim, o número de soluções módulo n é o produto do número de soluções módulo 2^k, p₁^e₁, ..., p_m^e_m, o que nos dá a fórmula do item (e).          $\blacksquare$

Teorema 2.15: Um inteiro n > 1 admite raiz primitiva se e somente se n = 2, n = 4 ou n é da forma p^k ou 2 p^k, onde p é um primo ímpar, admite raiz primitiva.

Dem: Os casos n = 2 e n = 4 podem ser verificados diretamente. A existência de uma raiz primitiva módulo p^k (p um primo ímpar) segue dos dois primeiros lemas desta seção. Para o caso 2 p^k, seja a uma raiz primitiva módulo p^k: a ou a + p^k, aquele que for ímpar, será uma raiz primitiva módulo 2 p^k pois $\varphi(2 p^k) = \varphi(p^k)$.

Se n não for de uma destas formas, o lema anterior garante que a congruência $x^2 \equiv 1 \pmod n$ admite mais de duas soluções. Por outro lado, a existência de uma raiz primitiva a módulo ngarante que a congruência $x^2 \equiv 1 \pmod n$ só tem as soluções 1 e n-1. De fato, qualquer solução pode ser escrita da forma a^k para algum ke nossa congruência torna-se $a^{2k} \equiv 1 \pmod n$ou $2k \equiv 0 \pmod {\varphi(n)}$, que só tem as soluções k = 0 (a^k = 1) e $k = (\varphi(n))/2$( $a^k \equiv n-1 \pmod n$).

Outra demonstração, sem usar o lema anterior, consiste em observar que se n não for de uma destas duas formas então n = n₁ n₂, com $n_1, n_2 \ge 3$ e $\operatorname{mdc}(n_1,n_2) = 1$. Temos então $a^{\varphi(n)/2} \equiv 1 \pmod n$ para todo a inteiro com $\operatorname{mdc}(a,n) = 1$, pois $\varphi(n_1) \mid \varphi(n)/2$ e $\varphi(n_2) \mid \varphi(n)/2$.          $\blacksquare$