Öklid Algoritması (Euclides Algoritması - Öklid Algoritmasının Bir Uygulaması)

Öklid algoritması iki doğal sayının OBEB ini bulmak için kullanılır, şöyleki;

    a>b>/1  olsun

    a=bq0+r1       ;  0/<r1<b               (a,b)=(b,r1)

eğer ise

    b=q1r1+r2       ;   0/<r2<b             (b,r1)=(r1,r2)

eğer ise yine böyle devam edilerek rn+1=0 oluncaya kadar gidilir.

    rn-2=qn-1rn-1+rn        ;     (rn-2,rn-1)=(rn-1,rn)

ve son satırda rn+1=0 olduğundan

    rn-1=qnrn+0      ;            (rn-1,rn)=rn

her satırda elde ettiğimiz eşitlikleri toplarsak

    (a,b)=(b1,r1)=(r1,r2)=.........=(rn-1,rn)=rn       demekki  a,b’nin obebi  rn’e  eşit.