I numeri primi
| I numeri primi fino a 1000 |
|---|
1 2 3 5 7 11 13 17 19 23 29 31 37
41 43 47 53 59 61 67 71 73 79 83 89 97
101 103 107 109 113 127 131 137 139 149 151 157 163
167 173 179 181 191 193 197 199 211 223 227 229 233
239 241 251 257 263 269 271 277 281 283 293 307 311
313 317 331 337 347 349 353 359 367 373 379 383 389
397 401 409 419 421 431 433 439 443 449 457 461 463
467 479 487 491 499 503 509 521 523 541 547 557 563
569 571 577 587 593 599 601 607 613 617 619 631 641
643 647 653 659 661 673 677 683 691 701 709 719 727
733 739 743 751 757 761 769 773 787 797 809 811 821
823 827 829 839 853 857 859 863 877 881 883 887 907
911 919 929 937 941 947 953 967 971 977 983 991 997
|
|
In tal modo i numeri interi positivi vengono a essere divisi in tre insiemi distinti:
a) il numero 1; b) i numeri primi; c) i numeri composti (scomponibili in fattori primi).
|
In matematica l'aggettivo
primo è usato in due accezioni leggermente diverse:
- numero primo [assoluto]: è un numero naturale (intero positivo) N che ha 2 e 2 soli divisori che sono ovviamente 1 ed N stesso; p.es. 2, 3, 5, 7, 11, 13 ...; il numero 1 viene quindi di norma escluso avendo un solo divisore (se stesso).
- numero primo relativamente a un altro numero: due numeri M e N si dicono primi tra di loro se hanno come unico divisore comune 1; detto in altri termini deve essere MCD(M, N) = 1. P.es. 25 in assoluto non è primo, 9 in assoluto non è primo ma 25 e 9 sono primi tra di loro avendo MCD(25, 9) = 1.
Nella tabella a destra sono elencati i numeri primi minori di 1000.
La teoria dei numeri primi nasce intorno al 300AC ad Alessandria con Euclide che negli Elementi riporta alcuni risultati fondamentali:
Pochi anni dopo, sempre ad Alessandria, Eratostene definisce un metodo per trovare la lista di tutti i numeri primi minori di un dato numero N. Questo metodo, noto come il crivello di Eratostene, è tuttora il più efficiente
metodo per generare liste di primi.
Da allora non è che si siano fatti molti progressi nella conoscenza dei numeri primi; i risultati più
importanti furono ottenuti da Eulero, circa 2000 anni dopo Euclide, con la dimostrazione
del
teorema di Eulero-Fermat e l'introduzione della
funzione di Eulero.
Eulero diede inoltre una nuova e sorprendente dimostrazione dell'infinità dei numeri primi, dimostrazione che
un secolo dopo portò Riemann a formulare quella congettura di Riemann che attende ancora oggi una
dimostrazione (o una confutazione).
In definitiva sappiamo ancora molto poco sui numeri primi. In particolare:
- Non si conosce una formula che permetta di generare i numeri primi, p.es. una funzione che ci permetta di calcolare il 1000º numero primo.
- La distribuzione dei numeri primi sembra a prima vista casuale; non sappiamo ancora se sia effettivamente così o se vi sia una qualche regolarità rimasta fino ad ora nascosta.
- Sono frequenti i numeri primi gemelli cioè accoppiati a distanza di 2; le prime coppie sono (5, 7) (11, 13), (17, 19), (29, 31); non sappiamo se la serie dei primi gemelli sia finita o infinita.
- Non si conoscono metodi veloci per stabilire se un numero è primo (test di primalità).
- Non si conoscono metodi veloci per scomporre un numero in fattori primi.
Il fatto di sapere così poco sui numeri primi si è rivelato un vantaggio per i crittologi; oggi quasi tutti i computer usano per comunicare in modo riservato il
cifrario RSA basato appunto sulla difficoltà di scomporre in fattori primi numeri molto grandi (centinaia di cifre decimali).
Se un giorno un matematico dovesse scoprire un metodo per trovare velocemente i fattori primi di un qualsiasi numero, il cifrario RSA perderebbe di colpo tutta la sua sicurezza!
Alcuni ritengono che una chiave del problema sia la
congettura di Riemann; se venisse dimostrata potrebbe aprirsi la strada ad algoritmi veloci per la fattorizzazione di un numero qualsiasi. Ma siamo appunto nel campo delle congetture.
Fonti bibliografiche e collegamenti
