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
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
har lösningar om och endast om .
Algoritm
[redigera | redigera wikitext]Talen x och y ovan kan beräknas genom den utökade Euklides algoritm, men lösningarna är inte unika. Om en lösning är känd ges de andra lösningarna av:
där k är ett godtyckligt heltal.
Bevis
[redigera | redigera wikitext]Givet två nollskilda heltal a och b, låt och . 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 . 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
Resten r är i , eftersom
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 sådant att a = cu och b = cv. Det följer att
Alltså är c en delare till d och därför gäller det att c ≤ d.