Stelling van Bachet-Bézout
Van Wikipedia
Inhoud |
[bewerk] Stelling
In woorden: Zijn a en b gehele getallen, dan bestaan nog twee gehele getallen, α en β zodat de grootste gemene deler van a en b gelijk is aan de som van a keer α en b keer β.
[bewerk] Bewijs
Uit het algoritme van Euclides volgt dat voor elke i uit de verzameling {1, 2, 3, ... k} geldt dat:
bi = ri − 1 = ai − 1 − qi − 1bi − 1
ri − 1 = de rest tijdens de ide herhaling van de lus qi − 1 = het quotiënt van de geheeltallige deling tijdens de ide herhaling van de lus
Door inductie toe te passen vind je dat elke ai en bi kan worden geschreven als een gehele lineaire combinatie van a en b. Hieruit volgt dat we ook bk als een dergelijke combinatie kunnen schrijven.
[bewerk] Generalisatie
Deze stelling kan ook gegeneraliseerd worden voor een eindige verzameling getallen ai. Er geldt dan dat:
met.
Dit is met inductie gemakkelijk aan te tonen.
[bewerk] Gevolgen
Deze stelling heeft enkele belangrijke gevolgen. Deze worden hier niet bewezen maar volgen vrijwel allemaal rechtstreeks uit de stelling.
- Voor elke geldt dat de vergelijking ax + by = c in de variabelen x en y oplossingen heeft in als en slechts als ggd(a,b)|c.
- Elke gemene deler van a en b deelt ook ggd(a,b).
- Voor alle geldt dat ggd(ggd(a1,a2),a3,...,an) = ggd(a1,a2,a3,...,an)
- Voor alle geldt dat ggd(a,bc) | ggd(a,b) * ggd(a,c) (In het bijzonder geldt dus dat ggd(a,bc)=ggd(a,c) als a en b onderling ondeelbaar zijn.)
- Zij . Voor elke bestaat er een zodat xy mod n = ggd(x,n) mod n.
- Voor alle met a | c,b | c en geldt dat . (In het bijzonder geldt dat elk gemeen veelvoud van a en b een veelvoud is van ab/d. Dus het kleinste gemene veelvoud kgv(a,b) is gelijk aan ab/ggd(a,b).