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₁-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₁ 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₁ 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.