Vi börjar med att hitta den största gemensamma divisorn för 527 och 341 med hjälp av den vanliga euklidiska algoritmen som uppvärmning:

Standardalgoritmen är kortfattad och enkel och kommer att fungera som en trevlig liten guide för att implementera den utökade algoritmen.

För den utvidgade euklidiska algoritmen tar vi den tredje ekvationen (i blått), subtraherar 155(1) från båda sidorna och gör lite omarrangemang för att få fram en likvärdig ekvation där 31 är isolerad.

Nästan ersätter vi 155 med 341-186(1), som kan hittas genom att lösa den andra ekvationen för 155, vilket ger oss följande:

Nu ska vi rensa upp detta. Se till att fördela det negativa tecknet genom parentesen och ersätt 186 + 186 med 186-2.

Som du kanske märker jobbar vi oss helt enkelt bakåt genom standardalgoritmen. Vi måste gå igenom denna process en gång till för att få fram en ekvation med 527 och 341, vilket i slutändan är vårt mål.

För att göra detta byter vi ut 186 mot 527 – 341(1), vilket kommer från den första ekvationen när vi löser för 186.

Förenkla återigen ekvationen genom att fördela 2 och kombinera i grupper om 527 och 341.

Vi har nu uttryckt 31 som en linjär kombination av 527 och 341. Ganska häftigt, eller hur?

För övrigt är talet på motsatt sida av linjärkombinationen den största gemensamma divisorn. Så i det här fallet är 31 den största gemensamma divisorn av 527 och 341.

Den utvidgade euklidiska algoritmen är praktisk eftersom den ger Bezout-identiteten och lyfter fram gcd.

Tack för att du läste!