Bézouts identitet

Mall:Källor Bézouts identitet är en sats inom talteori uppkallad efter Étienne Bézout som säger att för två heltal a och b med största gemensamma delare d går det att hitta heltal x och y så att

$ax+by=d$

och att d är det minsta positiva heltalet som kan skrivas på formen ax + by. Denna identitet förklarar även varför en linjär diofantisk ekvation på formen

$ax+by=c$

har lösningar om och endast om $\mathrm{SGD}(a,b)|c$.

Algoritm

Talen x och y ovan kan beräknas genom den utökade Euklides algoritm, men lösningarna är inte unika. Om en lösning $(x_0,y_0)$ är känd ges de andra lösningarna av:

$(x_0+\frac{kb}{\mathrm{SGD}(a,b)},y_0-\frac{ka}{\mathrm{SGD}(a,b)})$

där k är ett godtyckligt heltal.

Bevis

Givet två nollskilda heltal Mall:Mvar och Mall:Mvar, låt $S=\{ax+by\mid ax+by>0$ och $x,y\in \mathbb{Z}\}$. Mängden Mall:Mvar är icketom eftersom exempelvis Mall:Mvar eller Mall:Mvar är i mängden (tag Mall:Math och Mall:Math). Enligt välordningsprincipen har Mall:Mvar ett minsta element $d=as+bt$. För att visa att Mall:Mvar är den största gemensamma delaren till Mall:Mvar och Mall:Mvar visas att Mall:Mvar delar båda talen samt att Mall:Mvar är ett positivt heltal som delar Mall:Mvar och Mall:Mvar så gäller Mall:Math.

Via divisionsalgoritmen fås

$a=dq+r\text{med}0\le r<d.$

Resten Mall:Mvar är i $S\cup \{0\}$, eftersom

$\begin{array}{cc}r& =a-qd\\ & =a-q(as+bt)\\ & =a(1-qs)-bqt.\end{array}$

Eftersom Mall:Mvar är det minsta positiva heltalet i Mall:Mvar gäller således att Mall:Math och Mall:Mvar delar Mall:Mvar. På samma vis fås att Mall:Mvar delar Mall:Mvar.

Nu, låt Mall:Mvar vara en gemensam delare till Mall:Mvar och Mall:Mvar. Alltså finns $u,v\in \mathbb{Z}$ sådant att Mall:Math och Mall:Math. Det följer att

$\begin{array}{cc}d& =as+bt\\ & =cus+cvt\\ & =c(us+vt).\end{array}$

Alltså är Mall:Mvar en delare till Mall:Mvar och därför gäller det att Mall:Math.