Teorema di Proth
Da Wikipedia, l'enciclopedia libera.
In teoria dei numeri, il teorema di Proth è un test di primalità per i numeri di Proth.
Il teorema afferma che, se p è un numero di Proth, nella forma k2n + 1 con k dispari e k < 2n, allora se per qualche numero intero a,
allora p è primo (ed è chiamato primo di Proth). Questo test è pratico perché se p è primo, qualunque a arbitrariamente scelto ha circa il 50% di probabilità di funzionare.
Indice |
[modifica] Esempi numerici
Alcuni esempi di applicazione del teorema sono:
- per p = 3, 21 + 1 = 3 è divisibile per 3, dunque 3 è primo.
- per p = 5, 32 + 1 = 10 è divisibile per 5, dunque 5 è primo.
- per p = 13, 56 + 1 = 15626 è divisibile per 13, dunque 13 è primo.
- per p = 9, che non è primo, non esiste alcun a tale che a4 + 1 è divisibile per 9.
Alcuni tra i più piccoli numeri primi di Proth sono (Sequenza OEIS:A080076 dell'OEIS):
A gennaio 2008, il più grande numero primo di Proth conosciuto è 19249 · 213018586 + 1, trovato dal progetto di calcolo distribuito Seventeen or Bust. Ha 3.918.990 cifre ed è il più grande numero primo conosciuto a non essere un primo di Mersenne. [1]
[modifica] Storia
François Proth (1852 - 1879) elaborò il teorema nel 1878 circa.
[modifica] Articoli correlati
[modifica] Collegamenti esterni
- (EN) Teorema di Proth su MathWorld.