Öklid algoritması

[asdasdasddj]

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