
İki sayının ortak bölenlerini bulmak okul matematiğinde oldukça sıradan bir işlem gibi görünür. Ancak sayılar büyüdükçe bu basit soru hızla zorlaşır. Yaklaşık iki bin yıl önce Öklid, bu problemi çözmek için öylesine etkili bir yöntem ortaya koydu ki bugün hâlâ bilgisayar biliminde ve sayı teorisinde kullanıyoruz. Üstelik yöntem, asal çarpanlara ayırmaya bile ihtiyaç duymaz.
Bugün, belirli bir problemi çözmek için sonuca ulaşmayı garanti eden açık ve sonlu hesaplama yöntemlerine algoritma diyoruz. Bu nedenle Öklid’in bu yöntemi bugün “Öklid algoritması” olarak adlandırılır.
Öklid Algoritması Nedir?
Okul matematiğinde örneğin 135 ile 630’un en büyük ortak bölenini bulmak için önce bu sayıları asal çarpanlarına ayırırız:
- 135 = 3³ × 5
- 630 = 2 × 3² × 5 × 7
Daha sonra her asal için iki ayrışımda da bulunan en büyük ortak kuvveti alırız. Burada bu değer 3² × 5 olur. Çarpımı hesapladığımızda 3² × 5 = 45 elde ederiz. Dolayısıyla 135 ile 630’un en büyük ortak böleni 45’tir.
Bu yöntem, en büyük ortak böleni bulmak için asal çarpanlara ayırmanın gerekli olduğu izlenimini verir. Oysa Öklid algoritması asal çarpanlara ayırmadan önce gelir. Öklid, asal çarpanlarla ilgili temel özellikleri kanıtlamak için bu algoritmadan yararlanır.
Öklid’in Elementler’inin VII. Kitap 2. önermesinde, iki tam sayının en büyük ortak bölenini asal çarpanlara ayırmadan bulmayı sağlayan bir yöntem verilir. Yöntem, küçük sayıyı büyük sayıdan tekrar tekrar çıkarmaya, ardından kalanla küçük sayı üzerinde aynı işlemi sürdürmeye dayanır.
135 ile 630 örneğinde, önce küçük sayı olan 135’i 630’dan art arda çıkarırız. 630’dan 135 çıkınca 495, bir kez daha çıkarınca 360, sonra 225 ve 90 kalır. Artık 90, 135’ten küçük olduğu için 135 ile 90 üzerinde devam ederiz. 135 − 90 = 45 olur.
Son olarak 90’dan 45’i çıkardığımızda yine 45, bir kez daha çıkardığımızda ise 0 kalır. Böylece 135 ile 630’un en büyük ortak böleninin 45 olduğunu buluruz.

Öklid’in 30. önermesi bütün bu yapının temel taşlarından biridir. Günümüz diliyle söylersek, bir asal sayı iki sayının çarpımını bölüyorsa, bu iki sayıdan en az birini de bölmek zorundadır. 32. önerme ise her sayının ya asal olduğunu ya da en az bir asal çarpana sahip olduğunu söyler.
Bu iki sonucu bir araya getirdiğimizde, her sayının asal çarpanların çarpımı biçiminde yazılabildiğini ve bu ayrışımın, çarpanların sırası dışında tek olduğunu kolayca elde ederiz.
Öklid Algoritması Günümüzde Nerede Kullanılıyor?
Öklid algoritması yaklaşık iki bin yıllık olmasına rağmen bugün hâlâ bilgisayar bilimi ve sayı teorisinin temel araçlarından biri. Bunun nedeni yalnızca basit olması değil, aynı zamanda çok hızlı çalışmasıdır. Algoritma, çok büyük iki sayının ortak bölenini bu sayıları asal çarpanlarına ayırmadan hesaplar.
Kriptografi, algoritmanın en önemli kullanım alanlarından biridir. Özellikle genişletilmiş Öklid algoritması, modüler tersleri hesaplar. Basitçe söylemek gerekirse, belirli bir sayıyla çarpıldığında modüler aritmetikte 1 sonucunu veren sayıyı bulur. RSA gibi şifreleme sistemleri anahtar oluştururken bu tür hesaplamalardan yararlanır.
Bilgisayar cebiri de aynı algoritmadan yararlanır. Matematik yazılımları yalnızca tam sayıların değil, polinomların da en büyük ortak bölenlerini bu yöntemle hesaplar. Bu sayede programlar cebirsel ifadeleri sadeleştirir ve sembolik hesaplamaları daha verimli biçimde gerçekleştirir.
Öklid algoritmasının sürekli kesirlerle de doğrudan bir bağlantısı vardır. İki sayıya uyguladığımız algoritmanın adımları, bu sayıların oranının sürekli kesir açılımını verir. Matematikçiler bu bağlantıdan irrasyonel sayıları kesirlerle yaklaşık olarak ifade eder. Ayrıca bazı Diofant denklemlerini çözerken yararlanır.
Kısacası Öklid algoritması sayı teorisinden bilgisayar cebirine ve kriptografiye kadar pek çok alanda bugün de iş başındadır.
Okuma Önerisi: Fermat’nın Çarpanlara Ayırma Yöntemi Günümüz Şifreleme Sistemlerini Nasıl Tehdit Ediyor?
Kaynaklar ve ileri okumalar:
- Music and Euclid’s algorithm; yayınlanma tarihi: 1 Eylül 2006; Bağlantı: https://plus.maths.org/
- John Stillwell; Elements of Mathematics: From Euclid to Gödel ; Yayıncı: Princeton University Press
Size Bir Mesajımız Var!
Matematiksel, matematiğe karşı duyulan önyargıyı azaltmak ve ilgiyi arttırmak amacıyla kurulmuş bir platformdur. Sitemizde, öncelikli olarak matematik ile ilgili yazılar yer almaktadır. Ancak bilimin bütünsel yapısı itibari ile diğer bilim dalları ile ilgili konular da ilerleyen yıllarda sitemize dahil edilmiştir. Bu sitenin tek kazancı sizlere göstermek zorunda kaldığımız reklamlardır. Yüksek okunurluk düzeyine sahip bir web sitesi barındırmak ne yazık ki günümüzde oldukça masraflıdır. Bu konuda bizi anlayacağınızı umuyoruz. Ayrıca yazımızı paylaşarak da büyümemize destek olabilirsiniz. Matematik ile kalalım, bilim ile kalalım.
Matematiksel



