Stelling van Bachet-Bézout

De stelling van Bachet-Bézout is een stelling uit de getaltheorie, een deelgebied van de wiskunde, die inhoudt dat als d de grootste gemene deler van twee gehele getallen a en b ongelijk aan 0 is, dat er dan gehele getallen x en y (Bézoutgetallen of Bézoutcoëfficiënten genoemd) bestaan. waar |x|<|b| en |y|<|a|, zodat we kunnen schrijven

$ax+by=d. \,$

waar d het kleinste positieve getal is, waarvoor er geheeltallige oplossingen x en y voor deze vergelijking bestaan.

Men kan de stelling van Bachet-Bézout ook kortweg formuleren als dat de lineaire diophantische vergelijking

$ax+by=\mathrm{ggd}(a,b).\,\!$

een oplossing heeft.

Geschiedenis

De stelling van Bachet-Bézout is mede vernoemd naar Étienne Bézout, die de stelling bewees voor veeltermen. Maar de stelling was al eerder voor de gehele getallen geponeerd door de Franse wiskundige Claude Gaspard Bachet de Méziriac.

Algoritme

De Bézoutgetallen x en y (zie hierboven) kunnen worden bepaald met behulp van het uitgebreide algoritme van Euclides. Ze zijn echter niet uniek. Als een oplossing wordt gegeven door (x,y), dan zijn er oneindig veel oplossingen. Deze worden gegeven door

$\left\{\left . \left(x+\frac{kb}{\mathrm{ggd(a,b)}},\ y-\frac{ka}{\mathrm{ggd(a,b)}}\right) \right | k \in \mathbb{Z} \right\}.$

Bewijs

Het bewijs is constructief. Met het uitgebreide algoritme van Euclides kan voor elke a en b de g.g.d. uitgedrukt worden als een gehele lineaire combinatie van resultaten die zelf weer gehele lineaire combinaties zijn van andere tussenresultaten. In een eindig aantal stappen laten die tussenresultaten zich uitdrukken als een gehele lineaire combinatie van a en b.

Voorbeeld

De grootste gemene deler van 63 en 105 is 21. De stelling Bachet-Bézout beweert dat er een geheeltallige oplossing moet bestaan voor x en y in de onderstaande vergelijking:

63x + 105y = 21.

Een van de oplossingen is x = 2 en y = –1; inderdaad is

63×2 + 105×(–1) = 126 – 105 = 21.

Andere oplossingen zijn x=–3, y=2 en x=7, y=–4

Generalisatie

Deze stelling kan ook gegeneraliseerd worden voor een eindige verzameling getallen $a_i$. Er geldt dan dat:

$\forall a_1, a_2,\ldots ,a_n \in \mathbb{Z}\ \ \exists \alpha_1, \alpha_2,...,\alpha_n \in \mathbb{Z}: \mathrm{ggd}(a_1,a_2,...,a_n)= \alpha_1 a_1 + \alpha_2 a_2 + ...+\alpha_n a_n$.

Dit kan met volledige inductie aangetoond worden.

Gevolgen

Deze stelling heeft enkele belangrijke gevolgen. Deze worden hier niet bewezen, maar ze volgen vrijwel allemaal rechtstreeks uit de stelling.

1. De Diophantische vergelijking $ax+by=c$ in de variabelen x en y, dus met gehele a, b, c, x en y heeft alleen dan oplossingen als de g.g.d. van a en b een deler is van c.
2. Elke gemene deler van a en b is ook deler van de g.g.d. van a en b.
3. Voor alle gehele $a_1,a_2,...,a_n\,$ geldt dat $\mathrm{ggd}(\mathrm{ggd}(a_1,a_2),a_3,...,a_n) = \mathrm{ggd}(a_1,a_2,a_3,...,a_n)\,$
4. Voor alle a, b en c geldt dat ggd(a,bc) een deler is van het product ggd(a,b)×ggd(a,c). In het bijzonder geldt dus dat ggd(a,bc) = ggd(a,c) als a en b relatief priem zijn.
5. Voor elke natuurlijke n en gehele a is er een b zodat ab mod n = ggd(a,n) mod n.
6. Voor alle c en delers a en b van c geldt dat ab/ggd(a,b) ook een deler is van c. In het bijzonder geldt dat elk gemeen veelvoud van a en b een veelvoud is van ab/ggd(a,b). Het kleinste gemene veelvoud, kgv(a,b), van a en b is dus gelijk aan ab/ggd(a,b).

Zie ook

• Uitgebreid algoritme van Euclides