- Katılım
- 7 Eyl 2009
- Konular
- 6,986
- Mesajlar
- 38,038
- Çözüm
- 1
- Online süresi
- 7d 22h
- Reaksiyon Skoru
- 1,833
- Altın Konu
- 0
- Başarım Puanı
- 494
- MmoLira
- 6,600
- DevLira
- 0
HERAKLES Otomatik Avlı kalıcı sunucu. 19 Haziran'da açılıyor. Atius & Wizard güvencesiyle hemen kayıt ol, ön kayıt ödülleri aktif. HEMEN TIKLA!
Ö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,bnin obebi rne eşit.
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,bnin obebi rne eşit.
