Temel Matematiksel Kavramlar

2000 Yıllık Bir Algoritma: Öklid Algoritması

Bir kesir verildiğinde çoğu zaman onu sadeleştirmek gerekir. Ancak kesir, büyük sayılardan oluşursa, bu çok da kolay bir işlem değildir. Diyelim ki kesrimiz 4356207 / 1728941 ve biz de bu kesri sadeleştirmek istiyoruz. Bunun için 1728941 ve 4356207 sayılarının en büyük ortak bölenini bulmak lazım. Ancak, sadece 1728941’in bölenlerini bulmak bile kolay bir şey değildir. Neyse ki, iki sayının ortak bölenlerini bulmak, herhangi birinin bölenlerini bulmaktan daha kolaydır. Üstelik bunun için antik dönemlerden beri kullandığımız bir algoritmamız var adı da Öklid algoritması.

Öklid Algoritması Nasıl Çalışır?

Konuyu terimler ile ele almadan mümkün oldukça örnekler üzerinden ilerleyelim. Örneğin, 10000011 ve 10000012’nin en büyük ortak böleninin 1 olduğunu, her iki sayının da bölenlerini bilmeden hemen bilebiliriz. Çünkü d, 10000011 ve 10000012’nin ortak böleni ise p ve q pozitif sayıları için 10000011 = dp ve 10000012 = dq eşitlikleri doğru olmalıdır. Buradan da 10000012 – 10000011 = d(q – p) eşitliğini buluruz. Yani d aynı zamanda 10000012 ve 10000011 sayılarının farkını da böler ki bu fark 1’dir. Daha genel olarak, eğer d, a ve b sayılarının ortak böleni ise, o zaman a – b’yi de böler.

Yukarıda aktardığımız bilgi, en büyük ortak böleni bulmak için etkili bir algoritmanın temelidir. Bu bilgi 2000 yıl önce Elementler isimli kitabın 7. cildinde, 2. önerme olarak tanımlanmıştır. Tanımı yapan kişi Öklid olduğu için de Öklid algoritması olarak adlandırılır. Öklid Algoritması, iki tam sayının en büyük ortak bölenini hızlıca bulmak için kullanılan bir yöntemdir. Basitçe açıklamak gerekirse Öklid algoritmasını kullanırken verilen iki sayıyı sürekli olarak birbirinden çıkartıyoruz. Sonrasında fark ile çıkartılan sayı için aynı şeyi tekrarlıyoruz. Bu işleme fark sıfır olana kadar devam ediyoruz. Fark sıfır olduğunda anda çıkarttığımız son sayı bizim en büyük ortak bölenimiz oluyor.

Öklid Algoritması İle İlgili Birinci Örnek

Örneğin 18/24 kesrini sadeleştirmek isteyelim. Bu durumda bu ikilinin en büyük ortak bölenini ( EBOB) almamız gerekir. a = 18 ve b = 24 biçiminde düşünürsek a ve b’nin en büyük ortak böleninin aynı zamanda a – b’nin de bir bölenidir. O zaman EBOB(24, 18) = EBOB(18, 6) = EBOB(12, 6) = EBOB(6, 6) = EBOB(6, 0)= 6 olacaktır. Ancak örnek olarak küçük sayıları seçmemizin nedeni, aslında algoritmayı bu biçimde kullanmanın pek de pratik olmamasıdır. Yani sayılar büyüdükçe Öklid’in yaptığı gibi sadece çıkarma kullanmak pek doğru olmaz.

Örneğin, EBOB (101, 10100 + 1) için sonucu tekrar tekrar çıkarma ile bulmaya çalışırsak bu işlemi 1098 kez tekrarlamamız gerekir. Bu da elbette hızlı bir yöntem değil. Bu nedenle işin içine çıkarmanın kısa yolu olan bölme işlemini sokmamız gerekir. Sonuçta, r farkı b’den küçük olana kadar a’dan b’yi art arda çıkarmak, a’yı b’ye bölmek ve kalan r’yi elde etmekle aynıdır. Yani Öklid algoritmasını kullanırken sayıları defalarca birbirinden çıkartacağımıza iki sayıyı birbirine bölüp, kalanı elde ederek de algoritmayı uygulamaya devam edebiliriz.

GCD: Greatest Common Divisor yani en büyük ortak bölen demektir. Algoritma ile ilgili bir örnek daha.

Öklid Algoritması İle İlgili İkinci Örnek

1015 ve 231’in EBOB’unu bulalım. Önce 1015’i 231’e bölerek kalanı bulalım. 231 x 4 = 924 olduğundan, kalan 1015–924 = 91 olacaktır. Şimdi ortak bölen bulmaya çalıştığımız sayılar 231 ve 91’e indirgendi. 231’i 91’e bölersek kalan bu sefer 49 olacaktır. Şimdi 91 ve 49 için devam edelim. 91’in içinde 49 bir kere vardır ve kalan 42’dir. 49 ve 42 için devam edersek kalanı bu sefer 7 olarak buluruz. 7 x 6 tam olarak 42 olduğundan, bu bizim son adımımız! 1015 ve 231’in en büyük ortak böleni 7’dir. Bu algoritmanın neden işe yaradığını merak ederseniz bu makaleye de göz atabilirsiniz.

Elbette asal sayıları çarpanlarına ayırmak mümkün olduğunda ya da en büyük ortak bölenini bulmaya çalıştığınız sayılar küçük olduğunda geleneksel yöntemler ile ortak böleni hesaplamaya devam edin. Zaten okullarda veya sınavlarda karşınıza çıkacak sorular bu yöntem ile yapabileceğiniz biçimde ayarlanmış olacaktır. Ancak gerçek hayatta matematik, sınavlarda sorulan sorular için var olmaz. Öklid algoritması aracılığı ile en büyük ortak böleni 1 bulduğumuz zaman sayıların ortak böleni olmadığını yani sayıların aralarında asal olduklarını söyleyebiliriz. Bu bilgi de asal sayılar ile uğraşmak zorunda kaldığımız pek çok alanda bilmek istenilen bilgilerden birisidir. Kısacası Öklid algoritması bilgisayarlara büyük sayılar ile uğraşmak zorunda kalındığı zamanlarda önemli bir avantaj sağlar.

Sınavlarda sık karşımıza çıkan bu algoritma ile çözülebilecek bir soru için de videoya göz atabilirsiniz.

Kaynak: John Stillwell; Elements of Mathematics;  Princeton University Press

Matematiksel

Sibel Çağlar

Yola Kadıköy Anadolu Lisesi ile başladım. Ardından gelen tesadüfler, zamanında pek de sevmediğim, matematik ile yolumu kesiştirdi. Sonucunda Marmara Üniversitesinde İng. Matematik öğretmenliğinden mezun oldum. Zaman akıp gitti; bu süreçte ben de çeşitli özel eğitim kurumlarında matematik öğretmenliği ve eğitim koordinatörlüğü yaptım. Bu esnada da bol bol matematik ile ilgili serzenişlere şahit oldum. Ne yapmalı diye düşünürken, aklıma bu site fikri geldi. 2015 yılında matematiksel.org web sitesini kurdum. Amacım bilime ve özelinde matematiğe ilgiliyi arttırmaktı. Matematiğin hayattan kopuk olmadığını kanıtlamaktı. Devamında ekip arkadaşlarının da dahil olması ile kocaman bir aile olduk. Yolumuz uzun ama kesinlikle çok keyifli.
Başa dön tuşu