Bézouts identitet

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

${\displaystyle 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

${\displaystyle ax+by=c}$

har lösningar om och endast om ${\displaystyle \operatorname {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 ${\displaystyle (x_{0},y_{0})}$ är känd ges de andra lösningarna av:

${\displaystyle \left(x_{0}+{\frac {kb}{\operatorname {SGD} (a,b)}},y_{0}-{\frac {ka}{\operatorname {SGD} (a,b)}}\right)}$

där k är ett godtyckligt heltal.

Bevis

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

Via divisionsalgoritmen fås

${\displaystyle a=dq+r\quad {\text{med}}\quad 0\leq r<d.}$

Resten r är i ${\displaystyle S\cup \{0\}}$, eftersom

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

Eftersom d är det minsta positiva heltalet i S gäller således att r = 0 och d delar a. På samma vis fås att d delar b.

Nu, låt c vara en gemensam delare till a och b. Alltså finns ${\displaystyle u,v\in \mathbb {Z} }$ sådant att a = cu och b = cv. Det följer att

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

Alltså är c en delare till d och därför gäller det att c ≤ d.