Laten we beginnen met het vinden van de grootste gemene deler van 527 en 341 met behulp van het standaard algoritme van Euclides, als opwarmertje:

Het standaard algoritme is beknopt en eenvoudig en zal dienen als een mooie kleine gids voor de implementatie van het uitgebreide algoritme.

Voor het uitgebreide algoritme van Euclides nemen we de derde vergelijking (in blauw), trekken 155(1) van beide kanten af, en herschikken de vergelijking om een equivalente vergelijking te maken waarin 31 geïsoleerd is.

Nogmaals vervangen we 155 door 341-186(1), die gevonden kan worden door de tweede vergelijking op te lossen voor 155, zodat we het volgende krijgen:

Nu gaan we dit opruimen. Verdeel het negatieve teken door de haakjes en vervang 186 + 186 door 186-2.

Zoals u ziet, werken we gewoon achteruit door het standaardalgoritme. We moeten dit proces nog een keer doorlopen om een vergelijking met 527 en 341 te krijgen, wat uiteindelijk ons doel is.

Om dit te doen, vervangen we 186 door 527 – 341(1), wat uit de eerste vergelijking komt wanneer we voor 186 oplossen.

Vergemakkelijk de vergelijking opnieuw door de 2 te verdelen en te combineren in groepen van 527 en 341.

We hebben nu 31 uitgedrukt als een lineaire combinatie van 527 en 341. Best cool, hè?

Daarnaast is het getal aan de andere kant van de lineaire combinatie de grootste gemene deler. In dit geval is 31 dus de grootste gemene deler van 527 en 341.

Het uitgebreide algoritme van Euclides is handig omdat het zowel de Identiteit van Bezout als de gcd oplevert.

Bedankt voor het lezen!