13.2 De stelling van Bachet-Bézout

Een stelling

De stelling van Bachet-Bézout 
Uit de getaltheorie komt de stelling van Bachet-Bézout, 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ëfficienten genoemd) bestaan, waarvoor geldt

 ax+by=d. , 
met |x|<|b| en |y|<|a|

Je kunt de stelling van Bachet-Bézout ook formuleren als dat de lineaire diophantische vergelijking

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

een oplossing heeft.

 

 

De stelling zegt ons dat als de ggd(a,b)=1 dat er een x en een y te vinden moeten zijn zodatax+by=1
Als de modus is dan zijn a en x dus elkaars inverse onder de vermenigvuldiging modulo b, immers
ax+by(mod y)=ax(mod y)=1

Terug nu naar opgave 10 van les 12. We passen het algoritme van Euclides toe: 

Dat betekent omdat ggd(6,5)=1 er een getal x en een getal te vinden moeten zijn zodatx*6+y*5=1 
In dit geval is het probleem makkelijk op te lossen, immers 6-1*5=1, dus neem x=1 en y=-1.

Evenzo omdat ggd(17,6)=1 moeten er een getal x en een getal te vinden zijn zodat x*17+y*6=1.
en ook dat is met een beetje proberen wel op te lossen, want -1*17+3*6=1, dus x=-1 en y=3