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 $r n$ 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 $r n = (a, b)$ .

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