{"id":2584,"date":"2013-04-03T07:00:20","date_gmt":"2013-04-03T05:00:20","guid":{"rendered":"https:\/\/xmau.com\/wp\/ilpost\/?p=2584"},"modified":"2022-10-11T12:23:40","modified_gmt":"2022-10-11T10:23:40","slug":"euclide-aritmetico","status":"publish","type":"post","link":"https:\/\/xmau.com\/wp\/ilpost\/2013\/04\/03\/euclide-aritmetico\/","title":{"rendered":"Euclide aritmetico"},"content":{"rendered":"

Euclide \u00e8 uno dei pochi matematici il cui nome \u00e8 conosciuto anche da chi la matematica non la pu\u00f2 proprio sopportare: magari non sopporta neppure Euclide stesso, causa tristi ricordi scolastici, ma sa chi \u00e8… il che \u00e8 buffo, se si pensa che in fin dei conti della sua vita se ne sa ben poco<\/a>: gli Elementi<\/em> non hanno indicazione dell’autore, ed \u00e8 solo una singola citazione di Proclo che ci permette di conoscere il nome di chi li ha scritti. Ma c’\u00e8 anche un’altra cosa che se non proprio buffa \u00e8 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<\/em> 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\u00e0 dei numeri primi, e il calcolo del massimo comun divisore tra due numeri.<\/p>\n

Premessa: Euclide non si \u00e8 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 \u00e8 infinita” ma che “un qualunque segmento di retta pu\u00f2 essere prolungato in ciascuna direzione”. Allo stesso modo, il testo greco della Proposizione 20 del Libro IX recita<\/a> \u03bf\u1f31 \u03c0\u03c1\u1ff6\u03c4\u03bf\u03b9 \u1f00\u03c1\u03b9\u03b8\u03bc\u03bf\u1f76 \u03c0\u03bb\u03b5\u03af\u03bf\u03c5\u03c2 \u03b5\u1f30\u03c3\u1f76 \u03c0\u03b1\u03bd\u03c4\u1f78\u03c2 \u03c4\u03bf\u1fe6 \u03c0\u03c1\u03bf\u03c4\u03b5\u03b8\u03ad\u03bd\u03c4\u03bf\u03c2 \u03c0\u03bb\u03ae\u03b8\u03bf\u03c5\u03c2 \u03c0\u03c1\u03ce\u03c4\u03c9\u03bd \u1f00\u03c1\u03b9\u03b8\u03bc\u1ff6\u03bd. A dire il vero, io il greco non lo so mica, e la traduzione di Tartaglia<\/a>, che scrisse \u00abDati quanti numeri primi si uoglia, \u00e8 necessario esser alcuno numero primo da quelli diuerso\u00bb, aiuta poco. Per fortuna lo Heath d\u00e0 anche una traduzione in inglese, e soprattutto tra i miei amici c’\u00e8 una grecista: posso cos\u00ec fornire una traduzione letteralissima che fa \u00abi numeri primi sono pi\u00f9 numerosi di ogni quantit\u00e0 data di numeri primi\u00bb. Una bellissima affermazione finitista, che in italiano corrente si pu\u00f2 rendere come “non pensate di avere trovato tutti i numeri primi, perch\u00e9 ogni volta che voi me ne mostrate un gruppo, io ve ne tiro fuori dal cappello un altro”.<\/p>\n

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\u00f2 essere scritto in un unico modo come prodotto di numeri primi. Prendiamo “una quantit\u00e0 data” di numeri primi p<\/em>1<\/sub>, p<\/em>2<\/sub>, \u2026 p<\/em>n<\/em><\/sub>. Che facciamo ora? Li moltiplichiamo tutti tra loro e aggiungiamo 1, ottenendo un numeraccio N<\/em>. Se questo N<\/em> \u00e8 primo, allora siamo a posto; altrimenti lo scomponiamo in fattori primi. Nessuno di questi fattori primi pu\u00f2 essere uno dei p<\/em>k<\/em><\/sub>; per costruzione infatti dividere N<\/em> per ciascuno di loro d\u00e0 resto 1. Quindi N<\/em> deve avere degli fattori diversi dai p<\/em>k<\/em><\/sub>, e cos\u00ec anche in questo caso abbiamo trovato un numero primo diverso da quelli che avevamo gi\u00e0. Per esempio partendo dall’insieme (2,7,11) otteniamo 155=5×31, mentre con (3,5) abbiamo 16=24<\/sup>. (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).<\/p>\n

Questa dimostrazione \u00e8 considerata da molti (quorum ego) una di quelle del Libro<\/a>: l’elenco delle dimostrazioni “pi\u00f9 belle”, perch\u00e9 i matematici non si accontentano mica di dimostrare un teorema. In mancanza di meglio, tutto fa brodo: per\u00f2 una dimostrazione ottenuta per cos\u00ec 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. \u00c8 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\u00e0 principale dei numeri primi, essere i mattoni a partire dai quali si costruiscano tutti gli altri numeri, proprio per mostrare che non bastano perch\u00e9 con essi si pu\u00f2 costruire un numero “non costruibile”… un po’ come il teorema di indecibilit\u00e0 di G\u00f6del, se mi permettete un paragone molto azzardato.<\/p>\n

\"\"

L'algoritmo di Euclide in forma grafica (da Wikipedia, Euclid's_algorithm_Book_VII_Proposition_2_3.png)<\/p><\/div>\n

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

(\u00c8 il momento di una piccola digressione. Avevo gi\u00e0 scritto che 1 per i greci non \u00e8 un numero, come appunto \u00e8 visibile nella prima chiusa. Avevo per\u00f2 anche un po’ barato quando avevo detto che Euclide ha anche scritto di aritmetica, senza aggiungere che per\u00f2 per lui l’aritmetica derivava comunque dalla geometria, tanto che i due “numeri” sono indicati proprio come noi indichiamo i segmenti<\/strong>: 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)<\/p>\n

La costruzione – Euclide fa sempre matematica costruttiva, se appena gli riesce – non \u00e8 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 \u00e8 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 \u00e8 il nostro MCD cercato. Che l’algoritmo termini \u00e8 ovvio, perch\u00e9 i numeri che usiamo sono sempre pi\u00f9 piccoli; che termini con il massimo comun divisore \u00e8 anche (abbastanza) chiaro, perch\u00e9 se i due numeri iniziali m<\/em> e n<\/em> si fattorizzano come dh<\/em> e dk<\/em> non possiamo mai toglierci dai piedi il fattore d<\/em> con le sottrazioni, e l’ultimo passo ci assicura che non possiamo trovare un divisore maggiore poich\u00e9 non misurerebbe il pi\u00f9 piccolo dei due numeri.<\/p>\n

Cosa c’\u00e8 di importante in questo caso? Che \u00e8 il primo esempio (a me) noto di algoritmo<\/strong>. Ancora una volta, Euclide non l’avrebbe mai chiamato cos\u00ec: a parte che la parola “algoritmo” non sarebbe stata coniata ancora per 1500 anni o gi\u00f9 di l\u00ec, dal suo punto di vista quella era una costruzione proprio come quella per dimostrare il teorema di Pitagora. (L’ho gi\u00e0 scritto, che Euclide fa matematica costruttiva?) Per\u00f2 quello indicato \u00e8 un procedimento che pu\u00f2 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:<\/p>\n

{
\nint r;
\nr = a % b; \/\/ operazione modulo \/\/
\nwhile(r != 0) \/\/ ciclo di iterazione \/\/
\n{
\na = b;
\nb = r;
\nr = a % b;
\n}
\nreturn b;
\n}<\/tt><\/p>\n

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

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\u00e0 scoperto in passato. \u00c8 per\u00f2 chiaro che il suo lavoro \u00e8 stato indispensabile per tramutare la matematica in una macchina da guerra: e non si potr\u00e0 mai non essere grati a chi, da Teone ad Harun al Rashid ad Areta di Cesarea, ha contribuito a preservare la sua opera.<\/p>\n","protected":false},"excerpt":{"rendered":"

Gli Elementi non parlano solo di geometria, ma anche di aritmetica; e anche qua brilla l’esposizione di Euclide. Continue reading →<\/span><\/a><\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_lmt_disableupdate":"","_lmt_disable":"","jetpack_post_was_ever_published":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_memberships_contains_paid_content":false,"activitypub_content_warning":"","activitypub_content_visibility":"","activitypub_max_image_attachments":4,"activitypub_interaction_policy_quote":"anyone","activitypub_status":"","footnotes":"","jetpack_publicize_message":"","jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":true,"jetpack_social_options":{"image_generator_settings":{"template":"highway","default_image_id":0,"font":"","enabled":false},"version":2}},"categories":[1],"tags":[],"class_list":["post-2584","post","type-post","status-publish","format-standard","hentry","category-uncategorized"],"modified_by":".mau.","jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"jetpack_shortlink":"https:\/\/wp.me\/p6hpX6-FG","jetpack-related-posts":[{"id":277,"url":"https:\/\/xmau.com\/wp\/ilpost\/2014\/05\/28\/euclide-e-linfinita-dei-numeri-primi\/","url_meta":{"origin":2584,"position":0},"title":"Euclide e l’infinit\u00e0 dei numeri primi","author":".mau.","date":"28\/05\/2014","format":false,"excerpt":"Non \u00e8 vero che Euclide ha dimostrato che ci sono \"infiniti\" numeri primi, e non \u00e8 nemmeno vero che ha fatto una dimostrazione per assurdo","rel":"","context":"In \"aritmetica\"","block_context":{"text":"aritmetica","link":"https:\/\/xmau.com\/wp\/ilpost\/tag\/aritmetica\/"},"img":{"alt_text":"","src":"","width":0,"height":0},"classes":[]},{"id":404,"url":"https:\/\/xmau.com\/wp\/ilpost\/2010\/10\/08\/il-quinto-postulato-di-euclide\/","url_meta":{"origin":2584,"position":1},"title":"Il quinto postulato di Euclide","author":".mau.","date":"08\/10\/2010","format":false,"excerpt":"Quello delle geometrie non euclidee \u00e8 un tema che non pu\u00f2 mancare in un blog di divulgazione matematica; il difficile \u00e8 riuscire a dire qualcosa di diverso dal solito. Cominciamo a vedere la storia dei tentativi di dimostrazione.","rel":"","context":"In \"geometria\"","block_context":{"text":"geometria","link":"https:\/\/xmau.com\/wp\/ilpost\/tag\/geometria\/"},"img":{"alt_text":"","src":"","width":0,"height":0},"classes":[]},{"id":445,"url":"https:\/\/xmau.com\/wp\/ilpost\/2011\/09\/13\/prima-di-godel\/","url_meta":{"origin":2584,"position":2},"title":"Prima di G\u00f6del…","author":".mau.","date":"13\/09\/2011","format":false,"excerpt":"I teoremi di incompletezza di G\u00f6del hanno segnato la fine della sicurezza che i matematici hanno avuto per 2500 anni. Cosa \u00e8 successo prima che arrivasse lui?","rel":"","context":"In \"logica\"","block_context":{"text":"logica","link":"https:\/\/xmau.com\/wp\/ilpost\/tag\/logica\/"},"img":{"alt_text":"","src":"","width":0,"height":0},"classes":[]},{"id":2356,"url":"https:\/\/xmau.com\/wp\/ilpost\/2010\/11\/19\/gli-assiomi-dimenticati-da-euclide\/","url_meta":{"origin":2584,"position":3},"title":"Gli assiomi dimenticati da Euclide","author":".mau.","date":"19\/11\/2010","format":false,"excerpt":"Dopo aver scoperto la geometria ellittica e quella iperbolica, i matematici hanno anche trovato dei loro modelli nello spazio euclideo, mostrando cos\u00ec come ness. Da l\u00ec si \u00e8 giunti a scoprire come le fondazioni della geometria non erano poi cos\u00ec solide.","rel":"","context":"Similar post","block_context":{"text":"Similar post","link":""},"img":{"alt_text":"rette e no nella geometria ellittica (da Wikipedia)","src":"https:\/\/i0.wp.com\/www.ilpost.it\/wp-content\/uploads\/bloggers\/2010\/11\/ellittica.jpg?resize=350%2C200&ssl=1","width":350,"height":200},"classes":[]},{"id":460,"url":"https:\/\/xmau.com\/wp\/ilpost\/2013\/02\/06\/mersenne-48\/","url_meta":{"origin":2584,"position":4},"title":"Mersenne 48","author":".mau.","date":"06\/02\/2013","format":false,"excerpt":"\u00c8 stato scoperto un nuovo numero primo di Mersenne, o se preferite un nuovo numero perfetto.","rel":"","context":"In \"attualit\u00e0\"","block_context":{"text":"attualit\u00e0","link":"https:\/\/xmau.com\/wp\/ilpost\/tag\/attualita\/"},"img":{"alt_text":"","src":"","width":0,"height":0},"classes":[]},{"id":111,"url":"https:\/\/xmau.com\/wp\/ilpost\/2014\/02\/07\/paura-eh\/","url_meta":{"origin":2584,"position":5},"title":"Paura, eh?","author":".mau.","date":"07\/02\/2014","format":false,"excerpt":"Pretendere che si imparino a memoria le definizioni formali dei concetti matematici \u00e8 assurdo, a meno che non si sia matematici di professione.","rel":"","context":"In \"didattica\"","block_context":{"text":"didattica","link":"https:\/\/xmau.com\/wp\/ilpost\/tag\/didattica\/"},"img":{"alt_text":"","src":"","width":0,"height":0},"classes":[]}],"_links":{"self":[{"href":"https:\/\/xmau.com\/wp\/ilpost\/wp-json\/wp\/v2\/posts\/2584","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/xmau.com\/wp\/ilpost\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/xmau.com\/wp\/ilpost\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/xmau.com\/wp\/ilpost\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/xmau.com\/wp\/ilpost\/wp-json\/wp\/v2\/comments?post=2584"}],"version-history":[{"count":1,"href":"https:\/\/xmau.com\/wp\/ilpost\/wp-json\/wp\/v2\/posts\/2584\/revisions"}],"predecessor-version":[{"id":2585,"href":"https:\/\/xmau.com\/wp\/ilpost\/wp-json\/wp\/v2\/posts\/2584\/revisions\/2585"}],"wp:attachment":[{"href":"https:\/\/xmau.com\/wp\/ilpost\/wp-json\/wp\/v2\/media?parent=2584"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/xmau.com\/wp\/ilpost\/wp-json\/wp\/v2\/categories?post=2584"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/xmau.com\/wp\/ilpost\/wp-json\/wp\/v2\/tags?post=2584"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}