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

Az utolsó nem nulla maradék lesz a legnagyobb közös osztó.

Bizonyítás[szerkesztés | forrásszöveg szerkesztése]

Első lépésként lássuk be, hogy az algoritmus véges sok lépés után véget ér. Ennek főleg gyakorlati szempontok miatt van szerepe. Mivel az euklideszi osztás során a kisebb, mint az osztó abszolútértéke, a maradékok szigorúan monoton csökkenő sorozatot alkotnak a természetes számok halmazában, így a sorozat utolsó tagja biztosan nulla, mivel két különböző természetes szám különbsége nem lehet kisebb 1-nél (természetesen az abszolút értékét tekintve):

 |b|>r_1>r_2>...>r_n\geq0

A következő lépés, hogy bebizonyítjuk: az utolsó maradék közös osztó. Ehhez alulról felfelé haladunk az eljárásban:

  • r_{n-1}=q_nr_n
  • r_{n-2}=q_{n-1}r_{n-1}+r_n=\left(q_{n-1}q_n+1\right)r_n
  • r_{n-3}=q_{n-2}r_{n-2}+r_{n-1}
  • \dots

Mivel r_n osztója r_{n-2}-nek és r_{n-1}-nek is, ezért a lineáris kombinációjuknak is. Az eljárást végigkövetve kapjuk, hogy r_n|a és r_n|b.

Végül bizonyítjuk a maximalitást. Ennek során kihasználjuk azt a tényt, hogy a közös osztók egy szigorúan monoton növekvő természetes számsort alkotnak, aminek felső határa min(a,b), valamint hogy a lánc minden tagja osztója az utána következőnek. Tegyük fel, hogy a legnagyobb közös osztó x. Ekkor, mivel r_n is közös osztó, r_n|x. Viszont, mivel a közös osztók osztói a a két szám lineáris kombinációinak is, így a lánc elemeire felírva kapjuk:

  • x|r_1=a-q_1b.
  • x|r_2=b-q_2r_1
  • x|r_3=r_1-q_3r_2
  • \dots
  • x|r_n=r_{n-2}-q_nr_{n-1}.

Mivel a feltételünk az volt, hogy r_n osztója x-nek, ezért az oszthatóság definíciója miatt x=r_n. QED

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.

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

  • Az algoritmus visszafejtésével a legnagyobb közös osztó előállítható a két szám lineáris kombinációjaként:
(a,b)=ax+by

ezzel a lineáris diofantoszi egyenletek megoldhatóságára is feltételeket szabhatunk.

  • Az algoritmus a leggyorsabban akkor ér véget, ha b|a.
  • Az algoritmus a szomszédos Fibonacci-számok esetén rendkívül lassú, ugyanis végigfut visszafelé a teljes sorozaton. A sorozat ugyanis szigorúan monoton növekvő, valamint a definíció szerint
a_n=a_{n-1}+a_{n-2}
ami megfelel a maradékos osztás definíciójának.
  • Szakaszok esetén is értelmezhető a maradékos osztás, így az euklideszi algoritmus is elvégezhető. Itt azonban nem tudjuk biztosítani az eljárás véges hosszát. Ha ez teljesül, akkor a két szakasz összemérhető.

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;
}

A definícióhoz hűen megvalósítható az algoritmus rekurzióval is, ezt egy Java nyelvű példával szemléltethetjük:

class GreaterCommonDivider{
    public static int gcd(int a, int b){
        if(a%b == 0){
            return b;
        } else {
            return gcd(b, a%b);
    }

    public static void main(String args[]){
        if(args.length != 2){
            System.exit(1);
        }
        System.out.println( gcd( Integer.parseInt( args[0] ), Integer.parseInt( args[1] ) ) );
        System.exit(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.