Identità di Bézout

L'identità di Bézout permette di scrivere il massimo comune divisore di due interi a e b come combinazione lineare a coefficienti interi j e k. $$ MCD(a,b)=d=aj+bk $$

Come trovare i coefficienti dell'identità di Bézout

Per trovare i coefficienti interi j e k posso usare l'algoritmo euclideo delle divisioni successive di un numero.

Un esempio pratico

Devo calcolare il MCD di 2016 e 35

$$ a=2016 \\ b=35 $$

Uso l'algoritmo di Euclide

$$ 2016 = 35 \cdot 57 + 21
\\ 35 = 21 \cdot 1 + 14
\\ 21 = 14 \cdot 1 + 7
\\ 14 = 7 \cdot 2 + 0
$$

Nota. L'ultimo elemento di ogni riga è il resto della divisione.

L'ultimo resto non nullo (7) è il massimo comune divisore dei due numeri

$$ MCD(2016,35)=7 $$

Per trovare i coefficienti dell'identità di Bézout, assegno alle variabili a e b una coppia di valori unitari.

$$ a=(1,0) \\ b=(0,1) $$

Poi scrivo il primo resto delle divisioni successive nella forma

$$ r_1 = a+b(-q_1)
\\ r_2 = b+r_2(-q_2)
\\ r_3 = r_2+r_3(-q_3)
\\ r_4 = r_3+r_2(-q_4)
\vdots $$

In pratica, dopo aver scritto la prima riga, sposto verso sinistra i componenti senza doverli ricalcolare ogni volta.

$$ 21 = (1,0)+(0,1)(-57) = (1,-57) $$

$$ 14 = (0,1)+(1,-57)(-1) = (-1,58) $$

$$ 7 = (1,-57)+(-1,58)(-1) = (2,-115) $$

Non ci sono altri resti positivi nelle divisioni successive.

L'ultimo risultato sono i coefficienti dell'identità di Bezout.

$$ j=2 \\ k=-115 $$

Quindi posso riscrivere l'identità nella forma

$$ MCD(2016,35)=7=2016 \cdot j + 35 \cdot k $$

$$ 2016 \cdot 2 + 35 \cdot (-115) $$

Ho così trovato il massimo comune divisore nella forma di combinazione lineare di due interi.

Verifica. Svolgo le moltiplicazioni della combinazione lineare per vedere se il risultato è 7. $$ 2016 \cdot 2 + 35 \cdot (-115) \\ 4032 - 4025 = 7 $$

E così via.