Euklideszi algoritmus

A Wikipédiából, a szabad enciklopédiából

Az euklideszi algoritmus[1] 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[szerkesztés | forrásszöveg szerkesztése]

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.

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.

Az algoritmus helyes működésének bizonyítása[szerkesztés | forrásszöveg szerkesztése]

  • 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[szerkesztés | forrásszöveg szerkesztése]

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.

Programkód[szerkesztés | forrásszöveg szerkesztése]

Alábbiakban láthatunk egy C programnyelven írt megvalósítást:

 
#include <stdio.h>
int lnko(int a, int b){
    int temp;
    while(b>0){
        temp = b;
        b = a%b;
        a = temp;
    }
    return a;
}
int main(void){
    int s1, s2;
 
    printf("szam1 szam2: ");
    scanf("%d %d", &s1, &s2);
 
    printf("lnko(%d, %d)=%d", s1, s2, lnko(s1, s2));
    return 0;
}

Jegyzetek[szerkesztés | forrásszöveg szerkesztése]

  1. A matematikus nevének szabatos átírása Eukleidész volna, tehát a szerkezet eukleidészi algoritmus, de ebben a kifejezésben hagyományosan rögzült euklideszi alakban (lásd például Püthagorasz, de Pitagorasz-tétel stb.).

Hivatkozások[szerkesztés | forrásszöveg szerkesztése]

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