Aloitetaan etsimällä lämmittelynä 527:n ja 341:n suurin yhteinen jakaja tavallisella euklidisella algoritmilla:

Vakioalgoritmi on ytimekäs ja suoraviivainen, ja se toimii mukavana pienenä oppaana laajennetun algoritmin toteuttamisessa.

Laajennettua euklidista algoritmia varten otamme kolmannen yhtälön (sinisellä), vähennämme molemmista puolista 155(1) ja teemme pienen uudelleenjärjestelyn saadaksemme vastaavan yhtälön, jossa 31 on eristetty.

Seuraavaksi korvaamme 155:n yhtälöllä 341-186(1), joka löytyy ratkaisemalla toinen yhtälö 155:n tilalle, jolloin saamme seuraavan: Muista jakaa negatiivinen merkki sulkujen läpi ja korvata 186 + 186 luvulla 186-2.

Kuten huomaatte, työskentelemme yksinkertaisesti taaksepäin vakioalgoritmin kautta. Meidän on käytävä tämä prosessi läpi vielä kerran, jotta saamme yhtälön, jossa on mukana 527 ja 341, mikä on viime kädessä tavoitteemme.

Tehdäksemme tämän korvaa 186 yhtälöllä 527 – 341(1), joka tulee ensimmäisestä yhtälöstä, kun ratkaistaan 186.

Yhtälöä yksinkertaistetaan taas jakamalla 2 ja yhdistämällä ryhmiin 527 ja 341.

Olemme nyt ilmaisseet 31:n 527:n ja 341:n lineaarikombinaationa. Aika siistiä, eikö?

Lisäksi lineaarikombinaation vastakkaisella puolella oleva luku on suurin yhteinen jakaja. Tässä tapauksessa 31 on siis 527:n ja 341:n suurin yhteinen jakaja.

Laajennettu euklidinen algoritmi on kätevä, koska se antaa Bezoutin identiteetin sekä korostaa gcd:n.

Kiitos lukemisesta!