Il teorema di Bézout si dimostra come corollario di un altro teorema: il Teorema di Esistenza ed Unicità del Massimo Comun Divisore.
Teorema
Dati comunque a, b appartenenti a Z, non entrambi nulli, esiste ed è unico l’intero naturale d := MCD(a, b).
d coincide con il minimo intero positivo nell’insieme:
S := {ax + by : x ,y appartengono a Z, ax + by > 0}.
La dimostrazione di questo teorema viene lasciata da parte, e ritornando all’identità di Bézout questa può essere enunciata come corollario del precedente teorema:
Corollario (Identità di Bézout)
Dati comunque a, b appartenenti a Z, non entrambi nulli, esistono x0,y0 appartenenti a Z in modo che si abbia:
MCD(a, b) = ax0 + by0
Dimostrazione.
Per come è fatto l’insieme S (nell’enunciato del teorema precedente) d = min S, quindi d appartiene ad S e quindi esistono x0 e y0 tali che d = ax0 + by0.
Esiste anche una dimostrazione diretta di questo secondo teorema, basata sul fatto che il resto delle divisioni euclidee successive tra due numeri naturali può sempre essere scritto come combinazione del dividendo e del divisore. In dettaglio: supponiamo a < b, in modo che sia b = qa + r con q > 0; si ha allora anche ovviamente r = b – qa con r < a. Si divida ora a per r: si ottiene a = q’r + r’ e quindi r’ = a – q’r = (1 – qq’)a – q’b. Si prosegue allora dividendo r per r’, e così via.
Dal momento che a ogni divisione successiva il resto continua a diminuire, questo procedimento (noto come algoritmo di Euclide) termina solo quando si ottiene una divisione esatta (cioè con resto zero). Lasciamo al lettore il compito di verificare che il resto ottenuto nel penultimo “passo” è proprio il MCD di a e b, notando che qualsiasi numero che divide a e b divide anche tutti i resti ottenuti con questo algoritmo e che d’altra parte (come si vede “giocando” ancora con le espressioni delle divisioni effettuate) ogni resto ottenuto con questo algoritmo è multiplo del penultimo.