Euklidészi algoritmus

A Wikipédiából, a szabad lexikonból.

Tegyük fel, hogy x és y pozitív egész számok, és szeretnénk kiszámítani a legnagyobb közös osztójuk értékét. Ekkor vehetjük hasznát az euklidészi algoritmusnak.

Ha valamelyik szám osztja a másikat, mondjuk x | y, akkor (x,y) = x.

Ha nem osztják egymást, és mondjuk x a nagyobbik, osszuk el maradékosan y-nal: x = y * q + r, ahol 0 < r < y. Ekkor (x,y) = (y,r), így a problémát visszavezettük két kisebb szám legnagyobb közös osztójának meghatározására.

Ezt a lépést csak véges sokszor hajthatjuk végre, hiszen a számok mindvégig nem negatív egészek és folyamatosan csökkennek. Végül az utolsó, 0-tól különböző maradék a legnagyobb közös osztó.

[szerkesztés] Az euklidészi algoritmus formális leírása

Tekintsük az a,b \in \mathbb{Z}, b \neq 0 számpárt. Osszuk maradékosan a-t b-vel, majd b-t a maradékkal, majd a maradékot az új maradékkal, és így tovább, mindig az osztót a maradékkal. Ekkor egy

a = b q_1 + r_1 \, 0 \le r_1 < |b|
b = r_1 q_2 + r_2 \, 0 \le r_2 < r_1
r_1=r_2q_3+r_3 \, 0 \le r_3 < r_2
... ...


alakú sorozatot kapunk, ahol 0 \le \dots < r_3 < r_2 < r_1 < |b|. Így az rn sorozat véges kell hogy legyen, és valamely N \in \mathbb{N}-re r_N = 0 \,. Tehát

r_{N-2} = r_{N-1} q_{N-1} + r_N \quad r_N=0

Jelöljük n-nel az utolsó nem nulla maradék indexét (n = N − 1). Állítjuk, hogy ekkor rn = (a,b).

A legnagyobb közös osztó osztja a-t és b-t is, tehát r1 kreálásának módja miatt azt is. Mivel b-t és r1-et is osztja, hasonlóan r2-t is kell neki. Általánosan ha ri-t és ri + 1-et osztja, akkor így ri + 2-t is. Teljes indukcióval beláttuk tehát, hogy (a,b) | rn. Visszafelé haladva pedig tudjuk, hogy rn | rn − 1. Ekkor azonban rn | rn - 2, s általánosan ha rn | ri és rn | ri − 1, akkor rn | ri − 2. Így visszafelé elértük, hogy rn | a,b, azaz rn | (a,b). Ha ezt összevetjük azzal, hogy (a,b) | rn, akkor látható, hogy rn = (a,b). Az algoritmus tehát működik.

[szerkesztés] Hivatkozások

  • D.E.Knuth: A számítógépprogramozás művészete 1. Alapvető algoritmusok, Műszaki Könyvkiadó, Budapest, 2. kiadás, 1994, ISBN 963 1600750, 25-34. o.