Öklid algoritması

Öklid algoritması iki doğal sayının en büyük ortak bölenini bulmak için kullanılır.

Algoritma

a > b > 1 olsun.

a = q₀b + r₁; 0 < r₁ < b; (a, b) = (b, r₁) ve

b = q₁r₁ + r₂; 0 < r₂ < b; (b, r₁) = (r₁, r₂) tanımları ile

r_n+1 = 0 oluncaya kadar gidilir.

r_n-2 = q_n-1r_n-1 + r_n; (r_n-2, r_n-1) = (r_n-1, r_n) ve son satırda r_n+1 = 0 olduğundan

r_n-1 = q_nr_n + 0; (r_n-1, r_n) = r_n sonucuna ulaşılır.

Her satırda elde edilen eşitlikler toplandığında

(a, b) = (b₁, r₁) = (r₁, r₂) = ... = (r_n-1 ,r_n) = r_n sonucu elde edilir.

Matematik ile ilgili bu madde taslak seviyesindedir. Madde içeriğini genişleterek Vikipedi'ye katkı sağlayabilirsiniz.