Bezout identitet

Sats: Låt $d$ vara den största gemensamma delaren till heltalen $a$ och $b.$ Alla linjärkombinationer av $a$ och $b$, med heltalskoefficienter,  är multipler av $d$; speciellt existerar det heltalskoefficienter $(x,y)$ sådana att $ax+by=d.$

Bevis. Låt $S$ beteckna mängden av alla linjärkombinationer, med heltalskoefficienter, av heltalen $a$ och $b.$ 

    $S=\{ax+by : x,y\in\mathbb{Z}\}.$

Detta är en icke-tom mängd eftersom den innehåller heltalet $a = a\cdot 1 + b\cdot 0$ och därför innehåller den ett minsta element ($\delta$), enligt Välordningsprincipen. Följande resonemang visar att $\delta$ är en gemensam delare till $a$ och $b.$

Använd Euklides algoritm för att utföra divisionen $a/\delta$; algoritmen ger två heltal $(f,r)$ sådana att $a = \delta f + r$ där resten ($r$) uppfyller olikheterna $0\leq r < \delta.$ Eftersom $\delta \in S$ finns det två heltal $(u,v)$ sådana att $\delta = au+bv$ vilket medför att resten kan skrivas som en linjärkombination av $a$ och $b.$ Då $r\in S$ måste det vara större än $\delta$, eftersom $\delta$ ju är det minsta elementet i $S.$ Men kravet på $r$ var ju $r<\delta$, vilket visar att den enda möjligheten är att $r=0$, det vill säga $\delta$ är en delare till $a.$ På samma sätt visas att $\delta$ är en delare till $b.$

Låt heltalet $e$ vara en annan gemensam delare till $a$ och $b$, så att det finns två heltal $(\alpha,\beta)$ sådana att $a=e\alpha$ och $b=e\beta.$ Då är $e$ en delare till $\delta$ också, eftersom $\delta = au+bv = e\cdot (\alpha u+\beta v)$, vilket visar att $\delta$ är den största gemensamma delaren ($d$) till $a$ och $b$. 

    $\delta = d.$

Låt $ax+by$ vara ett godtyckligt element i mängden $S.$ Då $d$ är en gemensam delare till $a$ och $b$ finns det två heltal $(\lambda, \mu)$ sådana att $a=d\lambda$ och $b=d\mu$ vilket visar att varje linjärkombination av $a$ och $b$ är en multipel av $d.$