Testes baseados em fatorações de n-1

Proposição 3.5: Seja n > 1. Se para cada fator primo q de n-1 existe um inteiro a_qtal que $a_q^{n-1} \equiv 1 \pmod n$ e $a_q^{(n-1)/q} \not\equiv 1 \pmod n$então n é primo.

Dem: Seja q^k_q a maior potência de q que divide n-1. A ordem de a_q em $({\mathbb{Z} }/(n))^\ast$ é um múltiplo de q^k_q, donde $\varphi(n)$ é um múltiplo de q^k_q. Como isto vale para todo fator primo q de n-1, $\varphi(n)$ é um múltiplo de n-1 e n é primo.          $\blacksquare$

Proposição 3.6: (Pocklington) Se n - 1 = q^k R onde q é primo e existe um inteiro a tal que $a^{n-1} \equiv 1 \pmod n$e $\operatorname{mdc}(a^{(n-1)/q} - 1, n) = 1$ então qualquer fator primo de né congruo a 1 módulo q^k.

Dem: Se p é um fator primo de n então $a^{n-1} \equiv 1 \pmod p$e p não divide a^(n-1)/q - 1, donde $\operatorname{ord}_p a$, a ordem de a módulo p, divide n-1 mas não divide (n-1)/q. Assim, $q^k \vert \operatorname{ord}_p a \vert p - 1$, donde $p \equiv 1 \pmod q^k$.          $\blacksquare$

Corolário 3.7: Se n - 1 = FR, com F > R e para todo fator primo q de F existe a > 1tal que $a^{n-1} \equiv 1 \pmod n$ e $\operatorname{mdc}(a^{(n-1)/q} - 1, n) = 1$então n é primo.

Dem: Seja q um fator primo de F e q^k a maior potência de q que divide F; pela proposição anterior, todo fator primo de ndeve ser côngruo a 1 módulo q^k. Como isto vale para qualquer fator primo de F, segue que qualquer fator primo de n deve ser côngruo a 1 módulo F. Como $F > \sqrt{n}$, isto implica que n é primo.          $\blacksquare$

De fato, basta conhecer um conjunto de fatores primos cujo produto seja maior do que (n-1)^1/3 para, usando o resultado de Pocklington, tentar demonstrar a primalidade de n (o que deixamos como exercício). Os seguintes critérios clássicos são conseqüências diretas das proposições acima.

Fermat conjecturou que todo número da forma F_n = 2²ⁿ + 1 fosse primo e verificou a conjectura para $n \le 4$. Observe que 2ⁿ + 1 (e em geral aⁿ + 1 com $a \ge 2$) não é primo se n não é uma potência de 2: se p é um fator primo ímpar de n, podemos escrever $a^n + 1 = b^p + 1 = (b+1)(b^{p-1} - b^{p-2} + \cdots + b^2 - b + 1)$onde b = a^n/p. Euler mostraria mais tarde que F₅ não é primo (temos $F_5 = 4294967297 = 641 \cdot 6700417$) e já se demonstrou que F_n é composto para vários outros valores de n; nenhum outro primo da forma F_n = 2²ⁿ + 1 é conhecido, mas se conhecem muitos primos (alguns bastante grandes) da forma a²ⁿ + 1, que são conhecidos como primos de Fermat generalizados. O teste a seguir mostra como testar eficientemente a primalidade de F_n.

Corolário 3.8: (Teste de Pépin) Seja F_n = 2²ⁿ + 1; F_n é primo se e somente se $3^{(F_n - 1)/2} \equiv -1 \pmod {F_n}$.

Dem: Se $3^{(F_n - 1)/2} \equiv -1 \pmod {F_n}$ então a primalidade de F_nsegue da Proposição 3.5. Por outro lado, se F_n é primo então $3^{(F_n - 1)/2} \equiv (\frac{3}{F_n}) = (\frac{F_n}{3}) = (\frac{2}{3}) = -1 \pmod {F_n}$.          $\blacksquare$

Corolário 3.9: (Teorema de Proth; 1878) Seja $n = h\cdot 2^k + 1$ com 2^k > h. Então n é primo se e somente se existe um inteiro acom $a^{(n-1)/2} \equiv -1 \pmod n$.

Dem: Se n é primo, podemos tomar a qualquer com $(\frac{a}{n}) = -1$; ou seja, metade dos inteiros entre 1 e n-1 serve como a. A recíproca segue da Proposição 3.7 com F = 2^k.          $\blacksquare$

Corolário 3.10: Se $n = h\cdot q^k + 1$ com q primo e q^k > h. Então n é primo se e somente se existe um inteiro acom $a^{n-1} \equiv 1 \pmod n$ e $\operatorname{mdc}(a^{(n-1)/q} - 1, n) = 1$.

Dem: Se n é primo, podemos tomar a qualquer que não seja da forma x^q módulo n; ou seja, uma proporção de (q-1)/q dentre inteiros entre 1 e n-1serve como a. A recíproca segue da Proposição 3.7 com F = q^k.          $\blacksquare$

Uma expressiva maioria entre os 100 maiores primos conhecidos estão nas condições do teorema de Proth (ver tabelas). Isto se deve ao fato de primos desta forma serem freqüentes (mais freqüentes do que, por exemplo, primos de Mersenne) e que sua primalidade é facilmente demonstrada usando este resultado.