NUMERI PRIMI

I numeri primi sono quei numeri che non hanno divisori, cioè che sono divisibili solo per se stessi e per l’unità.
Ad esempio 105 non è un numero primo perchè  105 = 3x5x7.
I numeri primi compresi tra 1 e 100 sono:
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.
Tranne il numero 2, tutti i numeri primi sono dispari ed inoltre si dimostra che i numeri primi sono infiniti.
La distribuzione dei numeri primi è molto irregolare: vi sono numeri primi separati da un solo numero (come 71 – 73) e vi sono grandi “deserti” privi di numeri primi. Per esempio, tra i numeri primi 9990569 e 9990653 vi è un deserto di 83 numeri non primi, ma vi sono deserti ben più estesi.
Non è mai stata trovata una funzione che generi tutti i numeri primi, ma solo funzioni che generano un numero limitatissimo di numeri primi. Le due più semplici sono:
x^2 – x + 41  che genera 40 numeri primi sostituendo alla x tutti i numeri interi da 1 a 40.
2*x^2 + 29   che genera 28 numeri primi sostituendo alla x tutti i numeri interi da 1 a 28.
Per quanto riguarda il numero p(N) dei numeri primi tra 1 ed N, una buona approssimazione è data dalla formula:
p(N) = N/log(N)
tanto più valida quanto più grande è N.
Un’altra notevole proprietà dei numeri primi è data dal teorema di Wilson:
Chiamiamo F il prodotto di tutti i numeri interi da 1 a (P-1), allora, se P è primo, il resto della divisione di F per P è (P-1).
Una ulteriore proprietà è il “piccolo” Teorema di Fermat:
Se P è un numero primo, allora, per qualsiasi numero A compreso tra 1 e (P-1), il resto della divisione di A^P diviso per P è sempre A, cioè se si prende un qualunque numero A maggiore di 1, lo si moltiplica per se stesso P volte e si sottrae A, il risultato è divisibile per P.
Per esempio scegliamo il numero primo P = 7 e come numero qualsiasi 5. Avremo:
5^7 = 78125
78125 : 7 = 11160 col resto di 5.
I numeri primi possono essere divisi in due grandi famiglie: quelli che, divisi per 4, danno per resto 1 e quelli che, divisi per 4, danno per resto 3. I primi avranno forma generale P = 4n + 1 ed i secondi 4n + 3.
Ebbene i primi sono esprimibili in uno ed un solo modo come somma di due quadrati esatti ed i secondi in nessun modo.
Ad esempio il numero primo 89 è della forma 4n + 1, infatti  89 = 4*22 + 1. Esso è esprimibile in un solo modo come somma di due quadrati esatti, infatti  89 = 5² + 8². Il numero 71 invece è della forma 4n + 3 (71 = 4*17 +3) e non può essere rappresentato in nessun modo come somma di due quadrati esatti.
Da notare che i primi sono fattorizzabili nel campo complesso, per esempio:
89 = (8 + 5i)*(8 – 5i). 89 = (5 + 8i)*(5 – 8i).
Una congettura mai dimostrata, ma verificata anche per numeri enormi, è la cosidetta congettura di Goldbach:
Ogni numero pari è esprimibile come somma di due numeri primi. Ad esempio:
40 = 3 + 37 = 11 + 29 = 3 + 37.