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

$ax + by = d$

och att d är det minsta heltalet där det finns heltalslösningar till ovanstående ekvation.

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)$ är känd ges de andra lösningarna av:

$\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.