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
met |x|<|b| en |y|<|a|
Je kunt de stelling van Bachet-Bézout ook formuleren als dat de lineaire diophantische vergelijking
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 b 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 y 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 y 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