Algoritmo euclideo esteso - Extended Euclidean algorithm

In aritmetica e programmazione informatica , l' algoritmo euclideo esteso è un'estensione dell'algoritmo euclideo e calcola, oltre al massimo comun divisore (mcd) degli interi a e b , anche i coefficienti dell'identità di Bézout , che sono gli interi x e y tale che

ax+by=\gcd(a,b).

Questo è un algoritmo di certificazione , perché il mcd è l'unico numero che può soddisfare contemporaneamente questa equazione e dividere gli input. Essa permette di calcolare anche, con un costo quasi senza supplemento, i quozienti di un e b dal loro massimo comun divisore.

L'algoritmo euclideo esteso si riferisce anche a un algoritmo molto simile per il calcolo del massimo comun divisore polinomiale e dei coefficienti dell'identità di Bézout di due polinomi univariati .

L'algoritmo di Euclide esteso è particolarmente utile quando un e b sono coprimi . Con tale disposizione, x è l' inverso moltiplicativo modulare di a modulo b , e y è l'inverso moltiplicativo modulare di b modulo a . Analogamente, l'algoritmo euclideo polinomiale esteso permette di calcolare l' inverso moltiplicativo nelle estensioni di campo algebrico e, in particolare, nei campi finiti di ordine non primo. Ne consegue che entrambi gli algoritmi euclidei estesi sono ampiamente utilizzati in crittografia . In particolare, il calcolo dell'inverso moltiplicativo modulare è un passaggio essenziale nella derivazione di coppie di chiavi nel metodo di crittografia a chiave pubblica RSA .

Descrizione

L'algoritmo euclideo standard procede per una successione di divisioni euclidee i cui quozienti non vengono utilizzati. Vengono mantenuti solo i resti . Per l'algoritmo esteso vengono utilizzati i quozienti successivi. Più precisamente, l'algoritmo euclideo standard con a e b come input, consiste nel calcolare una sequenza di quozienti e una sequenza di resti tali che $q_{1},\ldots ,q_{k}$ $r_{0},\ldots ,r_{k+1}$

{\begin{aligned}r_{0}&=a\\r_{1}&=b\\&\,\,\,\vdots \\r_{i+1}&=r_{i- 1}-q_{i}r_{i}\quad {\text{e}}\quad 0\leq r_{i+1}<|r_{i}|\quad {\text{(questo definisce }}q_ {i})\\&\,\,\,\vdots \end{allineato}}

È la proprietà principale della divisione euclidea che le disuguaglianze a destra definiscano in modo univoco e da e $q_{i}$ $r_{i+1}$ $r_{i-1}$ $r_{i}.$

Il calcolo si ferma quando si raggiunge un resto che è zero; il massimo comun divisore è allora l'ultimo resto diverso da zero $r_{k+1}$ $r_{k}.$

L'algoritmo euclideo esteso procede in modo simile, ma aggiunge altre due sequenze, come segue

{\begin{aligned}r_{0}&=a&r_{1}&=b\\s_{0}&=1&s_{1}&=0\\t_{0}&=0&t_{1}& =1\\&\,\,\,\vdots &&\,\,\,\vdots \\r_{i+1}&=r_{i-1}-q_{i}r_{i}&{\ text{e }}0&\leq r_{i+1}<|r_{i}|&{\text{(questo definisce }}q_{i}{\text{)}}\\s_{i+1} &=s_{i-1}-q_{i}s_{i}\\t_{i+1}&=t_{i-1}-q_{i}t_{i}\\&\,\,\ ,\vdots \end{allineato}}

Il calcolo si ferma anche quando e dà $r_{k+1}=0$

$r_{k}$ è il massimo comun divisore dell'input e $a=r_{0}$ $b=r_{1}.$
I coefficienti di Bézout sono e cioè $s_{k}$ $t_{k},$ $\gcd(a,b)=r_{k}=as_{k}+bt_{k}$
I quozienti di un e b per il loro massimo comun divisore sono date da e $s_{k+1}=\pm {\frac {b}{\gcd(a,b)}}$ $t_{k+1}=\pm {\frac {a}{\gcd(a,b)}}$

Inoltre, se a e b sono entrambi positivi e , allora $\gcd(a,b)\neq \min(a,b)$

|s_{i}|\leq \left\lfloor {\frac {b}{2\gcd(a,b)}}\right\rfloor \quad {\text{e}}\quad |t_{ i}|\leq \left\lfloor {\frac {a}{2\gcd(a,b)}}\right\rfloor

per dove denota la parte integrale di $x$ , che è il massimo intero non maggiore di $x$ . $0\leq i\leq k,$ $\lfloor x\rfloor$

Ciò implica che la coppia di coefficienti di Bézout fornita dall'algoritmo euclideo esteso è la coppia minima di coefficienti di Bézout, essendo l'unica coppia che soddisfa entrambe le disuguaglianze di cui sopra.

Inoltre significa che l'algoritmo può essere eseguito senza integer overflow da un programma per computer utilizzando interi di dimensione fissa maggiore di quella di a e b .

Esempio

La tabella seguente mostra come procede l'algoritmo euclideo esteso con gli input 240 e 46 . Il massimo comun divisore è l'ultima voce diversa da zero, 2 nella colonna "resto". Il calcolo si ferma alla riga 6, perché il resto è 0 . I coefficienti di Bézout compaiono nelle ultime due voci della penultima riga. Infatti, è facile verificare che −9 × 240 + 47 × 46 = 2 . Infine gli ultimi due elementi 23 e -120 dell'ultima riga sono, fino al segno, i quozienti dell'ingresso 46 e 240 per il massimo comun divisore 2 .

indice i	quoziente q _{i −1}	Resto r _io	s _i	t _i
0		240	1	0
1		46	0	1
2	240 ÷ 46 = 5	240 − 5 × 46 = 10	1 − 5 × 0 = 1	0 − 5 × 1 = −5
3	46 ÷ 10 = 4	46 − 4 × 10 = 6	0 − 4 × 1 = −4	1 − 4 × −5 = 21
4	10 ÷ 6 = 1	10 − 1 × 6 = 4	1 − 1 × −4 = 5	−5 − 1 × 21 = −26
5	6 ÷ 4 = 1	6 − 1 × 4 = 2	−4 − 1 × 5 = −9	21 − 1 × −26 = 47
6	4 ÷ 2 = 2	4 − 2 × 2 = 0	5 − 2 × −9 = 23	−26 − 2 × 47 = −120

Prova

Poiché la sequenza di è una sequenza decrescente di interi non negativi (da i = 2 in poi). Quindi deve fermarsi con alcuni Questo dimostra che l'algoritmo si ferma alla fine. $0\leq r_{i+1}<|r_{i}|,$ $r_{i}$ $r_{k+1}=0.$

Poiché il massimo comun divisore è lo stesso per e Questo mostra che il massimo comun divisore dell'input è uguale a quello di Questo dimostra che è il massimo comun divisore di a e b . (Fino a questo punto, la dimostrazione è la stessa del classico algoritmo euclideo.) $r_{i+1}=r_{i-1}-r_{i}q_{i},$ $(r_{i-1},r_{i})$ $(r_{i},r_{i+1}).$ $a=r_{0},b=r_{1}$ $r_{k},r_{k+1}=0.$ $r_{k}$

Come e abbiamo per i = 0 e 1. La relazione segue per induzione per tutti : $a=r_{0}$ $b=r_{1},$ $as_{i}+bt_{i}=r_{i}$ $i>1$

r_{i+1}=r_{i-1}-r_{i}q_{i}=(as_{i-1}+bt_{i-1})-(as_{i}+bt_{ i})q_{i}=(come_{i-1}-come_{i}q_{i})+(bt_{i-1}-bt_{i}q_{i})=come_{i+1} +bt_{i+1}.

Così e sono coefficienti di Bézout. $s_{k}$ $t_{k}$

Considera la matrice

A_{i}={\begin{pmatrix}s_{i-1}&s_{i}\\t_{i-1}&t_{i}\end{pmatrix}}.

La relazione di ricorrenza può essere riscritta in forma matriciale

A_{i+1}=A_{i}\cdot {\begin{pmatrix}0&1\\1&-q_{i}\end{pmatrix}}.

La matrice è la matrice identità e il suo determinante è uno. Il determinante della matrice più a destra nella formula precedente è −1. Ne segue che il determinante di è In particolare, poiché abbiamo Considerando questo come un'identità di Bézout, questo mostra che e sono coprimi . La relazione che è stata dimostrata sopra e il lemma di Euclide mostrano che divide b e divide a . Essendo coprimi, sono, fino al loro segno, i quozienti di b e a per il loro massimo comun divisore. $A_{1}$ $A_{i}$ $(-1)^{i-1}.$ $i=k+1,$ $s_{k}t_{k+1}-t_{k}s_{k+1}=(-1)^{k}.$ $s_{k+1}$ $t_{k+1}$ $come_{k+1}+bt_{k+1}=0$ $s_{k+1}$ $t_{k+1}$

Per dimostrare l'ultima affermazione, supponiamo che a e b siano entrambi positivi e . Allora, , e se , si può vedere che le sequenze s e t per ( a , b ) sotto l'EEA sono, fino agli 0 e 1 iniziali, le sequenze t e s per ( b , a ). Le definizioni mostrano quindi che il caso ( a , b ) si riduce al caso ( b , a ). Quindi supponiamo che senza perdita di generalità. $\gcd(a,b)\neq \min(a,b)$ $a\neq b$ $a<b$ $a>b$

Si può vedere che è 1 e (che esiste da ) è un numero intero negativo. Successivamente, l' alternanza di segno e strettamente crescente in grandezza, che segue induttivamente dalle definizioni e dal fatto che per , il caso vale perché . Lo stesso vale per il dopo i primi termini, per lo stesso motivo. Inoltre, è facile vedere che (quando un e b sono entrambi positivi e ). Così, $s_{2}$ $s_{3}$ $\gcd(a,b)\neq \min(a,b)$ $s_{i}$ $q_{i}\geq 1$ $1\leq i\leq k$ $i=1$ $a>b$ $t_{i}$ $q_{k}\geq 2$ $\gcd(a,b)\neq \min(a,b)$

|s_{k+1}|=\left|{\frac {b}{\gcd(a,b)}}\right|\geq 2|s_{k}|\qquad {\text{e }}\qquad |t_{k+1}|=\left|{\frac {a}{\gcd(a,b)}}\right|\geq 2|t_{k}|.

Questo, accompagnato dal fatto che sono maggiori o uguali a in valore assoluto rispetto a qualsiasi precedente o rispettivamente completata la dimostrazione. $s_{k},t_{k}$ $s_{i}$ $t_{i}$

Algoritmo euclideo esteso polinomiale

Per i polinomi univariati con coefficienti in un campo , tutto funziona in modo simile, divisione euclidea, identità di Bézout e algoritmo euclideo esteso. La prima differenza è che, nella divisione euclidea e nell'algoritmo, la disuguaglianza deve essere sostituita da una disuguaglianza sui gradi Altrimenti, tutto ciò che precede in questo articolo rimane lo stesso, semplicemente sostituendo gli interi con i polinomi. $0\leq r_{i+1}<|r_{i}|$ $\deg r_{i+1}<\deg r_{i}.$

Una seconda differenza risiede nel vincolo sulla dimensione dei coefficienti di Bézout fornito dall'algoritmo euclideo esteso, che è più accurato nel caso polinomiale, portando al seguente teorema.

Se a e b sono due polinomi diversi da zero, allora l'algoritmo euclideo esteso produce l'unica coppia di polinomi ( s , t ) tale che

as+bt=\gcd(a,b)

e

\deg s<\deg b-\deg(\gcd(a,b)),\quad \deg t<\deg a-\deg(\gcd(a,b)).

Una terza differenza è che, nel caso polinomiale, il massimo comun divisore è definito solo fino alla moltiplicazione per una costante diversa da zero. Esistono diversi modi per definire in modo univoco un massimo comun divisore.

In matematica, è comune richiedere che il massimo comun divisore sia un polinomio monico . Per ottenere questo, è sufficiente dividere ogni elemento dell'uscita dal primo coefficiente di Ciò permette che, se un e b sono coprimi, si ottiene 1 sul lato destro della disuguaglianza di Bézout. Altrimenti, si può ottenere qualsiasi costante diversa da zero. In computer algebra , i polinomi hanno comunemente coefficienti interi, e questo modo di normalizzare il massimo comun divisore introduce troppe frazioni per essere conveniente. $r_{k}.$

Il secondo modo per normalizzare il massimo comun divisore nel caso di polinomi a coefficienti interi è dividere ogni output per il contenuto di per ottenere un massimo comun divisore primitivo . Se i polinomi di input sono coprimi, questa normalizzazione fornisce anche un massimo comun divisore uguale a 1. Lo svantaggio di questo approccio è che molte frazioni dovrebbero essere calcolate e semplificate durante il calcolo. $r_{k},$

Un terzo approccio consiste nell'estendere l'algoritmo delle sequenze di pseudo-resti subrisultati in modo simile all'estensione dell'algoritmo euclideo all'algoritmo euclideo esteso. Ciò consente che, partendo da polinomi con coefficienti interi, tutti i polinomi calcolati abbiano coefficienti interi. Inoltre, ogni resto calcolato è un polinomio sottorisultante . In particolare, se i polinomi di input sono coprimi, allora l'identità di Bézout diventa $r_{i}$

as+bt=\operatorname {Res} (a,b),

dove denota la risultante di a e b . In questa forma dell'identità di Bézout, non c'è alcun denominatore nella formula. Se si divide tutto per il risultante si ottiene l'identità classica di Bézout, con un esplicito denominatore comune per i numeri razionali che vi compaiono. $\operatorname {Ris} (a,b)$

Pseudocodice

Per implementare l'algoritmo sopra descritto, si dovrebbe prima notare che sono necessari solo gli ultimi due valori delle variabili indicizzate ad ogni passo. Pertanto, per risparmiare memoria, ogni variabile indicizzata deve essere sostituita da due sole variabili.

Per semplicità, l'algoritmo seguente (e gli altri algoritmi in questo articolo) usa assegnazioni parallele . In un linguaggio di programmazione che non ha questa caratteristica, le assegnazioni parallele devono essere simulate con una variabile ausiliaria. Ad esempio, il primo,

(old_r, r) := (r, old_r - quotient * r)

è equivalente a

prov := r;
r := old_r - quotient × prov;
old_r := prov;

e analogamente per gli altri incarichi paralleli. Questo porta al seguente codice:

function extended_gcd(a, b)
    (old_r, r) := (a, b)
    (old_s, s) := (1, 0)
    (old_t, t) := (0, 1)
    
    while r ≠ 0 do
        quotient := old_r div r
        (old_r, r) := (r, old_r − quotient × r)
        (old_s, s) := (s, old_s − quotient × s)
        (old_t, t) := (t, old_t − quotient × t)
    
    output "Bézout coefficients:", (old_s, old_t)
    output "greatest common divisor:", old_r
    output "quotients by the gcd:", (t, s)

I quozienti di un e b per il loro massimo comune divisore, che è uscita, possono avere un segno non corretto. Questo è facile da correggere alla fine del calcolo, ma non è stato fatto qui per semplificare il codice. Allo stesso modo, se a o b è zero e l'altro è negativo, il massimo comun divisore che viene prodotto è negativo e tutti i segni dell'output devono essere modificati.

Infine, si noti che nell'identità di Bézout, , si può risolvere per dato . Pertanto, un'ottimizzazione dell'algoritmo di cui sopra consiste nel calcolare solo la sequenza (che produce il coefficiente di Bézout ), e quindi calcolare alla fine: $ax+by=\gcd(a,b)$ $y$ $a,b,x,\gcd(a,b)$ $s_{k}$ $x$ $y$

function extended_gcd(a, b)
    s := 0;    old_s := 1
    r := b;    old_r := a
         
    while r ≠ 0 do
        quotient := old_r div r
        (old_r, r) := (r, old_r − quotient × r)
        (old_s, s) := (s, old_s − quotient × s)
    
    if b ≠ 0 then
        bezout_t := (old_r − old_s × a) div b
    else
        bezout_t := 0
    
    output "Bézout coefficients:", (old_s, bezout_t)
    output "greatest common divisor:", old_r

Tuttavia, in molti casi questa non è realmente un'ottimizzazione: mentre il primo algoritmo non è suscettibile di overflow se utilizzato con numeri interi macchina (cioè interi con un limite superiore fisso di cifre), la moltiplicazione di old_s * a nel calcolo di bezout_t può traboccare, limitando questa ottimizzazione agli input che possono essere rappresentati in meno della metà della dimensione massima. Quando si utilizzano interi di dimensione illimitata, il tempo necessario per la moltiplicazione e la divisione cresce quadraticamente con la dimensione degli interi. Ciò implica che l'"ottimizzazione" sostituisce una sequenza di moltiplicazioni/divisioni di numeri interi piccoli con un'unica moltiplicazione/divisione, che richiede più tempo di calcolo rispetto alle operazioni che sostituisce, messe insieme.

Semplificazione delle frazioni

Una frazione $.mw-parser-output .sfrac{white-space:nowrap}.mw-parser-output .sfrac.tion,.mw-parser-output .sfrac .tion{display:inline-block;vertical-align:-0.5em;font-size:85%;text-align:center}.mw-parser-output .sfrac .num,.mw-parser-output .sfrac .den{display:block;line-height:1em;margin:0 0.1em}.mw-parser-output .sfrac .den{border-top:1px solid}.mw-parser-output .sr-only{border:0;clip:rect(0,0,0,0);height:1px;margin:-1px;overflow:hidden;padding:0;position:absolute;width:1px} un/B$ è in forma canonica semplificata se $a$ e $b$ sono coprimi e $b$ è positivo. Questa forma canonica semplificata si ottiene sostituendo le tre righe di output dello pseudo codice precedente con

if  $s = 0$  then output "Division by zero"
if  $s < 0$  then  $s := - s$ ;   $t := - t$    (for avoiding negative denominators)
if  $s = 1$  then output  $- t$         (for avoiding denominators equal to 1)
output  $- t / s$

La dimostrazione di questo algoritmo si basa sul fatto che $s$ e $t$ sono due interi coprimi tali che $come + bt = 0$ , e quindi . Per ottenere la forma canonica semplificata è sufficiente spostare il segno meno per avere un denominatore positivo. ${\frac {a}{b}}=-{\frac {t}{s}}$

Se $b$ divide $a$ equamente, l'algoritmo esegue solo un'iterazione e abbiamo $s = 1$ alla fine dell'algoritmo. È l'unico caso in cui l'output è un numero intero.

Calcolo degli inversi moltiplicativi in strutture modulari

L'algoritmo euclideo esteso è lo strumento essenziale per il calcolo degli inversi moltiplicativi nelle strutture modulari, tipicamente gli interi modulari e le estensioni algebriche di campo . Un esempio notevole di quest'ultimo caso sono i campi finiti di ordine non primo.

Interi modulari

Se $n$ è un intero positivo, l'anello $Z / n Z$ può essere identificato con l'insieme ${0, 1, ..., n -1}$ dei resti della divisione euclidea per $n$ , l'addizione e la moltiplicazione consistenti nel prendere il resto per $n$ del risultato dell'addizione e della moltiplicazione di numeri interi. Un elemento $a$ di $Z / n Z$ ha un inverso moltiplicativo (cioè è un'unità ) se è coprimo con $n$ . In particolare, se $n$ è primo , $a$ ha un inverso moltiplicativo se non è zero (modulo $n$ ). Quindi $Z / n Z$ è un campo se e solo se $n$ è primo.

L'identità di Bézout afferma che $a$ e $n$ sono coprimi se e solo se esistono interi $s$ e $t$ tali che

ns+at=1

Riducendo questa identità modulo $n si$ ottiene

at\equiv 1\mod n.

Quindi $t$ , o più esattamente il resto della divisione di $t$ per $n$ , è l'inverso moltiplicativo di $a$ modulo $n$ .

Per adattare l'algoritmo euclideo esteso a questo problema, si dovrebbe notare che il coefficiente di Bézout di $n$ non è necessario, e quindi non deve essere calcolato. Inoltre, per ottenere un risultato positivo e minore di n , si può utilizzare il fatto che l'intero $t$ fornito dall'algoritmo soddisfa $| t | < n$ . Cioè, se $t < 0$ , si deve aggiungere $n$ alla fine. Ciò si traduce nello pseudocodice, in cui l'input n è un numero intero maggiore di 1.

 function inverse(a, n)
    t := 0;     newt := 1
    r := n;     newr := a

    while newr ≠ 0 do
        quotient := r div newr
        (t, newt) := (newt, t − quotient × newt) 
        (r, newr) := (newr, r − quotient × newr)

    if r > 1 then
        return "a is not invertible"
    if t < 0 then
        t := t + n

    return t

Estensioni di campi algebrici semplici

L'algoritmo euclideo esteso è anche lo strumento principale per il calcolo degli inversi moltiplicativi in semplici estensioni di campo algebrico . Un caso importante, ampiamente utilizzato in crittografia e teoria dei codici , è quello dei campi finiti di ordine non primo. Infatti, se $p$ è un numero primo, $eq = p d$ , il campo di ordine $q$ è una semplice estensione algebrica del campo primo di $p$ elementi, generato da una radice di un polinomio irriducibile di grado $d$ .

All'anello quoziente si può identificare una semplice estensione algebrica $L$ di un campo $K$ , generato dalla radice di un polinomio irriducibile $p$ di grado $d$ , ed i suoi elementi sono in corrispondenza biunivoca con i polinomi di grado minore di $d$ . L'addizione in $L$ è l'addizione di polinomi. La moltiplicazione in $L$ è il resto della divisione euclidea per $p$ del prodotto dei polinomi. Quindi, per completare l'aritmetica in $L$ , resta solo da definire come calcolare gli inversi moltiplicativi. Questo viene fatto dall'algoritmo euclideo esteso. $K[X]/\langle p\rangle ,$

L'algoritmo è molto simile a quello fornito sopra per il calcolo dell'inverso moltiplicativo modulare. Ci sono due differenze principali: in primo luogo la penultima riga non è necessaria, perché il coefficiente di Bézout fornito ha sempre un grado inferiore a $d$ . In secondo luogo, il massimo comun divisore che viene fornito, quando i polinomi di input sono coprimi, può essere un qualsiasi elemento non nullo di $K$ ; questo coefficiente di Bézout (un polinomio generalmente di grado positivo) va quindi moltiplicato per l'inverso di questo elemento di $K$ . Nello pseudocodice che segue, $p$ è un polinomio di grado maggiore di uno, e $a$ è un polinomio.

function inverse(a, p)
    t := 0;     newt := 1
    r := p;     newr := a

    while newr ≠ 0 do
        quotient := r div newr
        (r, newr) := (newr, r − quotient × newr)
        (t, newt) := (newt, t − quotient × newt)

    if degree(r) > 0 then 
        return "Either p is not irreducible or a is a multiple of p"

    return (1/r) × t

Esempio

Ad esempio, se il polinomio utilizzato per definire il campo finito GF(2 ⁸ ) è p = x ⁸ + x ⁴ + x ³ + x + 1, e a = x ⁶ + x ⁴ + x + 1 è l'elemento il cui inverso è desiderato, quindi l'esecuzione dell'algoritmo porta al calcolo descritto nella tabella seguente. Ricordiamo che nei campi di ordine 2 ⁿ , si ha - z = z e z + z = 0 per ogni elemento z nel campo). Poiché 1 è l'unico elemento diverso da zero di GF(2), l'aggiustamento nell'ultima riga dello pseudocodice non è necessario.

fare un passo	quoziente	r, nuovo	s, notizie	t, newt
		p = x ⁸ + x ⁴ + x ³ + x + 1	1	0
		a = x ⁶ + x ⁴ + x + 1	0	1
1	x ² + 1	x ² = p - a ( x ² + 1)	1	x ² + 1 = 0 - 1 × ( x ² + 1)
2	x ⁴ + x ²	x + 1 = a - x ² ( x ⁴ + x ² )	x ⁴ +x ² = 0 - 1(x ⁴ +x ² )	x ⁶ + x ² + 1 = 1 - ( x ⁴ + x ² ) ( x ² + 1)
3	x + 1	1 = x ² - ( x + 1) ( x + 1)	x ⁵ +x ⁴ +x ³ +x ² +1 = 1 - (x +1)(x ⁴ + x ² )	x ⁷ + x ⁶ + x ³ + x = ( x ² + 1) - ( x + 1) ( x ⁶ + x ² + 1)
4	x + 1	0 = ( x + 1) - 1 × ( x + 1)	x ⁶ + x ⁴ + x + 1 = (x ⁴ +x ² ) - (x+1)(x ⁵ +x ⁴ +x ³ +x ² +1)

Quindi, l'inverso è x ⁷ + x ⁶ + x ³ + x , come può essere confermato moltiplicando i due elementi tra loro e prendendo il resto per $p$ del risultato.

Il caso di più di due numeri

Si può trattare iterativamente il caso di più di due numeri. Per prima cosa lo mostriamo . Per dimostrare questo let . Per definizione di gcd è un divisore di e . Così per alcuni . Allo stesso modo è un divisore di così per alcuni . Lascia . Dalla nostra costruzione di , ma poiché è il massimo divisore è un'unità . E poiché il risultato è dimostrato. $\gcd(a,b,c)=\gcd(\gcd(a,b),c)$ $d=\gcd(a,b,c)$ $d$ $a$ $b$ $\gcd(a,b)=kd$ $k$ $d$ $c$ $c=jd$ $j$ $u=\gcd(k,j)$ $u$ $ud|a,b,c$ $d$ $u$ $ud=\gcd(\gcd(a,b),c)$