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.q0 + r1 , 0 ≤ r1 < b ; (a, b)=(b, r1)
Eğer r1≠0 ise, bölme algoritması ile
b=q1.r1 + r2 , 0 ≤ r2 < r1 ; (b, r1)=(r1, r2)
Eğer r2≠0 ise, yine bölme algoritması ile
r1=q2.r2 + r3 , 0 ≤ r3 < r2 ; (r1, r2)=(r2, r3) elde edilir.
her adımda elde edilen kalan küçüleceğinden sonsuz adımda devam etmeyecektir.
rn≠0 için rn+1=0 olacaktır. Öyle ki
rn-1=qn.rn+0 ; (rn-1, rn)=rn olacaktır.
O zaman
(a, b)=(b, r1)=(r1, r2)=...=(rn-1, rn)=rn
Demek ki a ve b'nin OBEB'i, Öklit Algoritmasında elde edilen son (sıfırdan farklı) kalandır.
