Melegítésként kezdjük az 527 és 341 legnagyobb közös osztójának megtalálásával a standard euklideszi algoritmus segítségével:
A standard algoritmus tömör és egyszerű, és szép kis útmutatóul szolgál a kiterjesztett algoritmus megvalósításához.
A kibővített euklideszi algoritmushoz fogjuk a harmadik egyenletet (kékkel), kivonjuk mindkét oldalból a 155(1)-t, és egy kis átrendezést végzünk, hogy egy egyenértékű egyenletet kapjunk, ahol a 31 izolálva van.
A következőkben a 155-öt helyettesítjük 341-186(1)-gyel, amit a második egyenlet 155-re való feloldásával találhatunk meg, így a következőt kapjuk:
Most tisztázzuk ezt. Ügyeljünk arra, hogy a zárójelen keresztül osszuk el a negatív előjelet, és a 186 + 186 helyébe 186-2 lépjen.
Amint észrevehetjük, egyszerűen visszafelé haladunk a standard algoritmuson keresztül. Ezt a folyamatot még egyszer végig kell futtatnunk, hogy egy 527-et és 341-et tartalmazó egyenletet kapjunk, ami végül is a célunk.
Ezért cseréljük ki 186-ot 527 – 341(1)-re, ami az első egyenletből származik, amikor megoldjuk 186-ra.
Még egyszer egyszerűsítsük az egyenletet a 2 elosztásával és az 527 és 341 csoportba való egyesítésével.
A 31-et most már 527 és 341 lineáris kombinációjaként fejeztük ki. Elég király, nem?
Még a lineáris kombináció túloldalán lévő szám a legnagyobb közös osztó. Tehát ebben az esetben 31 az 527 és 341 legnagyobb közös osztója.
A kiterjesztett euklideszi algoritmus azért praktikus, mert a Bezout-azonosságot is megadja, valamint kiemeli a gcd-t.
Köszönjük az olvasást!
Köszönjük az olvasást!