Bölme algoritması

Bölme algoritması, matematikte çok temel ve önemli bir kavramdır. En basit tanımıyla, verilen iki tam sayıdan (bölünen ve bölen) birini diğerine böldüğümüzde bir bölüm ve bir kalan elde etmemizi sağlayan bir yöntemdir. Bu kavram, ilkokuldan başlayarak lise ve üniversite matematiğine kadar pek çok alanda karşımıza çıkar ve sayı teorisi, kriptografi, bilgisayar bilimleri gibi alanlarda hayati bir rol oynar.

Bölme algoritması, bir tam sayının (bölünen, a) başka bir tam sayıya (bölen, b) bölündüğünde, bölüm (q) ve kalan (r) denilen benzersiz iki tam sayının var olduğunu ifade eder. Bu durum şu formülle ifade edilir:

a=bq+r

Burada;

 a: Bölünen (bölmek istediğimiz sayı)
 b: Bölen (bölen sayı, b değildir =0)
 q: Bölüm (bölme işleminin sonucu, a'nın b'ye kaç kez tam olarak bölünebildiği)
 r: Kalan (bölme işleminden sonra artan kısım)

Ve en önemli koşul, kalanın (r) her zaman bölenin (b) mutlak değerinden küçük olmasıdır: 0≤r<∣b∣. Bu koşul, kalanın her zaman pozitif veya sıfır olmasını ve tek olmasını garanti eder. Eğer r=0 ise, a sayısı b sayısına tam bölünüyor demektir.

 Bölme Algoritmasının Detaylı Açıklaması ve İşleyişi 
Bölme algoritması, aslında rasyonel sayıların kesirli gösteriminden veya ondalık açılımlarından farklı olarak, tam sayılarla yapılan bir işlemdir. Temelinde, bölünen sayıdan böleni tekrar tekrar çıkarma fikri yatar. Kaç kez çıkarabildiğimiz bölümü, en sonunda kalan ise artan kısmı ifade eder.

Örnek 1: Basit Bir Bölme İşlemi

Diyelim ki 17 sayısını 5'e bölmek istiyoruz.

a=17 (Bölünen) b=5 (Bölen)

Şimdi 17=5q+r denklemini çözmeye çalışalım, 0≤r<5 koşuluyla.

 17−5=12 (1 kez çıkardık, q=1)
 12−5=7 (2 kez çıkardık, q=2)
 7−5=2 (3 kez çıkardık, q=3)
 2<5 olduğu için daha fazla 5 çıkaramayız.

Bu durumda:

 q=3 (Bölüm)
 r=2 (Kalan)

Denklemi kontrol edelim: 17=5×3+2⟹17=15+2⟹17=17. Doğru. Kalan koşulu da sağlanıyor: 0≤2<5.

Örnek 2: Büyük Sayılarla Bölme İşlemi (Uzun Bölme Yöntemi)

Şimdi daha büyük sayılarla, özellikle "uzun bölme" (long division) olarak bilinen yöntemi kullanarak bölme algoritmasını uygulayalım. Diyelim ki 4578 sayısını 23'e böleceğiz.

a=4578 (Bölünen) b=23 (Bölen)

Uzun bölme adımları:

 45'te 23 kaç kere var? 23'ün katlarına bakalım: 23×1=23, 23×2=46. 46, 45'ten büyük olduğu için 1 kere var.
 Bölüme 1 yazılır.
 1×23=23. 45'ten 23 çıkarılır: 45−23=22.
 Kalanın yanına bir sonraki basamak indirilir. 22'nin yanına 7 indirilir, sayı 227 olur.
 227'de 23 kaç kere var? Tahmin etmeye çalışalım. 23×10=230. Demek ki 10'dan az olacak. 23×9=207.
 Bölüme 9 yazılır.
 9×23=207. 227'den 207 çıkarılır: 227−207=20.
 Kalanın yanına bir sonraki basamak indirilir. 20'nin yanına 8 indirilir, sayı 208 olur.
 208'de 23 kaç kere var? Yine 23×9=207 olduğunu biliyoruz.
 Bölüme 9 yazılır.
 9×23=207. 208'den 207 çıkarılır: 208−207=1.

Tüm basamaklar indirildi ve kalan 1 oldu. Bu durumda:

 q=199 (Bölüm)
 r=1 (Kalan)

Denklemi kontrol edelim: 4578=23×199+1⟹4578=4577+1⟹4578=4578. Doğru. Kalan koşulu da sağlanıyor: 0≤1<23.

Örnek 3: Negatif Sayılarla Bölme Algoritması

Bölme algoritması negatif sayılar için de geçerlidir, ancak kalan koşulu (0≤r<∣b∣) nedeniyle sonuçlar pozitif sayılardan biraz farklı olabilir.

Diyelim ki −17 sayısını 5'e bölmek istiyoruz.

a=−17 b=5

Denklem: −17=5q+r, ve 0≤r<5 olmalı.

Eğer q=−3 dersek: 5×(−3)=−15. −17=−15+r⟹r=−2. Bu, r≥0 koşulunu sağlamaz.

Bu durumda q'yu daha küçük seçmeliyiz. q=−4 diyelim: 5×(−4)=−20. −17=−20+r⟹r=3.

Bu durumda:

 q=−4 (Bölüm)
 r=3 (Kalan)

Denklemi kontrol edelim: −17=5×(−4)+3⟹−17=−20+3⟹−17=−17. Doğru. Kalan koşulu da sağlanıyor: 0≤3<5.

Peki ya bölen negatifse? Diyelim ki 17 sayısını −5'e bölmek istiyoruz.

a=17 b=−5

Denklem: 17=(−5)q+r, ve 0≤r<∣−5∣ yani 0≤r<5 olmalı.

Eğer q=−3 dersek: (−5)×(−3)=15. 17=15+r⟹r=2.

Bu durumda:

 q=−3 (Bölüm)
 r=2 (Kalan)

Denklemi kontrol edelim: 17=(−5)×(−3)+2⟹17=15+2⟹17=17. Doğru. Kalan koşulu da sağlanıyor: 0≤2<5.

Görüldüğü gibi, kalan her zaman pozitif veya sıfır olmalıdır.

 Bölme Algoritmasının Tarihçesi ve Önemi 
Bölme algoritması, matematik tarihinde oldukça köklü bir geçmişe sahiptir. Antik Yunan matematikçileri, özellikle Öklid, bu kavramı "Öklid Algoritması"nın temelini oluşturan teoremlerinde kullanmıştır. Öklid Algoritması, iki sayının en büyük ortak bölenini (EBOB) bulmak için kullanılan bir yöntemdir ve doğrudan bölme algoritmasına dayanır.

Bölme algoritmasının önemi çok yönlüdür:

 Sayı Teorisi: Sayı teorisinin temel taşlarından biridir. Asal sayılar, bölünebilme kuralları, modüler aritmetik (kriptografide ve bilgisayar bilimlerinde çok önemli) gibi birçok konunun temelini oluşturur.
 Kriptografi: Modern şifreleme algoritmalarının (RSA gibi) çoğu, büyük sayılarla yapılan modüler aritmetik işlemlere dayanır. Bu işlemlerin temelinde bölme algoritması yatar. Örneğin, bir sayının başka bir sayıya göre modunu bulmak demek, o sayıyı diğerine böldüğümüzde kalanı bulmak demektir.
 Bilgisayar Bilimleri: Bilgisayarların tamsayı bölme işlemleri, bölme algoritmasına uygun olarak tasarlanır. Derleyiciler, programlama dilleri ve donanımlar bu algoritmayı kullanır. Ayrıca, hata düzeltme kodları ve veri sıkıştırma algoritmaları da bölme algoritmasının prensiplerinden yararlanır.
 Soyut Cebir: Halkalar ve cisimler gibi soyut cebirsel yapılar incelenirken, bölme algoritması kavramının genellemeleri (Öklid Bölgeleri) büyük önem taşır. Bu genellemeler, polinom halkalarında ve diğer cebirsel yapılar üzerinde bölme işlemini tanımlamamıza olanak tanır.
 Periyodik Ondalık Sayılar: Rasyonel bir sayıyı ondalık olarak ifade ettiğimizde neden bazılarının sonlu ondalık, bazılarının ise periyodik ondalık olduğunu anlamak için bölme algoritması ve kalanların tekrarlanması prensibini kullanırız. Bölme işlemi sırasında kalanlar belirli bir noktadan sonra kendini tekrar etmeye başladığında periyodik ondalık açılım ortaya çıkar.

Örnek 4: Modüler Aritmetik ve Kalanlar

Bölme algoritmasının en pratik uygulamalarından biri modüler aritmetiktir. Modüler aritmetik, "saat matematiği" olarak da adlandırılabilir. Bir sayının başka bir sayıya göre modunu almak, o sayıyı diğerine böldüğümüzde elde edilen kalanı bulmaktır.

Formül olarak ifade edersek: a(mod m)=r, burada r kalan anlamına gelir.

Diyelim ki şu an saat 10:00 ve 5 saat sonra saatin kaç olacağını bulmak istiyoruz. 10+5=15. Bir saatte 12 saat olduğu için, 15'i 12'ye böleriz: 15=12×1+3. Kalan 3'tür. Yani saat 03:00 olacaktır.

Modüler aritmetik gösterimiyle: (10+5)(mod12)=15(mod12)=3.

Bir başka örnek: Bugün Perşembe ve 100 gün sonra haftanın hangi günü olacak? Bir haftada 7 gün vardır. 100'ü 7'ye bölelim: 100=7×14+2. Kalan 2'dir. Perşembe'den 2 gün sonra Cumartesi olur. Modüler aritmetik gösterimiyle: (Pers\cembe+100)(mod7)=(Pers\cembe+2)(mod7)=Cumartesi. (Perşembe'yi 4. gün olarak kabul edersek, (4+100)(mod7)=104(mod7)=2. Haftanın 2. günü Salı'ya denk gelir. Eğer Pazar'ı 0 kabul edersek Perşembe 4 olur, 104 mod 7 yine 6 yapar, yani Cumartesi olur. Başlangıç gününü nasıl kodladığınıza bağlı olarak değişir.)

 Bölme Algoritmasının İspatı (Sezgisel Yaklaşım) 
Bölme algoritmasının varlığı ve tekliği, matematikte aksiyomatik olarak kabul edilen sayma prensipleriyle (iyi sıralama prensibi gibi) ispatlanır. Ancak sezgisel olarak nasıl var olduğunu anlayabiliriz.

Varoluş: a ve b gibi iki tam sayı verildiğinde (b=0), a'dan b'yi çıkarmaya devam edebiliriz. a,a−b,a−2b,a−3b,… Bu dizi bir noktada pozitif olmayan bir sayıya ulaşacaktır (eğer a>0,b>0 ise). Bu dizideki en küçük pozitif veya sıfır olan sayıya ulaşana kadar devam ederiz. Bu sayı bizim kalanımız (r) olacaktır. Kaç kez b çıkardığımız ise bölümümüzü (q) verecektir.

Örneğin a=17,b=5: 17 17−5=12 12−5=7 7−5=2 (Bu pozitif ve 5'ten küçük, o yüzden bu r) Bu işlemi 3 kez yaptık, o yüzden q=3.

Teklik: Peki bu q ve r değerlerinin neden tek olduğunu nasıl ispatlarız? Farz edelim ki hem (q1,r1) hem de (q2,r2) adında iki farklı bölüm ve kalan çifti var olsun ve ikisi de bölme algoritmasının koşullarını sağlıyor olsun: a=bq1+r1, burada 0≤r1<∣b∣ a=bq2+r2, burada 0≤r2<∣b∣

İki denklemi birbirinden çıkarırsak: 0=bq1+r1−(bq2+r2) 0=b(q1−q2)+(r1−r2) b(q2−q1)=r1−r2

Bu denklem, b'nin (r1−r2)'yi böldüğünü gösterir. Ancak 0≤r1<∣b∣ ve 0≤r2<∣b∣ olduğundan, −(∣b∣−1)≤r1−r2≤∣b∣−1 olur. Yani r1−r2 farkı, ∣b∣'den kesinlikle küçüktür. b'nin (r1−r2)'yi bölebilmesi ve (r1−r2)'nin mutlak değerinin ∣b∣'den küçük olması sadece bir durumda mümkündür: r1−r2=0. Bu durumda r1=r2 olur.

Eğer r1=r2 ise, b(q2−q1)=0 denklemi elde edilir. b eşit değildir 0 olduğu için, q2−q1 sıfır olmak zorundadır. Yani q2=q1.

Bu ispat, bölüm ve kalanın her zaman tek olduğunu ve bu nedenle bölme algoritmasının tutarlı bir şekilde çalıştığını gösterir.

 Sonuç 
Bölme algoritması, matematiğin ve bilgisayar bilimlerinin temelini oluşturan, görünüşte basit ancak derinlemesine önemli bir kavramdır. Sayı teorisinden kriptografiye, günlük hesaplamalardan karmaşık algoritmaların tasarımına kadar geniş bir uygulama yelpazesine sahiptir. Kısacası, bir sayıyı diğerine böldüğümüzde elde ettiğimiz bölüm ve kalanı, belirli koşullar altında benzersiz bir şekilde tanımlayan matematiksel bir ifadedir ve modern dünyamızın işleyişi için vazgeçilmezdir.

 Kaynakça 

Kategori:Matematik
Kategori:Cebir
Kategori:Cebir teoremleri
Kategori:Matematik teorileri
Kategori:Algoritmalar