Ö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 0 b + r 1; 0 < r 1 < b; (a, b) = (b, r 1)

b = q 1 r 1 + r 2; 0 < r 2 < b; (b, r 1) = (r 1, r 2)

tanımları ile

r n+1 = 0

oluncaya kadar gidilir.

r n-2 = q n-1 r 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 n r 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 1, r 1) = (r 1, r 2) = ... = (r n-1,r n) = r n

sonucu elde edilir.

This article is issued from Vikipedi - version of the 10/20/2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.