Bölme Algoritması ve Öklid Algoritması (Euclid Algorithm)

Bölme Algoritması

a,b ∈ Z, b≠0 verilmiş olsun. Öyle ki a=q.b+r , 0≤ r ≤ |b| olacak biçimde tek türlü belirli q ve r sayıları vardır.

Bu teorem deki q sayısına, a'nın b ile bölünmesinden elde edilen bölüm ve r sayısına a'nın b ile bölünmesinden elde edilen kalan denir.

Teorem: a,b,q ve r ∈ Z\{0} olsun. a ile b sayılarının ortak bölenlerinin en büyüğü, (a, b) şeklinde gösterilmek üzere a=b.q+r ise

(a, b) = (b, a-q.b) = (b, r) dir.

Bu ek teorem bölme algoritması ile birleştirilirse iki sayının OBEB'ini bulmak için ünlü Öklid Algoritması elde edilir.

Öklid Algoritması

a > b ≥ 1 olsun. Bölme algoritması ile

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

Eğer r₁≠0 ise, bölme algoritması ile

b=q₁.r₁ + r₂ , 0 ≤ r₂ < r₁ ; (b, r₁)=(r₁, r₂)

Eğer r₂≠0 ise, yine bölme algoritması ile

r₁=q₂.r₂ + r₃ , 0 ≤ r₃ < r₂ ; (r₁, r₂)=(r₂, r₃) elde edilir.

her adımda elde edilen kalan küçüleceğinden sonsuz adımda devam etmeyecektir.

r_n≠0 için r_n+1=0 olacaktır. Öyle ki

r_n-1=q_n.r_n+0 ; (r_n-1, r_n)=r_n olacaktır.

O zaman

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

Demek ki a ve b'nin OBEB'i, Öklit Algoritmasında elde edilen son (sıfırdan farklı) kalandır.