Lad os starte med at finde den største fælles divisor af 527 og 341 ved hjælp af den euklidiske standardalgoritme som en opvarmning:

Standardalgoritmen er kortfattet og ligetil og vil tjene som en fin lille vejledning til implementering af den udvidede algoritme.

For den udvidede euklidiske algoritme tager vi den tredje ligning (med blå farve), trækker 155(1) fra begge sider og laver en lille omlægning for at lave en tilsvarende ligning, hvor 31 er isoleret.

Næst erstatter vi 155 med 341-186(1), som vi kan finde ved at løse den anden ligning for 155, hvilket giver os følgende:

Nu skal vi rydde op i det her. Sørg for at fordele det negative tegn gennem parentesen, og erstat 186 + 186 med 186-2.

Som du måske har bemærket, arbejder vi os simpelthen baglæns gennem standardalgoritmen. Vi skal igennem denne proces endnu en gang for at få en ligning med 527 og 341, hvilket i sidste ende er vores mål.

For at gøre dette skal vi erstatte 186 med 527 – 341(1), som kommer fra den første ligning, når vi løser for 186.

Videre forenkle ligningen ved at fordele 2 og kombinere i grupper af 527 og 341.

Vi har nu udtrykt 31 som en linearkombination af 527 og 341. Ret sejt, ikke?

Dertil kommer, at tallet på den modsatte side af linearkombinationen er den største fælles divisor. Så i dette tilfælde er 31 den største fælles divisor af 527 og 341.

Den udvidede euklidiske algoritme er praktisk, fordi den både giver Bezout’s identitet og fremhæver gcd.

Tak for læsning!