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 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
... | ... |
alakú sorozatot kapunk, ahol . Így az rn sorozat véges kell hogy legyen, és valamely -re . Tehát
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.