Teorema de Proth - Proth's theorem

Na teoria dos números , o teorema de Proth é um teste de primalidade para os números de Proth .

Afirma que se p é um número de Proth , da forma k 2 ⁿ + 1 com k ímpar ek <2 ⁿ , e se existe um inteiro a para o qual

${\ displaystyle a ^ {\ frac {p-1} {2}} \ equiv -1 {\ pmod {p}},}$

então p é primo . Nesse caso, p é chamado de proth de Proth . Este é um teste prático, porque se p é primo, qualquer escolhido um tem uma chance de 50 por cento do trabalho.

Se a for um módulo p não residual quadrático , o inverso também será verdadeiro e o teste será conclusivo. Tal a pode ser encontrado iterando um sobre pequenos primos e computando o símbolo de Jacobi até:

${\ displaystyle \ left ({\ frac {a} {p}} \ right) = - 1.}$

Assim, em contraste com muitos testes de primalidade de Monte Carlo (algoritmos randomizados que podem retornar um falso positivo ), o algoritmo de teste de primalidade baseado no teorema de Proth é um algoritmo de Las Vegas , sempre retornando a resposta correta, mas com um tempo de execução que varia aleatoriamente.

Exemplos numéricos

Exemplos do teorema incluem:

• para p = 3 = 1 (2 ¹ ) + 1, temos que 2 ^{(3-1) / 2} + 1 = 3 é divisível por 3, então 3 é primo.
• para p = 5 = 1 (2 ² ) + 1, temos que 3 ^{(5-1) / 2} + 1 = 10 é divisível por 5, então 5 é primo.
• para p = 13 = 3 (2 ² ) + 1, temos que 5 ^{(13-1) / 2} + 1 = 15626 é divisível por 13, então 13 é primo.
• para p = 9, que não é primo, não existe a tal que a ^{(9-1) / 2} + 1 seja divisível por 9.

Os primeiros primos de Proth são (sequência A080076 no OEIS ):

3, 5, 13, 17, 41 , 97 , 113 , 193 , 241, 257, 353, 449, 577, 641, 673, 769, 929, 1153….

O maior Proth prime conhecido em 2016 é , e tem 9.383.761 dígitos. Foi descoberto por Peter Szabolcs no projeto de computação distribuída PrimeGrid que o anunciou em 6 de novembro de 2016. É também o maior número primo não- Mersenne conhecido e o maior número de Colbert. O segundo maior proth conhecido é , encontrado por Seventeen ou Bust . ${\ displaystyle 10223 \ cdot 2 ^ {31172165} +1}$ ${\ displaystyle 19249 \ cdot 2 ^ {13018586} +1}$

Prova

A prova para este teorema usa o teste de primalidade de Pocklington-Lehmer e se assemelha muito à prova do teste de Pépin . A prova encontra-se na página 52 do livro de Ribenboim nas referências.

História

François Proth (1852-1879) publicou o teorema em 1878.

Veja também

• Teste de Pépin (o caso especial k  = 1, onde se escolhe a  = 3)
• Número Sierpinski

Referências

links externos

• Weisstein, Eric W. "Teorema de Proth" . MathWorld .