Bézouts identitet

Från Wikipedia
Hoppa till: navigering, sök

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.

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.