Test de primalitate

Una din problemele calculării numerelor prime este dificultatea de a stabili primalitatea lor pentru numere extrem de mari. Chiar și cu ajutorul super calculatoarelor, testele de primalitate existente în prezent impune, fie calcularea unor numere mult mai mari pentru a stabili primalitatea unui număr mai mic, ca în cazul teoremei lui Wilson sau a micii teoreme a lui Fermat , fie un număr impresionant de calcule.

Propun în acest topic un test ceva mai simplu, dar care trebuie demonstrat.
Pentru valorile pe care le-am calculat testul este valabil.
Nu l-am verificat pentru toate numerele consecutive până la valoarea la care am calculat, ci le-am luat aleatoriu fără să găsesc un contra exemplu.

Un număr n este prim dacă atât valoarea , cât și valoarea se divid cu n. Dacă cel puțin una dintre ele nu se divide cu n, atunci n nu este un număr prim.

Însă afirmația de mai sus trebuie demonstrată.
Personal, îi văd o utilitate practică ridicată pentru stabilirea primalității unui număr, mai ales pentru numerele foarte mari calculate cu ajutorul calculatorului.

Presupunând că afirmația de mai sus ar fi falsă, probabilitatea ca n să fie prim crește proporțional, dacă și valoarea se divide cu n.

Cu siguranță este prim dacă pentru orice toate numerele obținute prin formulele : și se divid cu n.

Eu cred totuși că este suficientă doar calcularea valorilor și a valorii .

De fapt prima, se divide cu orice n număr impar .

Ar însemna că testul se rezumă doar la a calcula dacă se divide cu n.
Dacă nu se divide, n nu este un număr prim.
Dacă se divide cu n, atunci n este număr prim.
Mai trebuie verificat o idee prin calcul, după care să încercăm să și demonstrăm asta.

Și cred că se poate și demonstra.

Da... eu am calculat pentru numerele care nu sunt prime.
Am găsit exemple pentru n prim care nu divide, dar nu am găsit contraexemple pentru n nonprim care divide.

O să încerc să găsesc explicația.

De fapt nu este o greșeală, pentru că am calculat dacă se divide cu n.

Când este vorba despre 3! , deci numitorul fracției este 6 și nu 3,
adică
În cazul ăsta merge.
Dacă nu se divide, n nu este un număr prim.
Dacă se divide cu n, atunci n este număr prim.

Am luat la calculat valorile consecutive până pe la vreo 500.
Concluzia la care am ajuns este următoarea, ca și regulă generală :

Fie p cel mai mic număr prim care divide un număr natural n.
Pentru orice număr par 2k și număr impar 2k+1, astfel încât , dacă n nu este un număr prim atunci nu divide niciuna din valorile:

sau/și

Sau mai simplu spus, dacă p este cel mai mic număr prim care divide n, atunci pentru m > p, orice valoare obținută prin formula



se divide cu n , iar pentru nu se divide cu n, dacă n nu este număr prim.



este pentru generalizare, iar semnul este dat de paritatea lui m. Dacă m este un număr par semnul va fi minus, dacă m este un număr impar, semnul va fi plus.

Un caz mai mult sau mai puțin particular îl reprezintă valoarea lui n un număr prim, caz în care pentru orice m>1 formula se divide cu n, dacă acesta este prim. Generalizarea enunțului este valabilă și pentru cazul n număr prim, pentru că acesta nu are divizori, cel mai mic număr prim care îl divide este el însuși (1 nefiind considerat prim), situație în care prima valoare pe care trebuie să o aibă m ca formula să nu se dividă cu p(adică n) este chiar p(adică n).

Câteva exemple pentru a înțelege mai bine raționamentul.
Calculăm spre exemplu, numărul 25. Cel mai mic număr prim care divide 25 este 5. Din enunț reiese că pentru orice m mai mic decât 5, rezultatul obținut de formluă se divide cu 25 :


Rezultatul se divide cu 25.


Rezultatul se divide cu 25


Rezultatul se divide cu 25.


Rezultatul nu se mai divide cu 25.


Nici în acest caz rezultatul nu se mai divide cu 25, ca de altfel pentru orice valoare am continua să calculăm.

În cazul lui n=121, spre exemplu, cel mai mic număr prim care divide n este 11. Pentru orice m mai mic ca 11, valoarea formulelor se divide cu 121. Pentru m mai mare sau egal cu 11, valoarea obținută prin formulele de mai sus nu se mai divide cu 121.
Desigur, am dat ca exemple doar pătrate perfecte, dar se poate calcula pentru orice alt număr. Condiția pentru care valoarea obținută prin cele două formule(cu plus și minus 1) nu se mai divide cu n dacă acesta nu este prim,
este ca m (din formulă) să fie mai mare sau egal cu cel mai mic număr prim care divide n.

Această observație este totuși destul de interesantă, poate chiar și importantă, pentru că utilitatea ei practică apare în momentul în care avem nevoie să știm care este cel mai mic număr prim care divide un număr, spre exemplu.