0 svar
95 visningar
Albiki 5320
Postad: 28 aug 2020 Redigerad: 28 aug 2020

Bezout identitet

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

Bevis. Låt SS beteckna mängden av alla linjärkombinationer, med heltalskoefficienter, av heltalen aa och b.b. 

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

Detta är en icke-tom mängd eftersom den innehåller heltalet a=a·1+b·0a = 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 aa och b.b.

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

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

    δ=d.\delta = d.

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

Svara Avbryt
Close