Bézouts identitet

 Den här artikeln behöver källhänvisningar för att kunna verifieras. (2020-06)
Åtgärda genom att lägga till pålitliga källor (gärna som fotnoter). Uppgifter utan källhänvisning kan ifrågasättas och tas bort utan att det behöver diskuteras på diskussionssidan.

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

a x + b y = d {\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

a x + b y = c {\displaystyle ax+by=c}

har lösningar om och endast om SGD ⁡ ( a , b ) | c {\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 ( x 0 , y 0 ) {\displaystyle (x_{0},y_{0})} är känd ges de andra lösningarna av:

( x 0 + k b SGD ⁡ ( a , b ) , y 0 − k a SGD ⁡ ( a , b ) ) {\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 S = { a x + b y ∣ a x + b y > 0 {\displaystyle S=\{ax+by\mid ax+by>0} och x , y ∈ Z } {\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 d = a s + b t {\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

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

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

r = a − q d = a − q ( a s + b t ) = a ( 1 − q s ) − b q t . {\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 u , v ∈ Z {\displaystyle u,v\in \mathbb {Z} } sådant att a = cu och b = cv. Det följer att

d = a s + b t = c u s + c v t = c ( u s + v t ) . {\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.