Testes baseados em fatorações de n+1

Suponha dados inteiros n > 1, P e Qtais que D = P² - 4Q não é um quadrado módulo n. Seja

$$\alpha = \frac{P + \sqrt{D}}{2},$$

raiz da equação X² - PX + Q = 0. É fácil provar por indução que

$$\alpha^m = \frac{V_m + U_m \sqrt{d}}{2}$$

para todo natural m onde U_m e V_m são definidos recursivamente por
$$\begin{align}U_0 &= 0, & U_1 &= 1, & U_{m+2} &= P U_{m+1} - Q U_m, \notag\\ V_0 &= 2, & V_1 &= P, & V_{m+2} &= P V_{m+1} - Q V_m. \notag \end{align}$$
Se

$$\overline{\alpha}= \frac{P - \sqrt{D}}{2}$$

é a segunda raiz da equação X² - PX + Q = 0, podemos também escrever

$$U_m = \frac{\alpha^m - \overline{\alpha}^m}{\sqrt{D}},\qquad V_m = \alpha^m + \overline{\alpha}^m,$$

como se demonstra facilmente por indução. Segue destas fórmulas que

$$U_{n+1} = \frac{P U_n + V_n}{2}, \qquad V_{n+1} = \frac{D U_n + P V_n}{2}$$

e

$$U_{2m} = U_m V_m, \qquad V_{2m} = V_m^2 - 2 Q^m.$$

Estas fórmulas nos permitem calcular U_m e V_m módulo nem $C \log m$ operações (para alguma constante positiva C): escrevemos $m = \sum_{0 \le i < M} a_i 2^i$, definimos

$$m_k = \sum_{0 \le i < k} a_{i+N-k} 2^i$$

e calculamos sucessivamente U_m1, V_m1, ..., U_mk, V_mk, ..., U_mM = U_m, V_mM = V_m.

Lembramos que vimos no capítulo anterior que se p > 2é primo e d não é um quadrado módulo p então $K = ({\mathbb{Z} }/(p))[\sqrt{d}]$ é um corpo com p² elementos.

Proposição 3.17: Se n é primo e D não é um quadrado módulo nentão $\alpha^n = \overline{\alpha}$ em $K = ({\mathbb{Z} }/(n))[\sqrt{D}]$.

Dem: Suponhamos que n seja primo. Em K temos a identidade (X+Y)ⁿ = Xⁿ + Yⁿ: ela segue do binômio de Newton e do fato que

$$\binom{n}{m} = \frac{n!}{m! (n-m)!}$$

é múltiplo de n se 0 < m < n. Aplicando esta identidade a $\alpha$ temos

$$\alpha^n = \frac{P^n + D^{(n-1)/2} \sqrt{D}}{2^n} = \frac{P - \sqrt{D}}{2} = \overline{\alpha},$$

pois $P^n \equiv P \pmod n$, $2^n \equiv 2 \pmod n$ e $D^{(n-1)/2} \equiv -1 \pmod n$.          $\blacksquare$

Analogamente, se n é primo, temos $\overline{\alpha}^n = \alpha$ em K. Assim, ainda em K, $\alpha^{n+1} = \overline{\alpha}^{n+1} = \alpha \overline{\alpha}$. Segue da fórmula para U_m que $U_{n+1} \equiv 0 \pmod n$. Proclamamos este resultado como uma proposição:

Proposição 3.18: Se n é primo ímpar, $(\frac{D}{n}) = -1$e as seqüências U_m e V_m são definidas pelas recorrências
$$\begin{align}U_0 &= 0, & U_1 &= 1, & U_{m+2} &= P U_{m+1} - Q U_m, \notag\\ V_0 &= 2, & V_1 &= P, & V_{m+2} &= P V_{m+1} - Q V_m. \notag \end{align}$$
então $U_{n+1} \equiv 0 \pmod n$.

Dem: Acima.         $\blacksquare$

Esta proposição nos dá mais um algoritmo para testar a primalidade de n.

Proposição 3.19: Se $n \ne 2$ é primo, $n \nmid Q$, $n \nmid D$ e D é quadrado módulo nentão $U_{n-1} \equiv 0 \pmod n$.

Dem: No anel $K = {\mathbb{Z} }/(n)[\sqrt{D}]$, 2 é invertível, assim como D e $\sqrt{D}$. Em K temos, portanto,

$$\alpha^n = \frac{P^n+D^{\frac{n-1}{2}} \sqrt{D}}{2^n} = \frac{P+\sqrt{D}}{2} = \alpha$$

donde $\alpha^{n-1} = 1$ em K(pois $\alpha$ é invertível em K: de fato, $\alpha\overline{\alpha}= Q$, que é invertível em K). Do mesmo modo, $\overline{\alpha}^{n-1}=1$ em K e portanto temos, em K,

$$U_{n-1} = \frac{1}{\sqrt{D}} (\alpha^{n-1} - \overline{\alpha}^{n-1}) = 0,$$

ou seja, $U_{n-1} \equiv 0 \pmod n$.          $\blacksquare$

Em suma, se $n \ne 2$ é primo, $n \nmid Q$, $n \nmid D$ então $U_{n - (\frac{D}{n})}$ é múltiplo de n, o que se deve ao fato de $\alpha^m$ ser igual a $\overline{\alpha}^m$ se $m = n-(\frac{D}{n})$ no anel $K = {\mathbb{Z} }/(n)[\sqrt{D}]$. Observemos agora que se $\alpha^m = \overline{\alpha}^m$ em Kentão existe um inteiro r tal que

$$\alpha^m = \overline{\alpha}^n + nr \sqrt{D}$$

pois $\frac{\alpha^m-\overline{\alpha}^m}{\sqrt{D}} \in {\mathbb{Z} }$. Vamos usar este fato para mostrar por indução o seguinte resultado.

Proposição 3.20: Se $n \ne 2$ é primo, $n \nmid Q$ e $n \nmid D$ então, para todo natural $k \ge 1$,     $U_{m\cdot n^{k-1}}$ é múltiplo de n^k, onde $m = n-(\frac{D}{n})$.

Dem: Vamos supor, por hipótese de indução, que $\alpha^{m\cdot n^{k-1}} = \overline{\alpha}^{m\cdot n^{k-1}} + n^k r_k \sqrt{D}$, $r_k \in {\mathbb{Z} }$. Elevando os dois lados da equação à n-ésima potência temos

$$\alpha^{m\cdot n^k} = (\overline{\alpha}^{m\cdot n^{k-1}} + n... ...^n = \overline{\alpha}^{m\cdot n^k} + n^{k+1} r_{k+1} \sqrt{D}$$

onde r_k+1 pertence a ${\mathbb{Z} }[\sqrt{D}]$ por um lado, e por outro $n^{k+1} r_{k+1} = U_{m\cdot n^k}$ é um inteiro, o que implica que $r_{k+1} \in {\mathbb{Q} }\cap {\mathbb{Z} }[\sqrt{D}]$, e portanto é inteiro, o que conclui a prova da afirmação, que equivale ao enunciado.          $\blacksquare$

Proposição 3.21: Sejam $r \ge 1$ com $\operatorname{mdc}(r,Q)=1$, e (U_k)uma seqüência de Lucas (com U₀ = 0, U₁=1 e U_k+2 = PU_k+1 - QU_k). Se $A_r = \{k \in {\mathbb{N} }^\ast \mid U_k \text{ é múltiplo de } r\}$é não vazio então existe $a \in {\mathbb{N} }^\ast$ tal que $r \mid U_k$ se e somente se $a \mid k$. Tal a será denotado por $\operatorname{ord}_r U$.

Dem: Observemos inicialmente que para todo $m,n \in {\mathbb{N} }$, $n \ne 0$ temos U_m+n = U_mU_n+1 - QU_m-1U_n . De fato, considerando mfixo e n variável, os dois lados da igualdade satisfazem a mesma recorrência de segunda ordem X_k+2 = PX_k+1 - QX_k , $\forall k \in {\mathbb{N} }$, e temos, para n=0, $U_{m+0} = U_m\cdot U_1 - QU_{m-1}\cdot U_0$ (pois U₁=1 e U₀=0), e, para m=1, $U_{m+1}=U_m\cdot U_2 - QU_{m-1}\cdot U_1$ (pois U₂=P, U₁=1 e U_m+1 = PU_m - QU_n-1), o que implica a igualdade para todo $n \in {\mathbb{N} }$.

Como conseqüência, se $r\mid U_\ell$ e $r\mid U_n$ então $r\mid U_{m+n}$ . Por outro lado, se $r\mid U_\ell$ e $r\mid U_s$ , com $\ell < s$ então, como (fazendo $m=\ell$, $n=s-\ell$) $U_s = U_\ell U_{s-\ell+1} - QU_{\ell-1}U_{s-\ell}$ temos que r divide $QU_{\ell-1} U_{s-\ell}$ , mas $\operatorname{mdc}(Q,r)=1$ e $\operatorname{mdc}(U_{\ell-1}, U_\ell)$ divide $Q^{\ell-1}$ (o que pode ser facilmente provado por indução a partir de $U_{\ell+1} = PU_\ell - QU_{\ell-1}$), donde $\operatorname{mdc}(r, U_{\ell-1})$ também é igual a 1, logo $r\mid U_{s-\ell}$ . Assim, $m,n \in A_r \Rightarrow m+n \in A_r$ , e $\ell,s \in A_r$ , $\ell < s \Rightarrow s-\ell \in A_r$ , o que implica que A_r é da forma descrita, com $a = \min A_r$ (de fato, se existe $k \in A_r$ que não seja múltiplo de a, existiriam b e c naturais com k = ab+c, 0 < c < a, mas $k \in A_r$ e, como $a \in A_r$ , $ab \in A_r$ , logo c=k-ab pertenceria a A_r , contradizendo a definição de a.          $\blacksquare$

Teorema 3.22: Seja n > 1 um inteiro ímpar. Se existe um inteiro d primo com n tal que para todo fator primo r de n+1existem P^(r), Q^(r) e m^(r) inteiros com $\operatorname{mdc}(m^{(r)},n) = 1$ e $D^{(r)} = (P^{(r)})^2 - 4Q^{(r)} \equiv d (m^{(r)})^2 \pmod n$tais que a seqüência de Lucas associada (U_k^(r)) satisfaz $U_{n+1}^{(r)} \equiv 0 \pmod n$e $U_{\frac{n+1}{r}}^{(r)} \not\equiv 0 \pmod n$ então n é primo.

Dem: Seja $n+1 = r_1^{\alpha_1} r_2^{\alpha_2} \dots r_k^{\alpha_k}$ a fatoração prima de n+1. As hipóteses implicam que $r_i^{\alpha_i}$ divide $\operatorname{ord}_n U^{(r_i)}$ para $i=1,2,\dots,k$. Por outro lado, se $n = \ell_1^{\beta_1} \ell_2^{\beta_2}\dots \ell_s^{\beta_s}$é a fatoração prima de n, segue da Proposição 3.20 que $\operatorname{ord}_{\ell_j^{\beta_j}} U^{(r_i)}$ divide $\ell_j^{\beta_j-1}(\ell_j-(\frac{d}{\ell_j}))$(A hipótese $\ell_j \nmid Q^{(r_i)}$ é satisfeita. De fato, como $\operatorname{mdc}(n,d)=1$, $\ell_j$ não divide D^(r_i), e, se $\ell_j$ dividisse Q^(r_i), $\ell_j$ não dividiria P^(r_i), e teríamos $U_k^{(r_i)} \equiv (P^{(r_i)})^{k-1} \pmod{\ell_j}$para todo $k \ge 1$, e $\ell_j$ não dividiria U_k^(r_i) para nenhum $k \ge 1$, contradizendo o fato de n dividir U_n+1^(r_i)). Assim, se $M = \operatorname{mmc}\{\ell_j^{\beta_j-1}(\ell_j - (\frac{d}{\ell_j}))$, $1 \le j \le d\}$ temos que $\ell_j^{\beta_j}$ divide U_M^(r_i), para $1 \le j \le d$, $1 \le i \le k$. Isso implica que $n = \ell_1^{\beta_1}\dots\ell_s^{\beta_s}$ divide U_M^(r_i) para $1 \le i \le k$, e portanto $r_i^{\alpha_i}\vert\operatorname{ord}_n U^{(r_i)}\vert M$ para $1 \le i \le k$, donde n+1 divide M. Temos agora duas possibilidades:

(i) s=1.    Nesse caso temos que n+1 divide $M = \ell_1^{\beta_1}(\ell_1-(\frac{d}{\ell_1}))$ o que é absurdo se $(\frac{d}{\ell_1}) = 1$, pois teríamos $M < \ell_1^{\beta_1} = n$, e se $(\frac{d}{\ell_1}) = -1$ temos que $\ell_1^{\beta_1} + 1$ divide $\ell_1^{\beta_1-1}(\ell_1+1)$, o que implica $\beta_1=1$, ou seja, n é primo.

(ii) $s\ge2$.    Nesse caso
$$\begin{align}M &= \operatorname{mmc}\{\ell_j^{\beta_j-1}(\ell_j-(d/\ell_j))\} \n... ...)/2) \notag\\ \le 2n \prod_{j=1}^s \frac{\ell_j+1}{2\ell_j}, \notag \end{align}$$
que é sempre menor que n(pois $2\cdot\frac 46\cdot \frac{6}{10} < 1$) e portanto é um absurdo que n+1 divida M.          $\blacksquare$

A seguinte proposição, devida a Morrison, é análoga ao resultado de Pocklington:

Proposição 3.23: Seja N > 1 um inteiro ímpar e N+1=FR. Se existe um inteiro d primo com N tal que para todo fator primo r de Fexiste uma seqüência de Lucas U_n^(r) associada a inteiros P^(r), Q^(r) e um inteiro m^(r) primo com Ne $D^{(r)} = (P^{(r)})^2 - 4 Q^{(r)} \equiv d (m^{(r)})^2 \pmod N$tal que $N \mid U_{N+1}^{(r)}$ e $\operatorname{mdc}(U_{\frac{N+1}{r}}^{(r)}, N) = 1$ então cada fator primo $\ell$ de N satisfaz $\ell \equiv (\frac{d}{\ell}) \pmod F$.

Dem: Se $F = r_1^{\alpha_1} r_2^{\alpha_2} \dots r_k^{\alpha_k}$ é a fatoração prima de F então $\operatorname{ord}_N U^{(r_i)} \mid N+1$ para $1 \le i \le k$. Se $\ell$ é um fator primo de N, também temos $\operatorname{ord}_\ell U^{(r_i)} \mid N+1$. Como $\operatorname{mdc}(N, U_{\frac{N+1}{r_i}}^{(r_i)}) = 1$ segue que $\ell \nmid U_{\frac{N+1}{r_i}}^{(r_i)}$ , donde $\operatorname{ord}_\ell U^{(r_i)} \nmid \frac{M+1}{r_i}$ , e portanto $r_i^{\alpha_i}$ divide $\operatorname{ord}_\ell U^{(r_i)}$para $1 \le i \le k$. Por outro lado, $\operatorname{ord}_\ell U^{(r_i)}$ divide $\ell - (\frac{d}{\ell})$, donde $r_i^{\alpha_i}$ divide $\ell - (\frac{d}{\ell})$ para $1 \le i \le k \Rightarrow F$ divide $\ell - (\frac{d}{\ell}) \implies \ell \equiv(\frac{d}{\ell}) \pmod F$.          $\blacksquare$

Corolário 3.24: Nas condições da proposição, se F > R então N é primo.

Dem: Qualquer fator primo de N deve ser congruente a 1 ou a -1 módulo F, mas, se N é composto, deve ter um fator primo menor ou igual à sua raiz quadrada, que deve, pois, ser igual a F-1. Como $F > \sqrt{N+1}$, F²-1 > N, logo $\frac{N}{F-1} < F+1$, donde o outro fator primo de N também deve ser igual a F-1, e teríamos $N=(F-1)^2 \Rightarrow N+1 = F^2-2F+2$, que só seria múltiplo de F se F fosse igual a 2, e F-1igual a 1, absurdo.          $\blacksquare$

Proposição 3.25: Seja n > 1 um inteiro ímpar. Se para todo fator primo r de n+1 existem P^(r), Q^(r) inteiros com $\operatorname{mdc}(D^{(r)}, n) = 1$ onde D^(r) = (P^(r))² - 4 Q^(r)tais que a seqüência de Lucas associada (U_k^(r)) satisfaz $U_{n+1}^{(r)} \equiv 0 \pmod n$ e $\operatorname{mdc}(U_{\frac{n+1}{r}}^{(r)}, n) = 1$ então n é primo.

Dem: Seja $\ell$ um fator primo de n. Para cada fator primo r de n+1temos que $U^{(r)}_{n+1} \equiv 0 \pmod \ell$e $U^{(r)}_{\frac{n+1}{r}} \not\equiv 0 \pmod \ell$. Assim, se $r^{\alpha_r}$ é a maior potência de rque divide n+1, então $r^{\alpha_r}$ divide $\ell - (\frac{D^{(r)}}{\ell})$, como acima. Em particular, $r^{\alpha_r}$ divide $\ell^2 - 1 = (\ell - 1)(\ell + 1)$, donde n+1 divide $\ell^2 - 1$. Assim, $\ell^2 - 1 \ge n+1$ donde $\ell > \sqrt{n}$, o que implica na primalidade de n pois n não tem nenhum fator primo menor ou igual à sua raiz quadrada.          $\blacksquare$

Vamos agora dar outra prova do critério de Lucas-Lehmer usando os resultados anteriores.

Dem: A seqüência de Lucas associada a P=2, Q=-2, é dada pela fórmula $U_k = \frac{1}{2\sqrt 3}((1+\sqrt 3)^k - (1-\sqrt 3)^k)$. Temos $(1+\sqrt 3)^k = \frac{V_k}{2} + U_k\sqrt 3$, onde $V_k = (1+\sqrt 3)^k + (1-\sqrt 3)^k$. Além disso, U_2k = U_kV_k para todo $k \in {\mathbb{N} }$.

Para $r \ge 1$ temos
$$\begin{align}V_{2^r} &= (1+\sqrt 3)^{2^r} + (1-\sqrt 3)^{2^r} = (4+2\sqrt 3)^{2^... ...t 3)^{2^{r-1}} + (2-\sqrt 3)^{2^{r-1}}) = 2^{2^{r-1}} S_{r-1} \notag \end{align}$$
(onde S0=4, Sm+1 = Sm2-2, $\forall m \in {\mathbb{N} }$). Se n > 2 e Mn = 2n-1 divide Sn-2 então Mn divide V2n-1, logo também divide UMn+1 = U2n = U2n-1 V2n-1, e, como $U_{\frac{M_{n+1}}{2}} = U_{2^{n-1}}$, e Vk2 - 12Uk2 = 4(-2)k, segue que V2n-12 - 12U2n-12 = 22n-1+2, e, se Mn dividisse $U_{\frac{M_{n+1}}{2}}$ , dividiria também 22n-1+2, absurdo. Assim, pelo Teorema 3.22, Mn é primo.

Por outro lado, se M_n é primo, como D=12, $(\frac{12}{M_n}) = (\frac{3}{M_n}) = -(\frac{M_n}{3}) = 1$, logo M_n divide U_Mn+1 = U_2ⁿ, e, como
$$\begin{align}V_{2^{n-1}}^2 &= V_{2^n} + 2(-2)^{2^{n-1}} = V_{2^n} + 2 \cdot 2^{\... ...2}} = V_{2^n}+4(\frac{2}{M_n}) \equiv V_{2^n} + 4 \pmod{M_n}, \notag \end{align}$$
pois $2\equiv 2^{n+1} \equiv(2^{\frac{n+1}{2}})^2 \pmod{M_n}$(já sabemos que n deve ser um primo ímpar). Temos $V_{2^n} = (1+\sqrt 3)^{2^n} + (1-\sqrt 3)^{2^n} = (1+\sqrt 3)^{M_n+1} + (1-\sqrt 3)^{M_n+1}$, que é igual a $(1-\sqrt 3)(1+\sqrt 3) + (1+\sqrt 3)(1-\sqrt 3) = -4$em $K={\mathbb{Z} }/(M_n)[\sqrt 3]$(pois $(\frac{3}{M_n}) = -1$) donde $V_{2^{n-1}}^2 = V_{2^n} + 4 \equiv 0 \pmod{M_n}$e portanto $M_n \mid V_{2^{n-1}} = 2^{2^{n-2}} S_{n-2}$. Assim, M_n divide S_n-2, o que conclui nossa nova demonstração do critério de Lucas-Lehmer.          $\blacksquare$

Se N é um primo ímpar e d não é quadrado módulo N, então $K = {\mathbb{Z} }/(N)[\sqrt d]$ é um corpo finito com N² elementos e portanto existem inteiros a e b tais que $x = a+b\sqrt d$ é uma raiz primitiva de K. Sejam $\overline x= a-b\sqrt d$ e, para $m \in {\mathbb{N} }$, $U_m = (x^m-\overline x^m)/2b\sqrt d$. Temos U₀=0, U₁=1 e U_m+2 = 2aU_m+1 - (a²-db²)U_m para todo $m \in {\mathbb{N} }$. Temos ainda $b \ne 0$ em K, senão x pertenceria a ${\mathbb{Z} }/(M) \subset K$ e $\operatorname{ord}_K x$ dividiria N-1. Assim, b e $\sqrt{d}$ são invertíveis em K e, se P = 2a, Q = a² - d b² então D = P² - 4Q = 4d b²satisfaz $(\frac{D}{N}) = -1$. Pela proposição 3.18, $U_{n+1} \equiv 0 \pmod N$. Por outro lado, se m é menor que N+1, caso N divida U_m teríamos $x^m = \overline x^m$ em K, donde teríamos em K, $(\overline x/x)^m = 1$. Pela proposição 3.17, $\overline x= x^N$, logo x^(N-1)m = 1, absurdo, pois $\operatorname{ord}_{K} x = N^2-1 = (N-1)(N+1) > (N-1)m$. Isto fornece recíprocas para os resultados desta seção.