Algoritmo euclideo - Euclidean algorithm

Metodo di Euclide per trovare il massimo comun divisore (MCD) di due lunghezze iniziali BA e DC, entrambe definite come multipli di una lunghezza "unità" comune. Essendo la lunghezza DC più corta, viene utilizzata per "misurare" BA, ma solo una volta perché il resto EA è inferiore a DC. EA ora misura (due volte) la lunghezza inferiore DC, con il resto FC più corto di EA. Quindi FC misura (tre volte) la lunghezza EA. Poiché non c'è resto, il processo termina con FC che è il GCD. A destra l' esempio di Nicomaco con i numeri 49 e 21 risultante nel loro MCD di 7 (derivato da Heath 1908:300).

In matematica , l' algoritmo di Euclide , o algoritmo di Euclide , è un metodo efficiente per calcolare il massimo comun divisore (MCD) di due interi (numeri), il numero più grande che li divide entrambi senza resto . Prende il nome dall'antico matematico greco Euclide , che per primo lo descrisse nei suoi Elementi (c. 300 aC). È un esempio di algoritmo , una procedura passo passo per eseguire un calcolo secondo regole ben definite, ed è uno degli algoritmi più antichi di uso comune. Può essere usato per ridurre le frazioni alla loro forma più semplice e fa parte di molti altri calcoli teorici e crittografici.

L'algoritmo euclideo si basa sul principio che il massimo comun divisore di due numeri non cambia se il numero maggiore viene sostituito dalla sua differenza con il numero minore. Ad esempio, 21 è il MCD di 252 e 105 (come 252 = 21 × 12 e 105 = 21 × 5), e lo stesso numero 21 è anche il MCD di 105 e 252 − 105 = 147. Poiché questa sostituzione riduce il maggiore dei due numeri, ripetendo questo processo si ottengono coppie di numeri successivamente più piccole fino a quando i due numeri diventano uguali. Quando ciò si verifica, sono il MCD dei due numeri originali. Da invertendo le fasi o utilizzando l' algoritmo di Euclide esteso , il GCD può essere espresso come una combinazione lineare dei due numeri originali, che è la somma dei due numeri, ciascuno moltiplicato per un numero intero (ad esempio, 21 = 5 × 105 + (-2) × 252). Il fatto che il GCD possa sempre essere espresso in questo modo è noto come identità di Bézout .

La versione dell'algoritmo euclideo sopra descritta (e da Euclide) può richiedere molti passaggi di sottrazione per trovare il MCD quando uno dei numeri dati è molto più grande dell'altro. Una versione più efficiente dell'algoritmo abbrevia questi passaggi, sostituendo invece il più grande dei due numeri con il suo resto quando viene diviso per il più piccolo dei due (con questa versione, l'algoritmo si ferma quando raggiunge un resto zero). Con questo miglioramento, l'algoritmo non richiede mai più passaggi di cinque volte il numero di cifre (base 10) dell'intero più piccolo. Ciò è stato dimostrato da Gabriel Lamé nel 1844 e segna l'inizio della teoria della complessità computazionale . Nel XX secolo sono stati sviluppati ulteriori metodi per migliorare l'efficienza dell'algoritmo.

L'algoritmo euclideo ha molte applicazioni teoriche e pratiche. Viene utilizzato per ridurre le frazioni alla loro forma più semplice e per eseguire divisioni in aritmetica modulare . I calcoli che utilizzano questo algoritmo fanno parte dei protocolli crittografici utilizzati per proteggere le comunicazioni Internet e nei metodi per violare questi sistemi crittografici fattorizzando grandi numeri composti . L'algoritmo euclideo può essere utilizzato per risolvere equazioni diofantee , come trovare numeri che soddisfano congruenze multiple secondo il teorema cinese dei resti , per costruire frazioni continue e per trovare approssimazioni razionali accurate ai numeri reali. Infine, può essere utilizzato come strumento di base per dimostrare teoremi nella teoria dei numeri come il teorema dei quattro quadrati di Lagrange e l' unicità delle scomposizioni in fattori primi . L'algoritmo originale è stato descritto solo per i numeri naturali e le lunghezze geometriche (numeri reali), ma l'algoritmo è stato generalizzato nel XIX secolo ad altri tipi di numeri, come interi gaussiani e polinomi di una variabile. Ciò ha portato a moderne nozioni algebriche astratte come i domini euclidei .

Contesto: massimo comun divisore

L'algoritmo euclideo calcola il massimo comun divisore (MCD) di due numeri naturali a e b . Il massimo comun divisore g è il più grande numero naturale che divide sia a che b senza lasciare resto. I sinonimi per il MCD includono il massimo comun divisore (GCF), il massimo comun divisore (HCF), il massimo comun divisore (HCD) e la massima misura comune (GCM). Il massimo comun divisore è spesso scritto come gcd ( ab ) o, più semplicemente, come ( ab ), anche se quest'ultimo notazione è ambiguo, utilizzato anche per concetti come un ideale in anello degli interi , che è strettamente relativo a GCD.

Se mcd( ab ) = 1, allora a e b si dicono coprimi (o relativamente primi). Questa struttura non implica che una o b sono essi stessi numeri primi . Ad esempio, né 6 né 35 sono numeri primi, poiché entrambi hanno due fattori primi: 6 = 2 × 3 e 35 = 5 × 7. Tuttavia, 6 e 35 sono coprimi. Nessun numero naturale diverso da 1 divide sia 6 che 35, poiché non hanno fattori primi in comune.

"Rettangolo alto e snello diviso in una griglia di quadrati. Il rettangolo è largo due quadrati e alto cinque".
Un rettangolo 24x60 è coperto con dieci tessere quadrate 12x12, dove 12 è il MCD di 24 e 60. Più in generale, un rettangolo a -by- b può essere ricoperto con tessere quadrate di lato c solo se c è un divisore comune di a e b .

Sia g = mcd( ab ). Poiché a e b sono entrambi multipli di g , possono essere scritti a  =  mg e b  =  ng , e non esiste un numero più grande G  >  g per cui questo è vero. I numeri naturali m e n devono essere coprimi, poiché qualsiasi fattore comune potrebbe essere scomposto da m e n per rendere g maggiore. Quindi, qualsiasi altro numero c che divide sia a che b deve dividere anche g . Il massimo comun divisore g di un e b è l'unico (positivo) comun divisore di un e b che è divisibile per qualsiasi altra comun divisore c .

Il GCD può essere visualizzato come segue. Considera un'area rettangolare a per b e qualsiasi divisore comune c che divide esattamente sia a che b . I lati del rettangolo possono essere divisi in segmenti di lunghezza c , che divide il rettangolo in una griglia di quadrati di lunghezza c . Il massimo comun divisore g è il più grande valore di c per cui ciò è possibile. A titolo illustrativo, un'area rettangolare di 24 per 60 può essere divisa in una griglia di: quadrati 1 per 1, quadrati 2 per 2, quadrati 3 per 3, quadrati 4 per 4, quadrati 6 per -6 quadrati o 12 per 12 quadrati. Pertanto, 12 è il massimo comun divisore di 24 e 60. Un'area rettangolare di 24 per 60 può essere divisa in una griglia di quadrati 12 per 12, con due quadrati lungo un bordo (24/12 = 2) e cinque quadrati lungo l'altro (60/12 = 5).

Il MCD di due numeri a e b è il prodotto dei fattori primi condivisi dai due numeri, in cui uno stesso fattore primo può essere utilizzato più volte, ma solo fino a quando il prodotto di questi fattori divide sia un e b . Ad esempio, poiché 1386 può essere scomposto in 2 × 3 × 3 × 7 × 11, e 3213 può essere scomposto in 3 × 3 × 3 × 7 × 17, il massimo comun divisore di 1386 e 3213 è uguale a 63 = 3 × 3 × 7, il prodotto dei loro fattori primi condivisi. Se due numeri non hanno fattori primi in comune, il loro massimo comun divisore è 1 (ottenuto qui come istanza del prodotto vuoto ), in altre parole sono coprimi. Un vantaggio chiave dell'algoritmo euclideo è che può trovare il GCD in modo efficiente senza dover calcolare i fattori primi. Si ritiene che la fattorizzazione di grandi numeri interi sia un problema computazionalmente molto difficile e la sicurezza di molti protocolli crittografici ampiamente utilizzati si basa sulla sua irrealizzabilità.

Un'altra definizione del GCD è utile nella matematica avanzata, in particolare nella teoria degli anelli . Il massimo comun divisore g   di due numeri non nulli a e b è anche la più piccola combinazione lineare intero positivo, cioè, il numero positivo più piccolo della forma ua  +  vb dove u e v sono numeri interi. L'insieme di tutte le combinazioni lineari integrali di un e b è in realtà lo stesso come l'insieme di tutti i multipli di g ( mg , dove m è un numero intero). Nel moderno linguaggio matematico, l' ideale generato da un e b è l'ideale generato da  g sola (un ideale generato da un singolo elemento è chiamato un ideale principale , e tutti gli ideali degli interi sono ideali principali). Alcune proprietà del GCD sono infatti più facili da vedere con questa descrizione, per esempio il fatto che qualsiasi comune divisore di un e b divide inoltre il MCD (divide entrambi i termini di UC  +  vb ). L'equivalenza di questa definizione GCD con le altre definizioni è descritta di seguito.

Il MCD di tre o più numeri è uguale al prodotto dei fattori primi comuni a tutti i numeri, ma può anche essere calcolato prendendo ripetutamente il MCD di coppie di numeri. Per esempio,

mcd( abc ) = mcd( a , mcd( bc )) = mcd(gcd( ab ),  c ) = mcd(mcd( ac ),  b ).

Pertanto, l'algoritmo di Euclide, che calcola il MCD di due interi, è sufficiente per calcolare il MCD di un numero arbitrario di interi.

Descrizione

Procedura

L'algoritmo euclideo procede in una serie di passaggi in modo tale che l'output di ogni passaggio venga utilizzato come input per quello successivo. Sia k un intero che conta i passi dell'algoritmo, partendo da zero. Pertanto, il passaggio iniziale corrisponde a k  = 0, il passaggio successivo corrisponde a k  = 1 e così via.

Ogni passo inizia con due resti non negativi r k −1 e r k −2 . Poiché l'algoritmo assicura che i resti diminuiscano costantemente ad ogni passo, r k −1 è minore del suo predecessore r k −2 . L'obiettivo del k- esimo passo è trovare un quoziente q k e un resto r k che soddisfino l'equazione

e che hanno 0 ≤ r k  <  r k −1 . In altre parole, i multipli del numero più piccolo r k −1 sono sottratti dal numero più grande r k −2 finché il resto r k è minore di r k −1 .

Nella fase iniziale ( k  = 0), i resti r -2 e r -1 sono uguali a a e b , i numeri per i quali si cerca il MCD. Nel passaggio successivo ( k  = 1), i resti sono uguali a b e il resto r 0 del passaggio iniziale, e così via. Pertanto, l'algoritmo può essere scritto come una sequenza di equazioni

Se a è minore di b , il primo passo dell'algoritmo scambia i numeri. Ad esempio, se a  <  b , il quoziente iniziale q 0 è uguale a zero e il resto r 0 è a . Pertanto, r k è più piccolo del suo predecessore r k −1 per ogni k  ≥ 0.

Poiché i resti decrescono ad ogni passo ma non possono mai essere negativi, un resto r N deve eventualmente essere uguale a zero, a quel punto l'algoritmo si ferma. Il resto finale non nullo r N −1 è il massimo comun divisore di a e b . Il numero N non può essere infinito perché c'è solo un numero finito di interi non negativi tra il resto iniziale r 0 e zero.

Prova di validità

La validità dell'algoritmo euclideo può essere dimostrata da un argomento in due fasi. Nella prima fase, si mostra che il resto finale diverso da zero r N −1 divide sia a che b . Poiché è un comun divisore, deve essere minore o uguale al massimo comun divisore g . Nella seconda fase, si mostra che qualsiasi divisore comune di a e b , incluso g , deve dividere r N −1 ; quindi, g deve essere minore o uguale a r N −1 . Queste due conclusioni sono incoerenti a meno che r N −1  =  g .

Per dimostrare che r N −1 divide sia a che b (il primo passo), r N −1 divide il suo predecessore r N −2

r N −2 = q N r N −1

poiché il resto finale r N è zero. r N −1 divide anche il suo predecessore successivo r N −3

r N −3 = q N −1 r N −2 + r N −1

perché divide entrambi i termini sul lato destro dell'equazione. Iterando lo stesso argomento, r N −1 divide tutti i resti precedenti, inclusi a e b . Nessuno dei resti precedenti r N -2 , r N -3 , ecc dividere un e b , poiché lasciano un residuo. Poiché r N −1 è un divisore comune di a e b , r N −1  ≤  g .

Nella seconda fase, qualsiasi numero naturale c che divide sia un e b (in altre parole, qualsiasi comun divisore di un e b ) divide i resti r k . Per definizione, a e b possono essere scritti come multipli di c  : a  =  mc e b  =  nc , dove m e n sono numeri naturali. Pertanto, c divide il resto iniziale r 0 , poiché r 0  =  a  −  q 0 b  =  mc  −  q 0 nc  = ( m  −  q 0 n ) c . Un argomento analogo mostra che c divide anche i successivi resti r 1 , r 2 , ecc. Pertanto, il massimo comun divisore g deve dividere r N −1 , il che implica che g  ≤  r N −1 . Poiché la prima parte dell'argomento mostrava il contrario ( r N −1  ≤  g ), ne consegue che g  =  r N −1 . Quindi, g è il massimo comun divisore di tutte le coppie successive:

g = mcd( a , b ) = mcd( b , r 0 ) = mcd( r 0 , r 1 ) = … = mcd( r N −2 , r N −1 ) = r N −1 .

Esempio funzionante

Animazione in cui vengono aggiunte tessere quadrate progressivamente più piccole per coprire completamente un rettangolo.
Animazione basata sulla sottrazione dell'algoritmo euclideo. Il rettangolo iniziale ha dimensioni a  = 1071 eb  = 462. I quadrati di dimensione 462×462 vengono posizionati al suo interno lasciando un rettangolo di 462×147. Questo rettangolo viene piastrellato con 147×147 quadrati fino a quando non rimane un rettangolo 21×147, che a sua volta viene piastrellato con 21×21 quadrati, senza lasciare alcuna area scoperta. La dimensione quadrata più piccola, 21, è il GCD di 1071 e 462.

A titolo illustrativo, l'algoritmo euclideo può essere utilizzato per trovare il massimo comun divisore di a  = 1071 e b  = 462. Per iniziare, i multipli di 462 vengono sottratti da 1071 fino a quando il resto è inferiore a 462. Due di questi multipli possono essere sottratti ( q 0  = 2), lasciando un resto di 147:

1071 = 2 × 462 + 147.

Quindi i multipli di 147 vengono sottratti da 462 fino a quando il resto è inferiore a 147. Si possono sottrarre tre multipli ( q 1  = 3), lasciando un resto di 21:

462 = 3 × 147 + 21.

Quindi i multipli di 21 vengono sottratti da 147 fino a quando il resto non è inferiore a 21. Si possono sottrarre sette multipli ( q 2  = 7), senza lasciare resto:

147 = 7 × 21 + 0.

Poiché l'ultimo resto è zero, l'algoritmo termina con 21 come massimo comun divisore di 1071 e 462. Ciò concorda con il mcd (1071, 462) trovato dalla scomposizione in fattori primi sopra . In forma tabellare, i passaggi sono:

passo k Equazione Quoziente e resto
0 1071 = q 0 462 + r 0 q 0 = 2 e r 0 = 147
1 462 = q 1 147 + r 1 q 1 = 3 e r 1 = 21
2 147 = q 2 21 + r 2 q 2 = 7 e r 2 = 0 ; l'algoritmo finisce

Visualizzazione

L'algoritmo euclideo può essere visualizzato nei termini dell'analogia di piastrellatura data sopra per il massimo comun divisore. Supponiamo di voler coprire esattamente un rettangolo a -by- b con tessere quadrate, dove a è il più grande dei due numeri. Per prima cosa proviamo ad affiancare il rettangolo usando b -by- b tessere quadrate; tuttavia, questo lascia un rettangolo residuo r 0 -by- b fino, dove r 0  <  b . Quindi tentiamo di affiancare il rettangolo residuo con r 0 -by- r 0 tessere quadrate. Questo lascia un secondo rettangolo residuo r 1 -by- r 0 , che tentiamo di affiancare usando r 1 -by- r 1 tessere quadrate, e così via. La sequenza termina quando non c'è un rettangolo residuo, cioè quando le tessere quadrate coprono esattamente il rettangolo residuo precedente. La lunghezza dei lati della piastrella quadrata più piccola è il MCD delle dimensioni del rettangolo originale. Ad esempio, la tessera quadrata più piccola nella figura adiacente è 21 per 21 (mostrata in rosso) e 21 è il GCD di 1071 e 462, le dimensioni del rettangolo originale (mostrato in verde).

divisione euclidea

Ad ogni passo k , l'algoritmo euclideo calcola un quoziente q k e resto r k da due numeri r k −1 e r k −2

r k −2 = q k r k −1 + r k

dove r k è non negativo ed è strettamente minore del valore assoluto di r k −1 . Il teorema che sta alla base della definizione della divisione euclidea assicura che tale quoziente e resto esistano sempre e siano unici.

Nella versione originale dell'algoritmo di Euclide, il quoziente e il resto si trovano per sottrazione ripetuta; cioè, r k −1 viene sottratto da r k −2 ripetutamente finché il resto r k è minore di r k −1 . Dopodiché vengono scambiati r k e r k −1 e il processo viene iterato. La divisione euclidea riduce tutti i passaggi tra due scambi in un unico passaggio, che è quindi più efficiente. Inoltre, i quozienti non sono necessari, quindi si può sostituire la divisione euclidea con l' operazione modulo , che dà solo il resto. Quindi l'iterazione dell'algoritmo euclideo diventa semplicemente

r k = r k −2 mod r k −1 .

implementazioni

Le implementazioni dell'algoritmo possono essere espresse in pseudocodice . Ad esempio, la versione basata sulla divisione può essere programmata come

function gcd(a, b)
    while b ≠ 0
        t := b
        b := a mod b
        a := t
    return a

All'inizio della k- esima iterazione, la variabile b contiene l'ultimo resto r k −1 , mentre la variabile a contiene il suo predecessore, r k −2 . Il passo b  := a mod b è equivalente alla formula di ricorsione precedente r kr k −2 mod r k −1 . La variabile temporanea t contiene il valore di r k −1 mentre viene calcolato il prossimo resto r k . Alla fine dell'iterazione del ciclo, la variabile b contiene il resto r k , mentre la variabile a mantiene il suo predecessore, r k −1 .

(Se sono consentiti input negativi, o se la funzione mod può restituire valori negativi, l'ultima riga deve essere modificata in return max (a, -a).)

Nella versione basata sulla sottrazione, che era la versione originale di Euclide, il calcolo del resto ( ) è sostituito da una sottrazione ripetuta. Contrariamente alla versione basata sulla divisione, che funziona con numeri interi arbitrari come input, la versione basata sulla sottrazione suppone che l'input sia costituito da numeri interi positivi e si fermi quando a = b : b := a mod b

function gcd(a, b)
    while a ≠ b 
        if a > b
            a := a − b
        else
            b := b − a
    return a

Le variabili una e b alternate tiene i resti precedenti r k -1 e r k -2 . Supponiamo che a sia maggiore di b all'inizio di un'iterazione; allora a è uguale a r k −2 , poiché r k −2 > r k −1 . Durante l'iterazione del ciclo, a viene ridotto di multipli del precedente resto b finché a non è minore di b . Allora a è il prossimo resto r k . Quindi b viene ridotto di multipli di a finché non è di nuovo minore di a , dando il resto successivo r k +1 , e così via.

La versione ricorsiva si basa sull'uguaglianza dei MCD dei resti successivi e sulla condizione di arresto gcd( r N −1 , 0) =  r N −1 .

function gcd(a, b)
    if b = 0
        return a
    else
        return gcd(b, a mod b)

(Come sopra, se sono consentiti input negativi, o se la funzione mod può restituire valori negativi, l'istruzione " return a" deve essere cambiata in " return max (a, -a)".)

A titolo illustrativo, il mcd(1071, 462) viene calcolato dall'equivalente mcd(462, 1071 mod 462) = mcd(462, 147). Quest'ultimo MCD è calcolato da mcd(147, 462 mod 147) = mcd(147, 21), che a sua volta viene calcolato da mcd(21, 147 mod 21) = mcd(21, 0) = 21.

Metodo dei minimi assoluti

In un'altra versione dell'algoritmo di Euclide, il quoziente ad ogni passo viene aumentato di uno se il resto negativo risultante è di grandezza inferiore al tipico resto positivo. In precedenza, l'equazione

r k −2 = q k r k −1 + r k

ipotizzato che | r k -1 | >  R k  > 0 . Tuttavia, un resto negativo alternativo e k può essere calcolato:

r k −2 = ( q k + 1) r k −1 + e k

se r k −1  > 0 o

r k −2 = ( q k − 1) r k −1 + e k

se r k −1  < 0 .

Se r k è sostituito da e k . quando | e k | < | r k | , allora si ottiene una variante dell'algoritmo euclideo tale che

| r k | | r k -1 | / 2

ad ogni passo.

Leopold Kronecker ha dimostrato che questa versione richiede il minor numero di passaggi di qualsiasi versione dell'algoritmo di Euclide. Più in generale, è stato dimostrato che, per ogni numeri di ingresso da e b , il numero di passi è minimo se e solo se q k viene scelto in modo che quando è il rapporto aureo .

Sviluppo storico

"Rappresentazione di Euclide come un uomo barbuto che tiene un paio di divisori su una tavoletta."
L'algoritmo euclideo fu probabilmente inventato prima di Euclide , qui raffigurato con in mano un compasso in un dipinto del 1474 circa.

L'algoritmo euclideo è uno dei più antichi algoritmi di uso comune. Appare negli Elementi di Euclide (c. 300 aC), in particolare nel Libro 7 (Proposizioni 1-2) e nel Libro 10 (Proposizioni 2-3). Nel Libro 7, l'algoritmo è formulato per i numeri interi, mentre nel Libro 10, è formulato per le lunghezze dei segmenti di linea. (Nell'uso moderno, si direbbe che sia stato formulato lì per numeri reali . Ma lunghezze, aree e volumi, rappresentati come numeri reali nell'uso moderno, non sono misurati nelle stesse unità e non esiste un'unità naturale di lunghezza, area, o volume; il concetto di numeri reali era sconosciuto a quel tempo.) Quest'ultimo algoritmo è geometrico. Il MCD di due lunghezze a e b corrispondente alla massima lunghezza g che le misure a e b uniformemente; in altre parole, le lunghezze una e b sono entrambi multipli interi della lunghezza g .

L'algoritmo probabilmente non è stato scoperto da Euclide , che ha compilato i risultati di matematici precedenti nei suoi Elementi . Il matematico e storico BL van der Waerden suggerisce che il libro VII derivi da un libro di testo sulla teoria dei numeri scritto da matematici della scuola di Pitagora . L'algoritmo era probabilmente conosciuto da Eudosso di Cnido (circa 375 aC). L'algoritmo potrebbe anche essere antecedente a Eudosso, a giudicare dall'uso del termine tecnico ἀνθυφαίρεσις ( antiphairesis , sottrazione reciproca) in opere di Euclide e Aristotele .

Secoli dopo, l'algoritmo di Euclide fu scoperto indipendentemente sia in India che in Cina, principalmente per risolvere equazioni diofantee sorte in astronomia e per creare calendari accurati. Alla fine del V secolo, il matematico e astronomo indiano Aryabhata descrisse l'algoritmo come il "polverizzatore", forse a causa della sua efficacia nel risolvere le equazioni diofantee. Sebbene un caso speciale del teorema cinese dei resti fosse già stato descritto nel libro cinese Sunzi Suanjing , la soluzione generale fu pubblicata da Qin Jiushao nel suo libro del 1247 Shushu Jiuzhang (數書九章Trattato matematico in nove sezioni ). L'algoritmo euclideo fu descritto per la prima volta numericamente e reso popolare in Europa nella seconda edizione dei Problèmes plaisants et délectables di Bachet ( Problemi piacevoli e divertenti , 1624). In Europa, è stato utilizzato anche per risolvere equazioni diofantee e nello sviluppo di frazioni continue . L' algoritmo euclideo esteso fu pubblicato dal matematico inglese Nicholas Saunderson , che lo attribuì a Roger Cotes come metodo per calcolare in modo efficiente le frazioni continue.

Nel XIX secolo, l'algoritmo euclideo portò allo sviluppo di nuovi sistemi numerici, come gli interi gaussiani e gli interi di Eisenstein . Nel 1815, Carl Gauss utilizzò l'algoritmo euclideo per dimostrare la fattorizzazione unica degli interi gaussiani , sebbene il suo lavoro fu pubblicato per la prima volta nel 1832. Gauss menzionò l'algoritmo nelle sue Disquisitiones Arithmeticae (pubblicate nel 1801), ma solo come metodo per le frazioni continue . Peter Gustav Lejeune Dirichlet sembra essere stato il primo a descrivere l'algoritmo euclideo come base per gran parte della teoria dei numeri. Lejeune Dirichlet ha notato che molti risultati della teoria dei numeri, come la fattorizzazione unica, sarebbero validi per qualsiasi altro sistema di numeri a cui l'algoritmo euclideo potesse essere applicato. Le lezioni di Lejeune Dirichlet sulla teoria dei numeri sono state curate e ampliate da Richard Dedekind , che ha utilizzato l'algoritmo di Euclide per studiare gli interi algebrici , un nuovo tipo generale di numero. Ad esempio, Dedekind fu il primo a dimostrare il teorema dei due quadrati di Fermat usando la fattorizzazione unica degli interi gaussiani. Dedekind ha anche definito il concetto di dominio euclideo , un sistema numerico in cui può essere definita una versione generalizzata dell'algoritmo euclideo (come descritto di seguito ). Negli ultimi decenni del XIX secolo, l'algoritmo euclideo venne gradualmente eclissato dalla teoria più generale degli ideali di Dedekind .

"[L'algoritmo euclideo] è il capostipite di tutti gli algoritmi, perché è il più antico algoritmo non banale sopravvissuto fino ai giorni nostri".

Donald Knuth , L'arte della programmazione informatica, vol. 2: Algoritmi seminumerici , 2a edizione (1981), p. 318.

Altre applicazioni dell'algoritmo di Euclide furono sviluppate nel XIX secolo. Nel 1829, Charles Sturm dimostrò che l'algoritmo era utile nel metodo della catena di Sturm per contare le radici reali dei polinomi in un dato intervallo.

L'algoritmo euclideo è stato il primo algoritmo di relazione intera , che è un metodo per trovare relazioni intere tra numeri reali commisurati. Sono stati sviluppati diversi nuovi algoritmi di relazione intera , come l'algoritmo di Helaman Ferguson e RW Forcade (1979) e l' algoritmo LLL .

Nel 1969, Cole e Davie hanno sviluppato un gioco a due giocatori basato sull'algoritmo euclideo, chiamato The Game of Euclid , che ha una strategia ottimale. I giocatori iniziano con due pile di pietre a e b . I giocatori, a turno, rimuovono m multipli della pila più piccola dalla più grande. Quindi, se le due pile sono costituite da x e y pietre, dove x è maggiore di y , il giocatore successivo può ridurre la pila più grande da x pietre a x − le mie pietre, purché quest'ultima sia un numero intero non negativo. Il vincitore è il primo giocatore che riduce una pila a zero pietre.

Applicazioni matematiche

L'identità di Bézout

L'identità di Bézout afferma che il massimo comun divisore g di due interi a e b può essere rappresentato come una somma lineare dei due numeri originari a e b . In altre parole, è sempre possibile trovare interi s e t tali che g  =  sa  +  tb .

Gli interi s e t possono essere calcolati dai quozienti q 0 , q 1 , ecc. invertendo l'ordine delle equazioni nell'algoritmo di Euclide. A partire dalla penultima equazione, g può essere espresso in termini del quoziente q N −1 e dei due resti precedenti, r N −2 e r N −3 :

g = r N −1 = r N −3q N −1 r N −2  .

Questi due resti possono essere espressi anche in termini dei loro quozienti e resti precedenti,

r N −2 = r N −4q N −2 r N −3 e
r N −3 = r N −5q N −3 r N −4  .

Sostituendo queste formule per r N -2 e r N -3 nella prima equazione si ottiene g come somma lineare dei resti r N -4 e r N -5 . Il processo di sostituzione dei resti con formule che coinvolgono i loro predecessori può essere continuato fino a raggiungere i numeri originali a e b :

r 2 = r 0q 2 r 1
r 1 = bq 1 r 0
r 0 = aq 0 b .

Dopo che tutti i resti r 0 , r 1 , ecc. sono stati sostituiti, l'equazione finale esprime g come somma lineare di a e b : g  =  sa  +  tb . L'identità di Bézout , e quindi l'algoritmo precedente, possono essere entrambi generalizzati al contesto dei domini euclidei .

Principali ideali e problemi correlati

L'identità di Bézout fornisce ancora un'altra definizione del massimo comun divisore g di due numeri a e b . Considera l'insieme di tutti i numeri ua  +  vb , dove u e v sono due interi qualsiasi. Poiché un e b sono entrambi divisibili per g , ogni numero dell'insieme è divisibile per g . In altre parole, ogni numero dell'insieme è un multiplo intero di g . Questo è vero per ogni comun divisore di a e b . Tuttavia, a differenza di altri comun divisori, il massimo comun divisore è un membro dell'insieme; per l'identità di Bézout, scegliendo u  =  s e v  =  t si ottiene g . Un divisore comune più piccolo non può essere un membro dell'insieme, poiché ogni membro dell'insieme deve essere divisibile per g . Viceversa, qualsiasi multiplo m di g può essere ottenuto scegliendo u  =  ms e v  =  mt , dove s e t sono gli interi dell'identità di Bézout. Questo può essere visto moltiplicando l'identità di Bézout per m ,

mg = msa + mtb .

Pertanto, l'insieme di tutti i numeri ua  +  vb è equivalente all'insieme dei multipli m di g . In altre parole, l'insieme di tutte le possibili somme di multipli interi di due numeri ( un e b ) è equivalente all'insieme di multipli di gcd ( a , b ). Si dice che il MCD è il generatore dell'ideale di a e b . Questa definizione GCD ha portato ai moderni concetti algebrici astratti di un ideale principale (un ideale generato da un singolo elemento) e un dominio ideale principale (un dominio in cui ogni ideale è un ideale principale).

Alcuni problemi possono essere risolti utilizzando questo risultato. Ad esempio, considera due misurini di volume a e b . Sommando/sottraendo u multipli della prima tazza e v multipli della seconda tazza, è possibile misurare qualsiasi volume ua  +  vb . Questi volumi sono tutti multipli di g  = mcd( ab ).

Algoritmo euclideo esteso

Gli interi s e t dell'identità di Bézout possono essere calcolati in modo efficiente utilizzando l' algoritmo euclideo esteso . Questa estensione aggiunge due equazioni ricorsive all'algoritmo di Euclide

s k = s k −2q k s k −1
t k = t k −2q k t k −1

con i valori di partenza

s −2 = 1, t −2 = 0
s −1 = 0, t −1 = 1.

Usando questa ricorsione, gli interi di Bézout s e t sono dati da s  =  s N e t  =  t N , dove N+1 è il passo su cui l'algoritmo termina con r N+1  = 0.

La validità di questo approccio può essere dimostrata per induzione. Supponiamo che la formula di ricorsione sia corretta fino al passo k  − 1 dell'algoritmo; in altre parole, supponiamo che

r j = s j a + t j b

per tutti j minori di k . Il k- esimo passo dell'algoritmo dà l'equazione

r k = r k −2q k r k −1 .

Poiché la formula di ricorsione è stata assunta corretta per r k −2 e r k −1 , possono essere espressi in termini delle corrispondenti variabili s e t

r k = ( s k −2 a + t k −2 b ) − q k ( s k −1 a + t k −1 b ).

Riorganizzando questa equazione si ottiene la formula di ricorsione per il passaggio k , come richiesto

r k = s k a + t k b = ( s k −2q k s k −1 ) a + ( t k −2q k t k −1 ) b .

Metodo della matrice

Gli interi s e t possono essere trovati anche utilizzando un metodo matriciale equivalente . La sequenza delle equazioni dell'algoritmo di Euclide

può essere scritto come prodotto di matrici quoziente 2 per 2 moltiplicando un vettore di resto bidimensionale

Sia M il prodotto di tutte le matrici quoziente

Questo semplifica l'algoritmo euclideo nella forma

Per esprimere g come somma lineare di un e b , entrambi i lati di questa equazione può essere moltiplicati per l'inversa della matrice M . Il determinante di M è uguale a (−1) N +1 , poiché è uguale al prodotto dei determinanti delle matrici quoziente, ciascuna delle quali è negativa. Poiché il determinante di M non è mai zero, il vettore dei resti finali può essere risolto usando l'inverso di M

Poiché l'equazione superiore dà

g = (−1) N +1 ( m 22 am 12 b ),

due interi di identità di bézout sono s  = (-1) N +1 m 22 e t  = (-1) N m 12 . Il metodo della matrice è efficiente quanto la ricorsione equivalente, con due moltiplicazioni e due addizioni per passo dell'algoritmo euclideo.

Lemma di Euclide e fattorizzazione unica

L'identità di Bézout è essenziale per molte applicazioni dell'algoritmo di Euclide, come la dimostrazione della fattorizzazione unica dei numeri in fattori primi. Per illustrare ciò, supponiamo che un numero L possa essere scritto come prodotto di due fattori u e v , cioè L  =  uv . Se anche un altro numero w divide L ma è coprimo con u , allora w deve dividere v , con il seguente argomento: Se il massimo comun divisore di u e w è 1, allora gli interi s e t possono essere trovati tali che

1 = su + tw  .

dall'identità di Bézout. Moltiplicando entrambi i membri per v dà la relazione

v = suv + twv = sL + twv  .

Poiché w divide entrambi i termini a destra, deve dividere anche a sinistra, v . Questo risultato è noto come lemma di Euclide . In particolare, se un numero primo divide L , allora deve dividere almeno un fattore di L . Viceversa, se un numero w è coprimo a ciascuno di una serie di numeri a 1 , a 2 , ..., a n , allora w è anche coprimo al loro prodotto, a 1  ×  a 2  × ... ×  a n .

Il lemma di Euclide è sufficiente a dimostrare che ogni numero ha un'unica fattorizzazione in numeri primi. Per vedere ciò, supponiamo il contrario, che ci siano due fattorizzazioni indipendenti di L in m ed n fattori primi, rispettivamente

L = p 1 p 2p m = q 1 q 2q n  .

Poiché ogni primo p divide L per ipotesi, deve dividere anche uno dei fattori q ; poiché anche ogni q è primo, deve essere che p  =  q . La divisione iterativa per i fattori p mostra che ogni p ha una controparte uguale q ; le due fattorizzazioni prime sono identiche tranne che per il loro ordine. La fattorizzazione unica dei numeri in numeri primi ha molte applicazioni nelle dimostrazioni matematiche, come mostrato di seguito.

Equazioni diofantee lineari

"Una linea diagonale che va dall'angolo in alto a sinistra a quello in basso a destra. Quindici cerchi sono spaziati a intervalli regolari lungo la linea. Gli assi delle coordinate xy perpendicolari hanno la loro origine nell'angolo in basso a sinistra; la linea ha attraversato l'asse y in alto a sinistra e attraversa l'asse x in basso a destra."
Grafico di un'equazione diofantea lineare , 9 x  + 12 y  = 483. Le soluzioni sono mostrate come cerchi blu.

Le equazioni diofantee sono equazioni in cui le soluzioni sono limitate a numeri interi; prendono il nome dal matematico alessandrino del III secolo Diofanto . Una tipica equazione diofantea lineare cerca interi x e y tali che

ax + per = c

dove a , b e c sono dati interi. Questo può essere scritto come un'equazione per x in aritmetica modulare :

axc mod b .

Sia g il massimo comun divisore di a e b . Entrambi i termini in ax  +  by sono divisibili per g ; quindi anche c deve essere divisibile per g , altrimenti l'equazione non ha soluzioni. Dividendo entrambi i membri per c / g , l'equazione può essere ridotta all'identità di Bezout

sa + tb = g

dove s e t possono essere trovati dall'algoritmo euclideo esteso . Ciò fornisce una soluzione all'equazione diofantea, x 1  =  s ( c / g ) ey 1  =  t ( c / g ).

In generale, un'equazione diofantea lineare non ha soluzioni o un numero infinito di soluzioni. Per trovare quest'ultimo, considera due soluzioni, ( x 1y 1 ) e ( x 2y 2 ), dove

ax 1 + di 1 = c = ax 2 + di 2

o equivalente

a ( x 1x 2 ) = b ( y 2y 1 ).

Pertanto, la più piccola differenza tra due soluzioni x è b / g , mentre la più piccola differenza tra due soluzioni y è a / g . Quindi, le soluzioni possono essere espresse come

x = x 1bu / g
y = y 1 + au / g .

Permettendo a u di variare su tutti i possibili interi, si può generare una famiglia infinita di soluzioni da un'unica soluzione ( x 1y 1 ). Se le soluzioni devono essere numeri interi positivi ( x  > 0,  y  > 0), può essere possibile solo un numero finito di soluzioni. Questa restrizione sulle soluzioni accettabili consente ad alcuni sistemi di equazioni diofantee con più incognite delle equazioni di avere un numero finito di soluzioni; questo è impossibile per un sistema di equazioni lineari quando le soluzioni possono essere qualsiasi numero reale (vedi Sistema sottodeterminato ).

Inversi moltiplicativi e algoritmo RSA

Un campo finito è un insieme di numeri con quattro operazioni generalizzate. Le operazioni sono chiamate addizione, sottrazione, moltiplicazione e divisione e hanno le loro proprietà abituali, come commutatività , associatività e distributività . Un esempio di campo finito è l'insieme di 13 numeri {0, 1, 2, ..., 12} utilizzando l'aritmetica modulare . In questo campo, il risultato di qualsiasi operazione matematica (addizione, sottrazione, moltiplicazione o divisione) è ridotto modulo 13; cioè, multipli di 13 vengono aggiunti o sottratti finché il risultato non viene riportato nell'intervallo 0–12. Ad esempio, il risultato di 5 × 7 = 35 mod 13 = 9. Tali campi finiti possono essere definiti per qualsiasi primo p ; usando definizioni più sofisticate, possono anche essere definite per qualsiasi potenza m di un primo p m . I campi finiti sono spesso chiamati campi di Galois e sono abbreviati come GF( p ) o GF( p m ).   

In tale campo di m numeri, ogni elemento diverso da zero un ha un unico inverso moltiplicativo modulare , un -1 tale che AA -1  =  un -1 un  ≡ 1 mod  m . Questo inverso può essere trovato risolvendo l'equazione di congruenza ax  ≡ 1 mod  m , o l'equazione diofantea lineare equivalente

ascia + mio = 1.

Questa equazione può essere risolta dall'algoritmo euclideo, come descritto sopra . Trovare gli inversi moltiplicativi è un passaggio essenziale nell'algoritmo RSA , ampiamente utilizzato nel commercio elettronico ; in particolare, l'equazione determina l'intero utilizzato per decifrare il messaggio. Sebbene l'algoritmo RSA utilizzi anelli anziché campi, l'algoritmo euclideo può ancora essere utilizzato per trovare un inverso moltiplicativo dove ne esiste uno. L'algoritmo euclideo ha anche altre applicazioni nei codici correttori di errori ; ad esempio, può essere utilizzato in alternativa all'algoritmo Berlekamp–Massey per la decodifica dei codici BCH e Reed–Solomon , che si basano sui campi di Galois.

Teorema cinese del resto

L'algoritmo di Euclide può essere utilizzato anche per risolvere più equazioni diofantee lineari. Tali equazioni sorgono nel teorema cinese dei resti , che descrive un nuovo metodo per rappresentare un intero x . Invece di rappresentare un intero con le sue cifre, può essere rappresentato dai suoi resti x i modulo un insieme di N numeri coprimi m i :

L'obiettivo è determinare x dai suoi N resti x i . La soluzione è combinare le equazioni multiple in un'unica equazione diofantea lineare con un modulo M molto più grande che è il prodotto di tutti i singoli moduli m i , e definire M i come

Quindi, ogni M i è il prodotto di tutti i moduli tranne m i . La soluzione dipende dalla ricerca di N nuovi numeri h i tali che

Con questi numeri h i , qualsiasi intero x può essere ricostruito dai suoi resti x i dall'equazione

Poiché questi numeri h i sono gli inversi moltiplicativi di M i , possono essere trovati utilizzando l'algoritmo di Euclide come descritto nella sottosezione precedente.

Albero di poppa–Brocot

L'algoritmo euclideo può essere utilizzato per organizzare l'insieme di tutti i numeri razionali positivi in un albero binario di ricerca infinito , chiamato albero di Stern-Brocot . Il numero 1 (espresso come frazione 1/1) è posto alla radice dell'albero, e la posizione di qualsiasi altro numero a / b può essere trovata calcolando gcd( a , b ) usando la forma originale dell'algoritmo euclideo , in cui ogni passo sostituisce il più grande dei due numeri dati con la sua differenza con il numero più piccolo (non il resto), fermandosi quando vengono raggiunti due numeri uguali. Un passo dell'algoritmo euclideo che sostituisce il primo dei due numeri corrisponde a un passo nell'albero da un nodo al suo figlio destro, e un passo che sostituisce il secondo dei due numeri corrisponde a un passo nell'albero da un nodo al figlio sinistro. La sequenza di passi costruita in questo modo non dipende dal fatto che a / b sia dato in termini minimi, e forma un cammino dalla radice a un nodo contenente il numero a / b . Questo fatto può essere usato per dimostrare che ogni numero razionale positivo appare esattamente una volta in questo albero.

Ad esempio, 3/4 può essere trovato partendo dalla radice, andando a sinistra una volta, poi a destra due volte:

L'albero Stern–Brocot e le successioni Stern–Brocot di ordine i per i = 1, 2, 3, 4

L'algoritmo euclideo ha quasi la stessa relazione con un altro albero binario sui numeri razionali chiamato albero di Calkin-Wilf . La differenza è che il percorso è invertito: invece di produrre un percorso dalla radice dell'albero a un obiettivo, produce un percorso dall'obiettivo alla radice.

Frazioni continue

L'algoritmo euclideo ha una stretta relazione con le frazioni continue . La sequenza delle equazioni può essere scritta nella forma

L'ultimo termine a destra è sempre uguale all'inverso del membro a sinistra dell'equazione successiva. Quindi, le prime due equazioni possono essere combinate per formare

La terza equazione può essere utilizzata per sostituire il termine denominatore r 1 / r 0 , ottenendo

Il rapporto finale dei resti r k / r k −1 può sempre essere sostituito usando l'equazione successiva della serie, fino all'equazione finale. Il risultato è una frazione continua

Nell'esempio lavorato sopra , è stato calcolato il mcd (1071, 462) e i quozienti q k erano rispettivamente 2, 3 e 7. Pertanto, la frazione 1071/462 può essere scritta

come può essere confermato dal calcolo.

Algoritmi di fattorizzazione

Calcolare un massimo comune divisore è un passo essenziale in diversi integer fattorizzazione algoritmi, come l'algoritmo di Pollard rho , l'algoritmo di Shor , metodo fattorizzazione di Dixon e la Lenstra curva ellittica fattorizzazione . L'algoritmo euclideo può essere utilizzato per trovare questo GCD in modo efficiente. La fattorizzazione della frazione continua utilizza le frazioni continue, che vengono determinate utilizzando l'algoritmo di Euclide.

Efficienza algoritmica

"Un insieme di linee colorate che si irradiano verso l'esterno dall'origine di un sistema di coordinate xy. Ogni linea corrisponde a un insieme di coppie di numeri che richiedono lo stesso numero di passaggi nell'algoritmo euclideo".
Numero di passaggi nell'algoritmo euclideo per gcd( x , y ). I punti più chiari (rosso e giallo) indicano relativamente pochi passi, mentre i punti più scuri (viola e blu) indicano più passi. L'area scura più grande segue la linea y = Φx , dove Φ è il rapporto aureo .

L'efficienza computazionale dell'algoritmo di Euclide è stata studiata a fondo. Questa efficienza può essere descritta dal numero di passaggi di divisione richiesti dall'algoritmo, moltiplicato per la spesa computazionale di ciascun passaggio. La prima analisi conosciuta dell'algoritmo di Euclide è dovuta ad AAL Reynaud nel 1811, che mostrò che il numero di passi di divisione sull'input ( u , v ) è limitato da v ; in seguito lo migliorò a v /2 + 2. Successivamente, nel 1841, PJE Finck mostrò che il numero di passaggi di divisione è al massimo 2 log 2  v  + 1, e quindi l'algoritmo di Euclide viene eseguito in polinomio temporale nella dimensione dell'input. Émile Léger , nel 1837, studiò il caso peggiore, ovvero quando gli input sono numeri di Fibonacci consecutivi . L'analisi di Finck fu affinata da Gabriel Lamé nel 1844, che mostrò che il numero di passaggi richiesti per il completamento non è mai più di cinque volte il numero h delle cifre in base 10 del numero più piccolo  b .

Nel modello di costo uniforme (adatto per analizzare la complessità del calcolo gcd su numeri che rientrano in una singola parola macchina), ogni passaggio dell'algoritmo richiede tempo costante e l'analisi di Lamé implica che anche il tempo di esecuzione totale sia O ( h ). Tuttavia, in un modello di calcolo adatto per il calcolo con numeri più grandi, la spesa computazionale di un singolo calcolo del resto nell'algoritmo può essere grande quanto O ( h 2 ). In questo caso il tempo totale per tutte le fasi dell'algoritmo può essere analizzato utilizzando una serie telescopica , mostrando che è anche O ( h 2 ). Le moderne tecniche algoritmiche basate sull'algoritmo di Schönhage-Strassen per la moltiplicazione rapida di interi possono essere utilizzate per accelerare questo processo, portando ad algoritmi quasilineari per il GCD.

Numero di passi

Il numero di passaggi per calcolare il MCD di due numeri naturali, a e b , può essere indicato con T ( ab ). Se g è il MCD di a e b , allora a  =  mg e b  =  ng per due numeri coprimi m e n . Quindi

T ( a , b ) = T ( m , n )

come si può vedere dividendo tutti i passaggi dell'algoritmo euclideo per g . Per lo stesso argomento, il numero di passaggi rimane lo stesso se a e b vengono moltiplicati per un fattore comune w : T ( a , b ) = T ( wa , wb ). Pertanto, il numero di passi T può variare notevolmente tra coppie di numeri adiacenti, come T( a , b ) e T( ab  + 1), a seconda della dimensione dei due MCD.

La natura ricorsiva dell'algoritmo euclideo fornisce un'altra equazione

T ( a , b ) = 1 + T ( b , r 0 ) = 2 + T ( r 0 , r 1 ) = … = N + T ( r N −2 , r N −1 ) = N + 1

dove T ( x , 0) = 0 per ipotesi.

Nel peggiore dei casi

Se l'algoritmo euclideo richiede N passaggi per una coppia di numeri naturali a  >  b  > 0, i valori più piccoli di a e b per i quali questo è vero sono rispettivamente i numeri di Fibonacci F N +2 e F N +1 . Più precisamente, se l'algoritmo di Euclide richiede N passaggi per la coppia un  >  b , allora si ha una  ≥  F N 2 e b  ≥  F N + 1 . Questo può essere dimostrato per induzione . Se N  = 1, b divide un senza resto; i più piccoli numeri naturali per i quali ciò è vero sono b  = 1 e a  = 2, che sono rispettivamente F 2 e F 3 . Supponiamo ora che il risultato valga per tutti i valori di N fino a M  − 1. Il primo passo dell'algoritmo M -step è a  =  q 0 b  +  r 0 , e l'algoritmo euclideo richiede M  − 1 passi per la coppia b  >  r 0 . Per ipotesi induzione, si ha b  ≥  F M 1 ed r 0  ≥  F M . Pertanto, a  =  q 0 b  +  r 0  ≥  b  +  r 0  ≥  F M +1  +  F M  =  F M +2 , che è la disuguaglianza desiderata. Questa dimostrazione, pubblicata da Gabriel Lamé nel 1844, rappresenta l'inizio della teoria della complessità computazionale , e anche la prima applicazione pratica dei numeri di Fibonacci.

Questo risultato è sufficiente per mostrare che il numero di passi nell'algoritmo di Euclide non può mai essere più di cinque volte il numero delle sue cifre (base 10). Infatti, se l'algoritmo richiede N passaggi, allora b è maggiore o uguale a F N +1 che a sua volta è maggiore o uguale a φ N −1 , dove φ è il rapporto aureo . Poiché b  ≥  φ N −1 , allora N  − 1 ≤ log φ b . Poiché log 10 φ  > 1/5, ( N  − 1)/5 < log 10 φ  log φ b  = log 10 b . Quindi, N  5 log 10 b . Pertanto, l'algoritmo euclideo richiede sempre meno di O ( h ) divisioni, dove h è il numero di cifre nel numero più piccolo b .

Media

Il numero medio di passi compiuti dall'algoritmo euclideo è stato definito in tre modi diversi. La prima definizione è il tempo medio T ( a ) necessario per calcolare il MCD di un dato numero a e di un numero naturale più piccolo b scelto con uguale probabilità dagli interi 0 a a  − 1

Tuttavia, poiché T ( ab ) fluttua drammaticamente con il MCD dei due numeri, anche la funzione media T ( a ) è "rumorosa".

Per ridurre questo rumore, una seconda media τ ( a ) viene rilevata tutti i numeri coprimo con un

Ci sono φ ( a ) interi coprimi minori di a , dove φ è la funzione totiente di Eulero . Questa media tau cresce senza problemi con a

con l'errore residuo essendo dell'ordine un - (1/6) + ε , dove ε è infinitesimale . La costante C ( Costante di Porter ) in questa formula è uguale a

dove γ è la costante di Eulero-Mascheroni e ζ' è la derivata della funzione zeta di Riemann . Il coefficiente principale (12/π 2 ) ln 2 è stato determinato con due metodi indipendenti.

Poiché la prima media può essere calcolata dalla media tau sommando sui divisori d di  a

può essere approssimato dalla formula

dove Λ( d ) è la funzione di Mangoldt .

Una terza media Y ( n ) è definita come il numero medio di passaggi richiesti quando sia a che b sono scelti casualmente (con distribuzione uniforme) da 1 a n

Sostituendo la formula approssimativa per T ( a ) in questa equazione si ottiene una stima per Y ( n )

Spese computazionali per passo

In ogni passo k dell'algoritmo euclideo, il quoziente q k e il resto r k sono calcolati per una data coppia di interi r k -2 e r k -1

r k −2 = q k r k −1 + r k .

La spesa computazionale per passo è associata principalmente alla ricerca di q k , poiché il resto r k può essere calcolato rapidamente da r k −2 , r k −1 e q k

r k = r k −2q k r k −1 .

La spesa computazionale per dividere i numeri di h- bit scala come O ( h ( +1)), dove è la lunghezza del quoziente.

Per fare un confronto, l'algoritmo basato sulla sottrazione originale di Euclide può essere molto più lento. Una singola divisione intera equivale al quoziente q numero di sottrazioni. Se il rapporto di un e b è molto grande, il quoziente è grande e sarà richiesto molti sottrazioni. D'altra parte, è stato dimostrato che è molto probabile che i quozienti siano interi piccoli. La probabilità di un dato quoziente q è approssimativamente ln| u /( u  − 1)| dove u  = ( q  + 1) 2 . A titolo illustrativo, la probabilità di un quoziente di 1, 2, 3 o 4 è rispettivamente di circa 41,5%, 17,0%, 9,3% e 5,9%. Poiché l'operazione di sottrazione è più veloce della divisione, in particolare per i grandi numeri, l'algoritmo di Euclide basato sulla sottrazione è competitivo con la versione basata sulla divisione. Questo è sfruttato nella versione binaria dell'algoritmo di Euclide.

Combinando la stima del numero di passi con la spesa computazionale stimato per spettacoli passo che l'algoritmo di Euclide cresce quadratico ( h 2 ) con il numero medio di cifre h nei primi due numeri a e b . Sia h 0 , h 1 , ..., h N −1 rappresentino il numero di cifre nei resti successivi r 0r 1 , ...,  r N −1 . Poiché il numero di passi N cresce linearmente con h , il tempo di esecuzione è limitato da

Metodi alternativi

L'algoritmo di Euclide è ampiamente utilizzato nella pratica, soprattutto per i piccoli numeri, per la sua semplicità. Per confronto, può essere determinata l'efficienza delle alternative all'algoritmo di Euclide.

Un approccio inefficiente per trovare il MCD di due numeri naturali a e b è quello di calcolare tutti i loro divisori comuni; il MCD è quindi il massimo comun divisore. I divisori comuni si trovano dividendo entrambi i numeri per numeri interi successivi da 2 al numero minore b . Il numero di passaggi di questo approccio cresce linearmente con b , o esponenzialmente nel numero di cifre. Un altro approccio inefficiente è trovare i fattori primi di uno o entrambi i numeri. Come notato sopra , il MCD è uguale al prodotto dei fattori primi condivise dai due numeri uno e b . Anche i metodi attuali per la scomposizione in fattori primi sono inefficienti; molti moderni sistemi di crittografia si affidano addirittura a tale inefficienza.

L' algoritmo binario GCD è un'alternativa efficiente che sostituisce la divisione con operazioni più veloci sfruttando la rappresentazione binaria utilizzata dai computer. Tuttavia, questa alternativa scala anche come O ( h ²) . È generalmente più veloce dell'algoritmo euclideo sui computer reali, anche se scala allo stesso modo. È possibile ottenere un'efficienza aggiuntiva esaminando solo le cifre iniziali dei due numeri a e b . L'algoritmo binario può essere esteso ad altre basi ( algoritmi k -ary), con incrementi di velocità fino a cinque volte. L'algoritmo GCD di Lehmer utilizza lo stesso principio generale dell'algoritmo binario per accelerare i calcoli GCD su basi arbitrarie.

Un approccio ricorsivo per interi elevati (con più di 25.000 posizioni) porta a quasilineari algoritmi intero GCD, come quelli di Schönhage e Stehlé e Zimmermann. Questi algoritmi sfruttano la forma matriciale 2×2 dell'algoritmo euclideo sopra indicato . Questi metodi quasilineari generalmente scalano come O ( h (log h ) 2 (log log h )).

generalizzazioni

Sebbene l'algoritmo euclideo sia utilizzato per trovare il massimo comun divisore di due numeri naturali (interi positivi), può essere generalizzato ai numeri reali e ad altri oggetti matematici, come polinomi , interi quadratici e quaternioni di Hurwitz . In questi ultimi casi, l'algoritmo euclideo viene utilizzato per dimostrare la proprietà cruciale della fattorizzazione unica, cioè che tali numeri possono essere scomposti in modo univoco in elementi irriducibili , le controparti dei numeri primi. La fattorizzazione unica è essenziale per molte prove della teoria dei numeri.

Numeri razionali e reali

L'algoritmo di Euclide può essere applicato ai numeri reali , come descritto da Euclide nel Libro 10 dei suoi Elementi . L'obiettivo dell'algoritmo è identificare un numero reale g tale che due numeri reali dati, a e b , ne siano multipli interi: a = mg e b = ng , dove m e n sono interi . Questa identificazione equivale a trovare un rapporto intero tra i numeri reali a e b ; cioè, determina interi s e t tali che sa + tb = 0 . Euclid usa questo algoritmo per trattare la questione delle lunghezze incommensurabili .

L'algoritmo euclideo dei numeri reali differisce dalla sua controparte intera per due aspetti. Primo, i resti r k sono numeri reali, sebbene i quozienti q k siano interi come prima. In secondo luogo, non è garantito che l'algoritmo termini con un numero finito N di passaggi. In caso affermativo, la frazione a / b è un numero razionale, cioè il rapporto tra due interi

e può essere scritta come una frazione continua finita [ q 0 ; q 1 , q 2 , ..., q N ] . Se l'algoritmo non si ferma, la frazione a / b è un numero irrazionale e può essere descritta da una frazione continua infinita [ q 0 ; q 1 , q 2 , …] . Esempi di frazioni continue infinite sono il rapporto aureo φ = [1; 1, 1, ...] e la radice quadrata di due , 2 = [1; 2, 2, ...] . È improbabile che l'algoritmo si fermi, poiché quasi tutti i rapporti a / b di due numeri reali sono irrazionali.

Una frazione continua infinita può essere troncata ad un passo k [ q 0 ; q 1 , q 2 , ..., q k ] per ottenere un'approssimazione di a / b che migliora all'aumentare di k . L'approssimazione è descritta da convergenti m k / n k ; il numeratore e il denominatore sono coprimi e obbediscono alla relazione di ricorrenza

dove m −1 = n −2 = 1 e m −2 = n −1 = 0 sono i valori iniziali della ricorsione. Il convergente m k / n k è la migliore approssimazione di numeri razionali ad a / b con denominatore n k :

polinomi

I polinomi in una singola variabile x possono essere sommati, moltiplicati e scomposti in polinomi irriducibili , che sono gli analoghi dei numeri primi per gli interi. Il massimo comun divisore polinomio g ( x ) di due polinomi a ( x ) e b ( x ) è definito come il prodotto dei loro polinomi irriducibili condivisi, che possono essere identificati mediante l'algoritmo euclideo. La procedura di base è simile a quella per i numeri interi. Ad ogni passo k , vengono identificati un polinomio quoziente q k ( x ) e un polinomio resto r k ( x ) per soddisfare l'equazione ricorsiva

dove r −2 ( x ) = a ( x ) e r −1 ( x ) = b ( x ) . Ogni polinomio quoziente è scelto in modo tale che ogni resto sia zero o abbia un grado inferiore al grado del suo predecessore: deg[ r k ( x )] < deg[ r k −1 ( x )] . Poiché il grado è un intero non negativo, e poiché decresce ad ogni passo, l'algoritmo euclideo conclude in un numero finito di passi. L'ultimo resto diverso da zero è il massimo comun divisore dei due polinomi originali, a ( x ) e b ( x ) .

Ad esempio, considera i seguenti due polinomi quartici, che ciascuno scompone in due polinomi quadratici

Dividendo a ( x ) per b ( x ) si ottiene un resto r 0 ( x ) = x 3 + (2/3) x 2 + (5/3) x − (2/3) . Nel passaggio successivo, b ( x ) viene diviso per r 0 ( x ) ottenendo un resto r 1 ( x ) = x 2 + x + 2 . Infine, dividendo r 0 ( x ) per r 1 ( x ) si ottiene un resto nullo, che indica che r 1 ( x ) è il massimo comun divisore polinomiale di a ( x ) e b ( x ) , coerente con la loro fattorizzazione.

Molte delle applicazioni sopra descritte per gli interi vengono trasferite ai polinomi. L'algoritmo euclideo può essere utilizzato per risolvere equazioni diofantee lineari e problemi cinesi sui resti per polinomi; possono essere definite anche frazioni continue di polinomi.

L'algoritmo polinomiale euclideo ha altre applicazioni, come le catene di Sturm , un metodo per contare gli zeri di un polinomio che si trova all'interno di un dato intervallo reale . Questo a sua volta ha applicazioni in diverse aree, come il criterio di stabilità di Routh-Hurwitz nella teoria del controllo .

Infine, i coefficienti dei polinomi non devono essere ricavati da numeri interi, reali o anche complessi. Ad esempio, i coefficienti possono essere ricavati da un campo generale, come i campi finiti GF( p ) descritti sopra. Le corrispondenti conclusioni sull'algoritmo euclideo e le sue applicazioni valgono anche per tali polinomi.

interi gaussiani

"Un insieme di punti che si trovano all'interno di un cerchio. Il modello di punti ha una simmetria quadrupla, cioè, le rotazioni di 90 gradi lasciano il modello invariato. Il modello può anche essere rispecchiato su quattro linee che passano attraverso il centro del cerchio: la verticale e l'orizzontale assi e le due linee diagonali a ±45 gradi."
Distribuzione dei primi gaussiani u + vi nel piano complesso, con norme u 2 + v 2 inferiori a 500

Gli interi gaussiani sono numeri complessi della forma α = u + vi , dove u e v sono interi ordinari e i è la radice quadrata di uno negativo . Definendo un analogo dell'algoritmo euclideo, si può dimostrare che gli interi gaussiani sono fattorizzabili in modo univoco, mediante l'argomento sopra . Questa fattorizzazione unica è utile in molte applicazioni, come derivare tutte le terne pitagoriche o dimostrare il teorema di Fermat sulla somma di due quadrati . In generale, l'algoritmo euclideo è conveniente in tali applicazioni, ma non essenziale; per esempio, i teoremi possono spesso essere dimostrati da altri argomenti.

L'algoritmo euclideo sviluppato per due interi gaussiani α e β è quasi lo stesso di quello per gli interi ordinari, ma differisce per due aspetti. Come prima, il compito ad ogni passo k è identificare un quoziente q k e un resto r k tali che

dove r k −2 = α , dove r k −1 = β , e dove ogni resto è strettamente minore del suo predecessore: | r k | < | r k -1 | . La prima differenza è che i quozienti ei resti sono essi stessi interi gaussiani, e quindi sono numeri complessi . I quozienti q k si trovano generalmente arrotondando le parti reali e complesse del rapporto esatto (come il numero complesso α / β ) agli interi più vicini. La seconda differenza sta nella necessità di definire come un resto complesso possa essere "più piccolo" di un altro. Per fare ciò, viene definita una funzione norma f ( u + vi ) = u 2 + v 2 , che converte ogni intero gaussiano u + vi in un intero ordinario. Dopo ogni passo k dell'algoritmo euclideo, la norma del resto f ( r k ) è minore della norma del resto precedente, f ( r k −1 ) . Poiché la norma è un intero non negativo e decresce ad ogni passo, l'algoritmo euclideo per gli interi gaussiani termina con un numero finito di passi. Il resto finale diverso da zero è mcd( α , β ) , l'intero gaussiano di norma più grande che divide sia α che β ; è unico fino alla moltiplicazione per un'unità, ±1 o ± i .

Molte delle altre applicazioni dell'algoritmo euclideo vengono trasferite agli interi gaussiani. Ad esempio, può essere utilizzato per risolvere equazioni diofantee lineari e problemi con i resti cinesi per interi gaussiani; possono essere definite anche frazioni continue di interi gaussiani.

domini euclidei

Un insieme di elementi sotto due operazioni binarie , denotate come addizione e moltiplicazione, è detto dominio euclideo se forma un anello commutativo R e, grosso modo, se su di essi può essere eseguito un algoritmo euclideo generalizzato. Le due operazioni di un tale anello non devono necessariamente essere l'addizione e la moltiplicazione dell'aritmetica ordinaria; piuttosto, possono essere più generali, come le operazioni di un gruppo matematico o di un monoide . Tuttavia, queste operazioni generali dovrebbero rispettare molte delle leggi che regolano l'aritmetica ordinaria, come la commutatività , l' associatività e la distributività .

L'algoritmo euclideo generalizzato richiede una funzione euclidea , cioè una mappatura f da R nell'insieme degli interi non negativi tale che, per due elementi a e b diversi da zero in R , esistono q ed r in R tali che a = qb + r e f ( r ) < f ( b ) . Esempi di tali mappature sono il valore assoluto per gli interi, il grado per i polinomi univariati e la norma per gli interi gaussiani sopra . Il principio di base è che ogni passo dell'algoritmo riduce f inesorabilmente; quindi, se f può essere ridotto solo un numero finito di volte, l'algoritmo deve fermarsi in un numero finito di passi. Questo principio si basa sulla proprietà di buon ordinamento degli interi non negativi, che afferma che ogni insieme non vuoto di interi non negativi ha un membro più piccolo.

Il teorema fondamentale dell'aritmetica si applica a qualsiasi dominio euclideo: qualsiasi numero di un dominio euclideo può essere scomposto in modo univoco in elementi irriducibili . Qualsiasi dominio euclideo è un dominio di fattorizzazione unica (UFD), sebbene non sia vero il contrario. I domini euclidei e gli UFD sono sottoclassi dei domini GCD , domini in cui esiste sempre un massimo comun divisore di due numeri. In altre parole, può esistere un massimo comun divisore (per tutte le coppie di elementi in un dominio), anche se potrebbe non essere possibile trovarlo utilizzando un algoritmo euclideo. Un dominio euclideo è sempre un dominio ideale principale (PID), un dominio integrale in cui ogni ideale è un ideale principale . Di nuovo, non è vero il contrario: non tutti i PID sono un dominio euclideo.

La fattorizzazione unica dei domini euclidei è utile in molte applicazioni. Ad esempio, l'unica fattorizzazione degli interi gaussiani è conveniente nel derivare formule per tutte le terne pitagoriche e nel dimostrare il teorema di Fermat sulle somme di due quadrati . La fattorizzazione unica fu anche un elemento chiave in un tentativo di dimostrazione dell'Ultimo Teorema di Fermat pubblicato nel 1847 da Gabriel Lamé, lo stesso matematico che analizzò l'efficienza dell'algoritmo di Euclide, sulla base di un suggerimento di Joseph Liouville . L'approccio di Lamé necessaria la fattorizzazione unica di numeri della forma x + ωy , dove x ed y sono numeri interi, e ω = e 2 / n è n esima di 1, che è, ω n = 1 . Sebbene questo approccio abbia successo per alcuni valori di n (come n = 3 , gli interi di Eisenstein ), in generale tali numeri non fattorizzano in modo univoco. Questo fallimento della fattorizzazione unica in alcuni campi ciclotomici ha portato Ernst Kummer al concetto di numeri ideali e, in seguito, Richard Dedekind agli ideali .

Fattorizzazione unica di interi quadratici

"Un insieme di punti che si trovano all'interno di un cerchio. Il modello di punti ha una simmetria di sei volte, cioè, le rotazioni di 60 gradi lasciano il modello invariato. Il modello può anche essere rispecchiato su sei linee che passano attraverso il centro del cerchio: la verticale e l'orizzontale assi e le quattro linee diagonali a ±30 e ±60 gradi."
Distribuzione di Eisenstein primi u + nel piano complesso, con norme inferiori a 500. Il numero ω è una radice cubica di 1 .

Gli anelli interi quadratici sono utili per illustrare i domini euclidei. Gli interi quadratici sono generalizzazioni degli interi gaussiani in cui l' unità immaginaria i è sostituita da un numero ω . Pertanto, hanno la forma u + , dove u e v sono interi e ω ha una delle due forme, a seconda di un parametro D . Se D non è uguale a un multiplo di quattro più uno, allora

Se, tuttavia, D è uguale a un multiplo di quattro più uno, allora

Se la funzione f corrisponde a una funzione norma , come quella usata per ordinare gli interi gaussiani sopra , allora il dominio è noto come norma-euclidea . Gli anelli norma-euclidea degli interi quadratici sono esattamente quelli in cui D è uno dei valori −11, −7, −3, −2, −1, 2, 3, 5, 6, 7, 11, 13, 17, 19 , 21, 29, 33, 37, 41, 57 o 73. I casi D = −1 e D = −3 danno rispettivamente gli interi gaussiani e gli interi di Eisenstein .

Se f può essere una qualsiasi funzione euclidea, allora l'elenco dei possibili valori di D per i quali il dominio è euclideo non è ancora noto. Il primo esempio di un dominio euclideo che non era norma-euclideo (con D = 69 ) è stato pubblicato nel 1994. Nel 1973, Weinberger dimostrò che un anello intero quadratico con D > 0 è euclideo se, e solo se, è principale dominio ideale , a condizione che valga l' ipotesi di Riemann generalizzata .

Anelli non commutativi

L'algoritmo euclideo può essere applicato ad alcuni anelli non commutativi come l'insieme dei quaternioni di Hurwitz . Lasciare α e p rappresentano due elementi da tale anello a. Hanno una comune destra divisore δ se α = ξδ e β = ηδ per alcune scelta di ξ e η nell'anello. Allo stesso modo, hanno un divisore fianco comune se α = e β = per alcune scelta di ξ e η nell'anello. Poiché la moltiplicazione non è commutativa, esistono due versioni dell'algoritmo euclideo, una per i divisori destri e l'altra per i divisori sinistri. Scegliendo i divisori giusti, il primo passo per trovare il mcd( α , β ) con l'algoritmo euclideo può essere scritto

dove ψ 0 rappresenta il quoziente e ρ 0 il resto. Questa equazione mostra che qualsiasi divisore comune diritto di α e β è similmente un divisore comune del resto P 0 . L'equazione analoga per i divisori di sinistra sarebbe

Con entrambe le scelte, il processo viene ripetuto come sopra fino a quando non viene identificato il massimo comune divisore destro o sinistro. Come nel dominio euclideo, la "dimensione" del resto P 0 (formalmente, la sua norma ) deve essere rigorosamente più piccolo β , e ci deve essere solo un numero finito di dimensioni possibili per ρ 0 , in modo che l'algoritmo è garantito terminare.

La maggior parte dei risultati per il MCD viene trasferita ai numeri non commutativi. Ad esempio, l'identità di Bézout afferma che il diritto mcd( α , β ) può essere espresso come una combinazione lineare di α e β . In altre parole, ci sono numeri σ e τ tali che

L'identità analoga per il GCD sinistro è quasi la stessa:

L'identità di Bézout può essere utilizzata per risolvere equazioni diofantee. Ad esempio, una delle dimostrazioni standard del teorema dei quattro quadrati di Lagrange , secondo cui ogni intero positivo può essere rappresentato come somma di quattro quadrati, si basa in questo modo sui MCD di quaternioni.

Guarda anche

  • Ritmo euclideo , un metodo per utilizzare l'algoritmo euclideo per generare ritmi musicali

Appunti

Riferimenti

Bibliografia

link esterno