Stelling van Bachet-Bézout

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

${\displaystyle ax+by=d.}$

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

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

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

heeft altijd een oplossing.

Geschiedenis

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

De bézoutgetallen ${\displaystyle x}$ en ${\displaystyle y}$ kunnen worden bepaald met behulp van het uitgebreide algoritme van Euclides, maar ze zijn niet uniek. Als het paar ${\displaystyle (x,y)}$ een oplossing is, dan zijn daaruit oneindig veel oplossingen te construeren. Deze worden namelijk gegeven door

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

Voorbeeld

De grootste gemene deler van 63 en 105 is 21. Er is dan volgens de stelling Bachet-Bézout een geheeltallige oplossing voor ${\displaystyle x}$ en ${\displaystyle y}$ in de vergelijking ${\displaystyle 63x+105y=21.}$ Een van de oplossingen is ${\displaystyle x=2}$ en ${\displaystyle y=-1}$. Inderdaad is ${\displaystyle 63\cdot 2+105\cdot (-1)=126-105=21.}$ Andere oplossingen zijn ${\displaystyle x=-3,y=2}$ en ${\displaystyle x=7,y=-4}$.

Bewijs

Generalisatie

Algemeen zegt deze stelling dat er voor elk eindig aantal getallen ${\displaystyle a_{1},a_{2},\ldots ,a_{n}}$ gehele getallen ${\displaystyle \alpha _{1},\alpha _{2},\ldots ,\alpha _{n}\in \mathbb {Z} }$ zijn, zodat:

${\displaystyle \mathrm {ggd} (a_{1},a_{2},\ldots ,a_{n})=\alpha _{1}a_{1}+\alpha _{2}a_{2}+\ldots +\alpha _{n}a_{n}}$

Dit kan met volledige inductie worden aangetoond.

Gevolgen

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

1. De diofantische vergelijking ${\displaystyle a<x+by=c}$ in de variabelen ${\displaystyle x}$ en ${\displaystyle y}$, dus met gehele ${\displaystyle a,b,c,x}$ en ${\displaystyle y}$ heeft alleen dan oplossingen als de ggd van ${\displaystyle a}$ en ${\displaystyle b}$ een deler is van ${\displaystyle c.}$
2. Wanneer twee getallen ${\displaystyle a}$ en ${\displaystyle b}$ door een derde getal ${\displaystyle c}$ zijn te delen, is ook ${\displaystyle \mathrm {ggd} (a,b)}$ door ${\displaystyle c}$ te delen.
3. Voor alle gehele ${\displaystyle a_{1},a_{2},\dots ,a_{n}}$ geldt dat ${\displaystyle \mathrm {ggd} (\mathrm {ggd} (a_{1},a_{2}),a_{3},\ldots ,a_{n})=\mathrm {ggd} (a_{1},a_{2},a_{3},\ldots ,a_{n})}$
4. Voor alle ${\displaystyle a,b}$ en ${\displaystyle c}$ geldt dat het product ${\displaystyle \mathrm {ggd} (a,b)\cdot \mathrm {ggd} (a,c)}$ door ${\displaystyle \mathrm {ggd} (a,bc)}$ kan worden gedeeld. In het bijzonder geldt dat ${\displaystyle \mathrm {ggd} (a,bc)=\mathrm {ggd} (a,c)}$ als ${\displaystyle a}$ en ${\displaystyle b}$ relatief priem zijn.
5. Voor elke natuurlijke ${\displaystyle n}$ en gehele ${\displaystyle a}$ is er een ${\displaystyle b}$ zodat ${\displaystyle ab=\mathrm {ggd} (a,n){\pmod {n}}.}$
6. Voor alle ${\displaystyle c}$ en daarbij alle ${\displaystyle a}$ en ${\displaystyle b}$, zodat ${\displaystyle c}$ door ${\displaystyle a}$ en ${\displaystyle b}$ kan worden gedeeld, geldt dat ${\displaystyle c}$ ook door ${\displaystyle ab/\mathrm {ggd} (a,b)}$ kan worden gedeeld. In het bijzonder geldt dat ieder getal dat tegelijk een veelvoud is van ${\displaystyle a}$ en ${\displaystyle b,}$ ook een veelvoud is van ${\displaystyle ab/\mathrm {ggd} (a,b)}$. Het kleinste gemene veelvoud ${\displaystyle \mathrm {kgv} (a,b)}$ van ${\displaystyle a}$ en ${\displaystyle b}$ is dus gelijk aan ${\displaystyle ab/\mathrm {ggd} (a,b)}$.