Stelling van Bachet-Bézout

Uit Wikipedia, de vrije encyclopedie
Ga naar: navigatie, zoeken
Etienne Bézout
Claude Gaspard Bachet de Méziriac

De stelling van Bachet-Bézout is een stelling uit de getaltheorie, een deelgebied van de wiskunde. De stelling houdt in dat als d de grootste gemene deler is van twee gehele getallen a en b die ongelijk zijn aan 0, er dan gehele getallen x en y bestaan, zodat

 ax+by=d. \,

x en y heten hier bézoutgetallen of bézoutcoëfficiënten. Bovendien is d het kleinste (strikt) positief getal dat kan worden geschreven als ax + by.

Men kan de stelling van Bachet-Bézout ook als volgt formuleren: de lineaire vergelijking

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

heeft altijd een oplossing.

Geschiedenis[bewerken]

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

Algoritme[bewerken]

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 (x,y) een oplossing is, dan zijn daaruit oneindig veel oplossingen te construeren. Deze worden namelijk 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 van de stelling[bewerken]

Het bewijs is constructief. Met het uitgebreide algoritme van Euclides kan voor elke a en b de ggd 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.

De lineaire diofantische vergelijking ax + by = c heeft dan en slechts dan een gehele oplossing als c door de ggd(a,b) is te delen.

\Rightarrow

In dit geval is c=ggd(a,b), dus is c door de ggd(a,b) te delen.

\Leftarrow

Er is zeker een oplossing van de diofantische vergelijking ax + by = ggd(a,b), die is door het Algoritme van Euclides bepaald. Omdat nu is gegeven dat c een veelvoud van ggd(a,b) is, kunnen we de vergelijking links en rechts vermenigvuldigen met c / ggd(a,b).

Voorbeeld[bewerken]

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 \cdot  2 + 105 \cdot (-1) = 126 - 105 = 21.

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

Generalisatie[bewerken]

Algemeen geldt deze stelling 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 worden aangetoond.

Gevolgen[bewerken]

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

  1. De diofantische 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 ggd van a en b een deler is van c.
  2. Iedere gemeenschappelijke deler van a en b is ook deler van de ggd 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 ieder getal, dat tegelijk een veelvoud is van a en b, ook 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).

Voetnoten[bewerken]

  1. Tignol, Jean-Pierre, Galois' Theory of Algebraic Equations (Galoistheorie van de algebraïsche vergelijkingen), World Scientific, Singapore, 2001. ISBN 981-02-4541-6.