Identità di Bézout

L’algoritmo di Euclide non serve solo a trovare il MCD: ripercorrendolo “all’indietro” si scopre un fatto notevole, l’identità di Bézout.

Teorema — Identità di Bézout

Per ogni coppia di interi $a,b$ (non entrambi nulli) esistono due interi $x,y$ tali che $a x + b y = \text{MCD}(a,b).$ In particolare, $a$ e $b$ sono coprimi ($\text{MCD}=1$) se e solo se esistono $x,y$ con $ax+by=1$.

I coefficienti $x,y$ si trovano risalendo le divisioni dell’algoritmo di Euclide, sostituendo di volta in volta il resto con la sua espressione.

Esempio: 84 e 60

Applichiamo Euclide: $84 = 1\cdot 60 + 24, \qquad 60 = 2\cdot 24 + 12, \qquad 24 = 2\cdot 12 + 0.$

Quindi $\text{MCD}(84,60)=12$. Ora risaliamo, partendo dalla penultima riga: $12 = 60 - 2\cdot 24.$ Ma dalla prima riga $24 = 84 - 1\cdot 60$; sostituiamo: $12 = 60 - 2\,(84 - 60) = 3\cdot 60 - 2\cdot 84.$

Abbiamo trovato $x=-2$, $y=3$: $-2\cdot 84 + 3\cdot 60 = -168 + 180 = 12 = \text{MCD}(84,60). \checkmark$

A che serve

L’identità di Bézout è la chiave di molti risultati: dimostra il lemma di Euclide (se un primo divide un prodotto, divide uno dei fattori), permette di risolvere le equazioni diofantee $ax+by=c$ e di calcolare gli inversi modulari alla base della crittografia RSA.

Collegamenti

Argomenti: Numeri e operazioni
Concetti: Algoritmo di Euclide · Identità di Bézout · Massimo comun divisore (MCD)
Competenze: Dimostrare
Persone: Étienne Bézout · Euclide