backup del Post

Euclide aritmetico

Euclide è uno dei pochi matematici il cui nome è conosciuto anche da chi la matematica non la può proprio sopportare: magari non sopporta neppure Euclide stesso, causa tristi ricordi scolastici, ma sa chi è… il che è buffo, se si pensa che in fin dei conti della sua vita se ne sa ben poco: gli Elementi non hanno indicazione dell’autore, ed è solo una singola citazione di Proclo che ci permette di conoscere il nome di chi li ha scritti. Ma c’è anche un’altra cosa che se non proprio buffa è comunque interessante da notare. Quasi tutti associano automaticamente a Euclide la geometria (euclidea, appunto), senza sapere che i libri dal VII al X degli Elementi parlano di aritmetica, arrivando fino a una specie di teoria dei numeri irrazionali, usando le tecniche di Eudosso per le approssimazioni con rapporti di numeri interi. Stavolta voglio raccontarvi di due teoremi aritmetici di Euclide, entrambi importantissimi anche se per ragioni diverse: l’infinità dei numeri primi, e il calcolo del massimo comun divisore tra due numeri.

Premessa: Euclide non si è ovviamente mai sognato di dire che i numeri primi fossero infiniti, per l’ottima ragione che il concetto di infinito come ente con cui lavorarci su era una bestemmia per gli antichi greci. Questo si vede dappertutto nella sua opera: non afferma che “la retta è infinita” ma che “un qualunque segmento di retta può essere prolungato in ciascuna direzione”. Allo stesso modo, il testo greco della Proposizione 20 del Libro IX recita οἱ πρῶτοι ἀριθμοὶ πλείους εἰσὶ παντὸς τοῦ προτεθέντος πλήθους πρώτων ἀριθμῶν. A dire il vero, io il greco non lo so mica, e la traduzione di Tartaglia, che scrisse «Dati quanti numeri primi si uoglia, è necessario esser alcuno numero primo da quelli diuerso», aiuta poco. Per fortuna lo Heath dà anche una traduzione in inglese, e soprattutto tra i miei amici c’è una grecista: posso così fornire una traduzione letteralissima che fa «i numeri primi sono più numerosi di ogni quantità data di numeri primi». Una bellissima affermazione finitista, che in italiano corrente si può rendere come “non pensate di avere trovato tutti i numeri primi, perché ogni volta che voi me ne mostrate un gruppo, io ve ne tiro fuori dal cappello un altro”.

E come lo si tira fuori dal cappello? Semplice, una volta che si sa (e naturalmente Euclide l’aveva dimostrato in precedenza) che un numero può essere scritto in un unico modo come prodotto di numeri primi. Prendiamo “una quantità data” di numeri primi p₁, p₂, … p_n. Che facciamo ora? Li moltiplichiamo tutti tra loro e aggiungiamo 1, ottenendo un numeraccio N. Se questo N è primo, allora siamo a posto; altrimenti lo scomponiamo in fattori primi. Nessuno di questi fattori primi può essere uno dei p_k; per costruzione infatti dividere N per ciascuno di loro dà resto 1. Quindi N deve avere degli fattori diversi dai p_k, e così anche in questo caso abbiamo trovato un numero primo diverso da quelli che avevamo già. Per esempio partendo dall’insieme (2,7,11) otteniamo 155=5×31, mentre con (3,5) abbiamo 16=2⁴. (Per la cronaca, ricordo che per i greci 1 non era considerato numero primo per l’ottima ragione che non era nemmeno considerato un numero, ma la base per costruire i numeri).

Questa dimostrazione è considerata da molti (quorum ego) una di quelle del Libro: l’elenco delle dimostrazioni “più belle”, perché i matematici non si accontentano mica di dimostrare un teorema. In mancanza di meglio, tutto fa brodo: però una dimostrazione ottenuta per così dire a martellate e pistola laser serve solo per riempire la casella, un po’ come un numismatico potrebbe accettare nella sua collezione una moneta consunta ma continuerebbe a cercarne una fior di conio. È difficile dare una definizione esplicita di dimostrazione “elegante”, anche se in genere i matematici hanno idee simili al riguardo: in questo caso penso che la bellezza del procedimento euclideo stia nello sfruttare la proprietà principale dei numeri primi, essere i mattoni a partire dai quali si costruiscano tutti gli altri numeri, proprio per mostrare che non bastano perché con essi si può costruire un numero “non costruibile”… un po’ come il teorema di indecibilità di Gödel, se mi permettete un paragone molto azzardato.

Di tutt’altro tipo è la seconda costruzione che vi voglio presentare: quella che ricava il massimo comun divisore (MCD) tra due numeri, vale a dire il numero più grande che è esattamente contenuto in ciascuno dei due numeri dati ( = “dividendo l’uno e l’altro numero per il massimo comun divisore, il resto è sempre zero”). Questa costruzione, nota come algoritmo di Euclide, si trova nelle Proposizioni 1 e 2 del Libro VII: insomma proprio all’inizio della parte matematica. Perché due proposizioni e non una sola, visto che il procedimento è lo stesso nei due casi? Ve l’ho detto sopra. La Proposizione 1 è il caso in cui i due numeri sono primi tra loro, quindi il massimo comun divisore è 1: la traduzione dello Heath (stavolta ve lo lascio in inglese…) termina la Proposizione 1 con «Therefore no number will measure the numbers AB, CD; therefore AB, CD are prime to one another» mentre la Proposizione 2 termina con «Therefore no number which is greater than CF will measure the numbers AB, CD; therefore CF is the greatest common measure of AB, CD.»

(È il momento di una piccola digressione. Avevo già scritto che 1 per i greci non è un numero, come appunto è visibile nella prima chiusa. Avevo però anche un po’ barato quando avevo detto che Euclide ha anche scritto di aritmetica, senza aggiungere che però per lui l’aritmetica derivava comunque dalla geometria, tanto che i due “numeri” sono indicati proprio come noi indichiamo i segmenti: con i due loro estremi. Non per nulla non viene usato il termine “divide”, come facciamo noi, ma “misura”: pensate a quando si misura un muro con un metro da falegname, che viene man mano riportato sulla parete fino ad arrivare in fondo)

La costruzione – Euclide fa sempre matematica costruttiva, se appena gli riesce – non è difficile: ve la mostro con un esempio. Supponiamo di voler trovare il MCD tra 220 e 284. Si inizia a sottrarre il minore dal maggiore fin quando è possibile, senza usare numeri negativi: possiamo farlo solo una volta, 284-220 = 64. Scartiamo ora il maggiore dei valori e facciamo la stessa cosa con il risultato appena ottenuto e il minore dei due valori iniziali: possiamo togliere tre volte il 64 dal 220, e ci rimane 28. Applicando la stessa operazione tra 28 e 64, due sottrazioni ci lasciano 8: tra 8 e 28 tre sottrazioni ci lasciano 4. Ma 4 divide esattamente 8: Euclide afferma allora che 4 è il nostro MCD cercato. Che l’algoritmo termini è ovvio, perché i numeri che usiamo sono sempre più piccoli; che termini con il massimo comun divisore è anche (abbastanza) chiaro, perché se i due numeri iniziali m e n si fattorizzano come dh e dk non possiamo mai toglierci dai piedi il fattore d con le sottrazioni, e l’ultimo passo ci assicura che non possiamo trovare un divisore maggiore poiché non misurerebbe il più piccolo dei due numeri.

Cosa c’è di importante in questo caso? Che è il primo esempio (a me) noto di algoritmo. Ancora una volta, Euclide non l’avrebbe mai chiamato così: a parte che la parola “algoritmo” non sarebbe stata coniata ancora per 1500 anni o giù di lì, dal suo punto di vista quella era una costruzione proprio come quella per dimostrare il teorema di Pitagora. (L’ho già scritto, che Euclide fa matematica costruttiva?) Però quello indicato è un procedimento che può tranquillamente essere riportato pari pari in un computer. Eccovi un esempio, nella versione accelerata che usa una divisione con resto invece che le sottrazioni multiple nei singoli passi:

{
int r;
r = a % b; // operazione modulo //
while(r != 0) // ciclo di iterazione //
{
a = b;
b = r;
r = a % b;
}
return b;
}

Con quella modifica, tra l’altro, l’algoritmo è ancora oggi il più veloce conosciuto: ci sono trucchetti che lo applicano alle rappresentazioni binarie usate dai computer per fare leggermente più in fretta, ma sono appunto minuzie. Wikipedia racconta che nel 1844 Gabriel Lamé dimostrò che l’algoritmo richiede un numero di divisioni pari al più a cinque volte il numero di cifre del più piccolo dei due interi di partenza, inventando nel contempo la teoria della complessità computazionale: se aggiungiamo che tanto per fare un paio di esempi l’algoritmo è alla base della teoria delle frazioni continue e quindi delle approssimazioni come frazione dei numeri, ed è anche il punto chiave dei metodi di crittografia RSA, capirete da soli che non è qualcosa da poco.

Non si sa quali siano i contributi originali di Euclide in matematica, nel senso di nuovi teoremi dimostrati; molti studiosi ritengono che lui abbia principalmente raccolto, ordinato e corretto quanto già scoperto in passato. È però chiaro che il suo lavoro è stato indispensabile per tramutare la matematica in una macchina da guerra: e non si potrà mai non essere grati a chi, da Teone ad Harun al Rashid ad Areta di Cesarea, ha contribuito a preservare la sua opera.