Öklid algoritması: Revizyonlar arasındaki fark
| [kontrol edilmiş revizyon] | [kontrol edilmiş revizyon] |
İçerik silindi İçerik eklendi
Değişiklik özeti yok |
Superyetkin (mesaj | katkılar) Düzenleme |
||
1. satır:
'''Öklid algoritması'''
▲'''Öklid algoritması''', iki doğal sayının [[OBEB]] ini bulmak için kullanılır, şöyleki;
== Algoritma ==
:{{matematik|a > b > 1}} olsun.
:{{Matematik|a {{=}} q<sub>0</sub>b + r<sub>1</sub>; 0 < r<sub>1</sub> < b; (a, b) {{=}} (b, r<sub>1</sub>)}} ve
:{{Matematik|b {{=}} q<sub>1</sub>r<sub>1</sub> + r<sub>2</sub>; 0 < r<sub>2</sub> < b; (b, r<sub>1</sub>) {{=}} (r<sub>1</sub>, r<sub>2</sub>)}} tanımları ile
:{{Matematik|r<sub>n+1</sub> {{=}} 0}} oluncaya kadar gidilir.
:{{Matematik|r<sub>n-2</sub> {{=}} q<sub>n-1</sub>r<sub>n-1</sub> + r<sub>n</sub>; (r<sub>n-2</sub>, r<sub>n-1</sub>) {{=}} (r<sub>n-1</sub>, r<sub>n</sub>)}} ve son satırda {{Matematik|r<sub>n+1</sub> {{=}} 0}} olduğundan
:{{Matematik|r<sub>n-1</sub> {{=}} q<sub>n</sub>r<sub>n</sub> + 0; (r<sub>n-1</sub>, r<sub>n</sub>) {{=}} r<sub>n</sub>}} sonucuna ulaşılır.
:Her satırda elde edilen eşitlikler toplandığında
:{{Matematik|(a, b) {{=}} (b<sub>1</sub>, r<sub>1</sub>) {{=}} (r<sub>1</sub>, r<sub>2</sub>) {{=}} ... {{=}} (r<sub>n-1</sub> ,r<sub>n</sub>) {{=}} r<sub>n</sub>}} sonucu elde edilir.
{{matematik-taslak}}
[[Kategori:Sayılar teorisi algoritmaları]]
| |||