Nel post precedente abbiamo illustrato il metodo di Eratostene per ricavare i numeri primi “setacciandoli” (crivello vuol dire, appunto, setaccio) sull’intero insieme dei numeri naturali. L’algoritmo procede per eliminazione attraverso un raffinato processo di selezione dei multipli.
Per comprendere il motivo del funzionamento del crivello dobbiamo comprendere due importanti punti. Sia N il numero di interi che vogliamo setacciare:
- ad ogni passo, il numero di cui eliminamo i multipli è necessariamente primo
- l’algoritmo termina quando il primo corrente è il più grande intero minore della radice quadrata di N.
Torniamo all’esempio del post scorso, con N=50, e riprendiamo l’algoritmo al passo in cui abbiamo appena eliminato i multipli di 1, 2 e 3:
1 2 3 5 7 11 13 17 19 23 25 29 31 35 37 41 43 47 49
Secondo la nostra prima proposizione, ad ogni passo il candidato successivo, nel caso specifico 5, deve essere necessariamente primo. Ci sono vari modi per dimostrare questo fatto, noi scegliamo di esercitarci con un ferro della nostra borsa del matematico che abbiamo usato tempo addietro, la dimostrazione per assurdo. Sappiamo che, ad ogni passo, i numeri rimasti nel setaccio non sono divisibili per tutti i numeri primi che abbiamo già setacciato.
Nell’esempio concreto, i numeri della griglia non sono divisibili per 1, 2 e 3. Sappiamo, inoltre, che un numero o è primo o è composto, non ci sono terze opzioni. Consideriamo ora il caso generale, per cui il numero corrente sia K e supponiamo per assurdo che K non sia primo. Se K non è primo, vuol dire che è composto e, quindi, possiamo costruirne la scomposizione in fattori (ne abbiamo già parlato):
F(K) = {k1, k2, …., kS}
Nel post precedente abbiamo definito F(K) come quella funzione che restituisce l’elenco dei fattori di K, ordinati, con l’esclusione di 1 e di K stesso. Ad esempio, F(18) = {2, 3, 3}. Nel caso più generale possibile, K ha un numero finito di fattori, diciamo S.
Ora, sappiamo che in questi fattori non possono figurare tutti i numeri primi minori di K, perché li abbiamo eliminati al passo precedente. Sappiamo anche che tra i fattori di K non possono figurare numeri primi maggiori di K. E’ un fatto banale: ad esempio 33 non è divisibile (con divisione intera) per 35.
Ma se tra i fattori di K non figurano i primi minori di K né quelli maggiori di K, l’insieme F(K) è necessariamente vuoto, ovvero K è divisibile solamente per 1 e per sé stesso. Siamo partiti con l’ipotesi che K sia composto e abbiamo ottenuto una contraddizione, perché non esistono numeri composti divisibili solamente per sé stessi e per uno. K è quindi primo.
La seconda proposizione che vogliamo dimostrare è la condizione di arresto dell’algoritmo. Nel caso N=50, l’algoritmo si arresta al numero primo massimo che sia minore della radice quadrata di 50, ovvero 7. Consideriamo il passo generico, dove stiamo eliminando l’i-simo numero primo, che chiamiamo Pi. Il crivello è costruito in modo tale da eliminare, al passo i, tutti gli interi K tali che Pi sia contenuto nel proprio insieme di fattori.
Siccome abbiamo eliminato tutti i fattori precedenti, a Pi, il minimo numero composto nella griglia è dato proprio dal quadrato di Pi. Questo vuol dire che, ad ogni passo, se Pi è il numero primo corrente, tutti i numeri fino a Pi^2 (escluso) contenuti nella griglia sono primi. Osservate la griglia del setaccio sopra, dove Pi = 5: il primo numero non primo contenuto nella griglia è proprio Pi^2.
Insomma, Eratostene ci ha già stupito con la brillante intuizione con cui ha misurato la lunghezza del meridiano e questa dimostrazione è solo un assaggio del suo genio. E il bello è che tutta la scienza è costellata di figure geniali e di idee innovative.
Tutte da scoprire.
