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
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 Givet två nollskilda heltal och , låt och . Mängden är icketom eftersom exempelvis eller är i mängden (tag och ). Enligt välordningsprincipen har ett minsta element . För att visa att är den största gemensamma delaren till och visas att delar båda talen samt att är ett positivt heltal som delar och så gäller .
Via divisionsalgoritmen fås
Resten är i , eftersom
Eftersom är det minsta positiva heltalet i gäller således att och delar . På samma vis fås att delar .
Nu, låt vara en gemensam delare till och . Alltså finns sådant att och . Det följer att
Alltså är en delare till och därför gäller det att .
Kategori:Talteori