Testul Wilson

Testul lui Wilson pentru primalitatea unui număr întreg pozitiv n derivă direct din teorema lui Wilson . Testul se aplică în acest fel: dat un număr întreg pozitiv n (posibil impar, dacă n ≠ 2, altfel este divizibil cu 2), calculăm ( n - 1)! + 1 și verificăm dacă acest număr este divizibil cu n sau nu. În acel moment, dacă ( n - 1)! + 1 este divizibil cu n, deci n este prim, altfel n nu este prim.

Observăm imediat că acest test oferă probleme de calcul uriașe, după cum putem vedea din aceste două exemple.

Exemplul 1

Dacă luați un număr mic pentru n , cum ar fi n = 7, n - 1 = 6, trebuie să calculați

6!+1=1\cdot 2\cdot 3\cdot 4\cdot 5\cdot 6+1=721=7\cdot 103

{\ displaystyle 6! + 1 = 1 \ cdot 2 \ cdot 3 \ cdot 4 \ cdot 5 \ cdot 6 + 1 = 721 = 7 \ cdot 103}

{\ displaystyle 6! + 1 = 1 \ cdot 2 \ cdot 3 \ cdot 4 \ cdot 5 \ cdot 6 + 1 = 721 = 7 \ cdot 103}

și, prin urmare, divizibil cu 7.

Exemplul 2

Dacă iau un număr foarte mare pentru n , cum ar fi n = 10 ⁵ + 1, este necesar să fac 10 ⁵ operații, dintre care 10 ⁵ - 1 sunt produse cu un număr foarte mare, ceea ce durează mult și este din ce în ce mai dificil de realizat calculati.

Utilizarea testului

Prin urmare, se înțelege că acest test este practic inutilizabil pentru un număr mare și că se bazează pe un algoritm exponențial (cantitatea de calcule se bazează pe ( n - 1)! Al cărui calcul este exponențial). Mai utile, pentru a face față numărului mare, sunt testele Lucas-Lehmer și Miller-Rabin .

Elemente conexe

Portalul de matematică : accesați intrările Wikipedia care se ocupă de matematică