Öklid algoritması

Vikipedi, özgür ansiklopedi

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

Bu madde ya da bir kısmı, Vikipedi standartlarına uygun değildir ve bu nedenle düzenlenmesi gerekmektedir. Maddeyi Vikipedi standartlarına uygun biçimde düzenleyip, geliştirerek Vikipedi'ye katkıda bulunabilirsiniz. NOT:Gerekli değişiklik yapılmadan bu şablon kaldırılmamalıdır. Bu madde Şubat 2008 tarihinden beri, düzenleme isteğiyle etiketlidir.