Öklid algoritması

Vikipedi, özgür ansiklopedi
Atla: kullan, ara

Ö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 | kaynağı 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.