Numeri primi: prime proprietà


I mattoni dell'aritmetica.

Definizione: Un numero naturale, p, é primo se p >1 e se i suoi unici divisori sono 1 e p. Un numero naturale n >1 non primo é detto composto.

Per esempio 2, 3, 5, 7, 11, 13, 17, 19 sono tutti i numeri primi minori o uguali a 20; tutti gli altri (4, 6, 8, 9,..., 20) sono composti.

Si vede così che i numeri naturali sono ripartiti in tre classi: l'unità (=1), i numeri primi, i numeri composti.

colorbar.gif (4491 bytes)

L'importanza dei numeri primi deriva dal fatto che sono i primi mattoni, gli atomi di tutti i numeri: questo segue dal teorema della fattorizzazione unica di ogni numero in prodotto di numeri primi:

Teorema 1: Ogni numero naturale n >1 si esprime in modo unico come un prodotto di numeri primi.

Questo teorema significa la cosa seguente: sia n >1 un numero naturale. Allora n = p1a1.p2a2...pkak dove p1, p2, ..., pk sono dei numeri primi distinti (i.e. pi è diverso da pj se i è diverso da j) e dove a1, a2, ..., ak sono dei numeri naturali >0. Inoltre se n = q1b1.q2b2...qmbm dove q1, q2, ..., qm sono dei numeri primi distinti e dove b1, ..., bm sono dei naturali >0, allora m = k, e (riordinando semmai gli indici) pi = qi e ai = bi per ogni i. Per esempio la decomposizione in fattori primi di 28 é:

28 = 22.7.

La dimostrazione del teorema 1 usa tra altre cose il lemma di Gauss:

Lemma : (Gauss) Sia p un numero primo e a,b dei numeri naturali.Se p divide ab allora p divide a o p divide b.

La dimostrazione del teorema 1 non é facile facile, ma con un pò di sforzi si può seguire. Chi è interessato alla  dimostrazione può cliccare qui.


Quanti numeri primi ?

La prossima domanda che viene naturale é "quanti" numeri primi ci sono ? Se ce ne sono solo un numero finito bisogna farne la lista; se invece l'insieme dei numeri primi é infinito ogni lista sarà sempre incompleta. Cosa ne pensate e perché ?

Come sempre in matematica prima di dimostrare un teorema bisogna cercare di "indovinare" (con degli argomenti magari incompleti ma il più possibile convincenti); anche perché altrimenti non si sa cosa dimostrare!

Il teorema precedente può darci un primo suggerimento: se ci fossero solo un numero finito, diciamo N, di numeri primi: 2 = p1 , 3 = p2 , ..., pN; allora ogni numero naturale sarebbe un prodotto di potenze di p1, p2, ..., pN.

Quest'ultima affermazione (dovrebbe) urta(re) l'intuizione che abbiamo dei numeri naturali e perciò dovremmo cercare di dimostrare che l'insieme dei numeri primi é infinito (infinito significa: non finito). A questo ci aveva già pensato Euclide 23 secoli fa:

 

Teorema : L'insieme dei numeri primi é infinito.

Dim: Si ragiona per assurdo. Supponiamo come sopra che 2 = p1 , 3 = p2 , ..., pN, siano gli unici numeri primi e consideriamo il numero Q = p1.p2...pN + 1. Siccome Q > pN , Q non é primo. Dal lemma 3 però Q é divisibile per un numero primo che dev'essere quindi uno dei numeri p1, p2, ..., pN. Ma questo é impossibile perché: Q/pi = p1.p2..pi-1.pi+1....pN + (1/ pi), che non é un intero.

colorbar.gif (4491 bytes)

Questo teorema é molto potente perché si conoscono solo un numero finito di numeri primi. (Nel 1984 il più grande numero primo noto era 244497-1; é un numero con 13.395 cifre; dopo non mi sono tenuto aggiornato!). Benché questo numero sia molto grande c'é un infinita di numeri più grandi di lui e solo un numero finito di numeri più piccoli! La dimostrazione del fatto che 244497-1 é un numero primo usa in modo essenziale l'uso di un computer ad "alta velocità"; fatta a mano questa dimostrazione richiederebbe più di una vita; il teorema comunque asserisce che esistono numeri primi maggiori di 244497-1.

Il problema é che malgrado diversi tentativi effetuati in questi ultimi 23 secoli, non si dispone di una formula che dia tutti i numeri primi e neanche di una formula che dia solo numeri primi (osservare la differenza).

Per esempio la formula: n2-79n+1601 fornisce numeri primi per n <= 79 ma se n = 80: 802 - 79.80 + 1601 = 1681 = 412. Un'altra formula che dà numeri primi é: n2 - n + 41, per n <= 40 si trovano numeri primi ma se n = 41: 412 - 41 + 41 = 412.

Questo é un fatto generale: non esiste nessun polinomio P(x) tale che P(n) sia un numero primo per ogni numero naturale, n > 0.

Infatti sia P(x) = a0 + a1x + a2x2 + ... + anxn; gli ai sono dei numeri interi positivi, negativi o nulli. Supponiamo P(b) = p, un numero primo. Sia m un numero naturale e guardiamo P(b+mp).

P(b+mp) = a0 + a1(b+mp) + a2(b+mp)2 + ... + an(b+mp)n, sviluppando e tenendo da parte il primo termine di ogni parentesi otteniamo: P(b+mp) = (a0 + a1b + a2b2 + ... + anbn)+ [tanti altri termini, ognuno divisibile per p]. La prima parentesi non é altro che P(b) = p; mettendo p in fattore vediamo che p divide P(b+mp). Quindi P(b+mp) non é primo.

colorbar.gif (4491 bytes)

Il grande matematico P. Fermat  pensava di avere trovato una formula che dava solo numeri primi. Secondo Fermat tutti i numeri Fn = 22n + 1 (n = 0) erano primi. Per i primi valori di n:

F0 = 220 + 1 = 3          F1 = 221 + 1 = 5       F2 = 222 + 1 = 17          F3 = 223 + 1 = 257

F4 = 224 + 1 = 65357

Disgraziatamente: F5 = 225 +1 = 4294967297 é un numero composto (se non avete nient'altro da fare, provate a dividere per 641 o 6700417); invece F3 e F4 sono primi, per verificarlo potete usare il seguente programmino