Euklideszi algoritmus

Az euklideszi algoritmus egy számelméleti algoritmus, mellyel két szám legnagyobb közös osztója határozható meg.

Nevét az ókori görög matematikusról, Eukleidészről kapta.

Formális leírása

Legyen

$a,b \in \mathbb{Z}\setminus\{0\}$

Az algoritmus első lépésében maradékosan osztjuk $a$-t $b$-vel, a második lépésben $b$-t a maradékkal, majd az előbbi maradékot az új maradékkal, és így tovább, mindig az osztót a maradékkal.

Így a következő lépéssorozatot kapjuk:

• $a = b\cdot q_1 + r_1 \,$
• $b = r_1\cdot q_2 + r_2 \,$
• $r_1=r_2\cdot q_3 + r_3 \,$
• $\dots$

ahol

$|b|> r_1 > r_2 > r_3 > \dots \ge 0$

A maradék véges sok lépés után nulla lesz, hiszen amíg nem nulla, addig minden lépésben legalább eggyel csökkenni fog, tehát az utolsó lépésnél:

$r_{n-1} = r_n \cdot q_{n+1} \, (+ 0)$

A keresett legnagyobb közös osztó az $r_n$, azaz az utolsó nem nulla maradék.

Az algoritmus helyes működésének bizonyítása

• $a$ és $b$ bármely közös osztója osztja $r_1$-et is, hiszen

$r_1=a - b\cdot q_1$, és két szám közös osztója a különbségüket is osztja.

• Hasonlóképpen $b$ és $r_1$ bármely közös osztója osztja $a$-t is, hiszen

$a = b\cdot q_1 + r_1 \,$, és két szám közös osztója az összegüket is osztja.

Ezekből következik, hogy $a$ és $b$ közös osztói megegyeznek $b$ és $r_1$ közös osztóival, és így a legnagyobb közös osztójuk is azonos:

$(a,b)=(b,r_1) \,$

Ez a gondolatmenet minden lépésre ugyanígy megismételhető, azaz

$(a,b)=(b,r_1)=(r_1,r_2)=(r_2,r_3)=\dots=(r_{n-1},r_n)$

$(a,b)=(r_{n-1},r_n) \,$

$r_{n-1}$ és $r_n$ legnagyobb közös osztója már könnyen meghatározható, hiszen a fentebbiek szerint

$r_{n-1}=r_n \cdot q_{n+1}$, azaz

$r_n \mid r_{n-1} \,$

Vagyis $r_n$ osztja $r_{n-1}$-et, így a legnagyobb közös osztó maga $r_n$:

$(r_{n-1},r_n)=r_n \,$

$(a,b)=r_n \,$

Az algoritmus tehát helyesen működik.

Példa

A 360 és a 225 legnagyobb közös osztójának meghatározása az euklideszi algoritmussal:

$360=225\cdot 1+135 \,$

$225=135\cdot 1+90 \,$

$135=90\cdot 1+45 \,$

$90=45\cdot 2+0 \,$

Tehát a legnagyobb közös osztó a 45.

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.