] >
Een belangrijke eigenschap met vele gevolgen is de volgende stelling.
Bewijs. In: ”Getallen”, Epsilon deel 65, uitgegeven door Epsilon-Uitgaven. □
Met een kleine uitbreiding van het algoritme van Euclides zijn de en snel uit te rekenen. Zie het einde van deze paragraaf.
We leiden nu eerst enkele gevolgen af van bovenstaande stelling.
Bewijs.
Zij een gemene deler van en . We nemen aan dat . Dan zijn er zo dat . Uit en volgt dat en dus ook .
Dus is iedere gemene deler van en een deler van de grootste gemene deler van en . □
7.32 Voorbeeld. De gemene delers van en bepaalden we al eerder. Het zijn de getallen , , , . Dit zijn juist de delers van , de ggd van en .
Bewijs.
Stel en . Er zijn zodat . Dan . Omdat en , geldt dus ook .
Dus: als en , dan . □
Nog enkele consequenties van Stelling 7.30.
Bewijs. In: ”Getallen”, Epsilon deel 65, uitgegeven door Epsilon-Uitgaven. □
Bewijs. Als een gemene deler is van en , dan is een gemene deler van en , en dus een deler van . Dus in het bijzonder voor :
Er zijn gehele getallen met . Dan ook . Daaruit volgt:
7.36 Propositie. Laat de kleinste noemer van een rationaal getal zijn. Dan is iedere noemer van een veelvoud van .
Bewijs. In: ”Getallen”, Epsilon deel 65, uitgegeven door Epsilon-Uitgaven. □
Als met , dan zijn de noemers van dus veelvouden van . Hieruit volgt dat als er een is met en . Breuken met positieve noemer en waarvan teller en noemer relatief priem zijn noemt men wel breuken in gereduceerde vorm.
De eigenschappen van de grootste gemene deler gebruiken we voor het oplossen van Diophantische vergelijkingen van het type
waarbij . Het gaat erom alle oplossingen te bepalen.
Diophantische vergelijkingen zijn vergelijkingen waarbij gehele oplossingen worden gevraagd. Ze zijn zo genoemd naar Diophantus. Hij is bekend geworden door zijn boek Arithmetica over het oplossen van algebraïsche vergelijkingen en getaltheorie. Van zijn leven is vrijwel niets bekend. Hij leefde van ongeveer 200 tot ongeveer 284.
7.37 Stelling. Laten en gehele getallen zijn met en niet beide . Dan is de Diophantische vergelijking
oplosbaar dan en slechts dan als .
Bewijs.
Stel de vergelijking is oplosbaar en met is een oplossing, ofwel
Dan, omdat en , hebben we ook .
Dus: als de vergelijking oplosbaar is, dan geldt .
Stel dat , zeg met . Uit Stelling 7.30 volgt dat er getallen zijn zo dat
Dan ook
en dus is een oplossing van .
Dus: als , dan is de vergelijking oplosbaar. □
7.38 Voorbeeld. De vergelijking
is niet oplosbaar, want . Daarentegen is de vergelijking
wel oplosbaar want . Hebben we een oplossing van , dan krijgen we door met te vermenigvuldigen een oplossing van . Een oplossing van is , hetgeen ook een oplossing is van ; een oplossing van is dan . We gaan nu alle met bepalen zo dat .
Stel voldoen aan . Dan
ofwel
Omdat volgt uit Propositie 7.33 dat , dus is er een zo dat , ofwel
Dan , ofwel
Oplossingen van zijn dus van de vorm
Anderzijds zijn dit ook allemaal oplossingen. Dus hebben we alle oplossingen van de vergelijking bepaald.
7.39 Definitie. Laten en gehele getallen zijn. We zeggen dat een gemeen veelvoud is van en als
Als en , dan zijn er positieve gemene veelvouden van en . De kleinste onder de positieve gemene veelvouden van en noemen we het kleinste gemene veelvoud van en ; notatie: . Deze definiëren we alleen voor en .
7.40 Voorbeeld. De positieve veelvouden van zijn , , , , , etc. De kleinste die tevens een veelvoud is van is . Dus is het kleinste gemene veelvoud van en .
Bewijs. Zij en . Omdat en volgt uit Lemma 7.34 en Propositie 7.35 dat , ofwel . Uit blijkt dat een gemeen veelvoud is van en . Dus , zodat . Met volgt nu dat . □
Bewijs. In: ”Getallen”, Epsilon deel 65, uitgegeven door Epsilon-Uitgaven. □
Volgens Lemma 7.27 kan het bepalen van de getallen en zo dat voor worden teruggebracht tot het bepalen van getallen en met , waarbij en . Door steeds bij te houden hoe iedere nieuwe rest die optreedt bij het algoritme van Euclides een combinatie is van het oorspronkelijke tweetal getallen vinden we uiteindelijk zo’n combinatie voor de grootste gemene deler. We voeren dit uit voor en :
65 | 23 | 19 | 4 | 3 | 1 | 0 |
2 | 1 | 4 | 1 | 3 | ||
1 | 0 | 1 | -1 | 5 | -6 | 23 |
0 | 1 | -2 | 3 | -14 | 17 | -65 |
Hierbij is links begonnen. In de tweede rij staan de quotiënten: het getal daarboven is de nieuwe rest: wordt verkregen door van af te trekken. In de onderste twee rijen is ieder nieuw getal op dezelfde manier een combinatie van de twee vorige getallen. In dit voorbeeld is de grootste gemene deler . Waren we met en begonnen, dan waren de getallen in de bovenste rij alle keer zo groot.
Het algoritme is met Python eenvoudig uit te voeren.