Öklid algoritması
En büyük ortak bölenleri hesaplamak için bir algoritma
Öklid algoritması iki doğal sayının en büyük ortak bölenini bulmak için kullanılır.
Algoritma
değiştir- a > b > 1 olsun.
- a = q0b + r1; 0 < r1 < b; (a, b) = (b, r1) ve
- b = q1r1 + r2; 0 < r2 < b; (b, r1) = (r1, r2) tanımları ile
- 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 sonucuna ulaşılır.
- Her satırda elde edilen eşitlikler toplandığında
- (a, b) = (b1, r1) = (r1, r2) = ... = (rn-1 ,rn) = rn sonucu elde edilir.
 | Matematik ile ilgili bu madde taslak seviyesindedir. Madde içeriğini genişleterek Vikipedi'ye katkı sağlayabilirsiniz. |