Bir kesir verildiğinde çoğu zaman onu sadeleştirmek gerekir. Ancak kesir büyük sayılardan oluşuyorsa, bu işlem çok da kolay değildir. İşte böyle durumlarda, farkında olmadan birçoğumuz Öklid algoritmasını kullanırız.
Öklid Algoritması Nedir?
Öklid algoritması, iki sayı arasındaki en büyük ortak böleni (EBOB) bulmak için kullanılan etkili bir yöntemdir. EBOB, iki sayıyı da kalansız bölebilen en büyük sayıdır. Küçük sayılar için, her iki sayının bölenlerini listeleyip ortak en büyük olanı seçmek işe yarayabilir. Ancak bu yöntem, sayılar büyüdükçe oldukça zahmetli ve zaman alıcı hâle gelir.
Bu sorunu çözmek için geliştirilen Öklid algoritması, EBOB’u çok daha hızlı şekilde bulmamıza olanak tanır. Temel prensibi şudur: İki sayıdan büyük olanı, küçük olana bölümünden kalan ile değiştirirsek, sayıların EBOB’u değişmez. Bu işlemi, kalan sıfır olana kadar tekrarladığımızda, son sıfır olmayan sayı, iki sayının EBOB’u olur.
Öklid algoritması, a ve b (burada a > b olacak şekilde) iki sayısının en büyük ortak bölenini (EBOB) bulmak için kullanılan bir yöntemdir. Önce a sayısını b’ye bölüp kalanı bulun, bu kalana c diyelim. Ardından b sayısını c’ye bölün, kalan d olsun. Bu işlemi, kalan sıfır olana kadar tekrar edin. Sıfırdan önceki son kalan, başlangıçta verilen iki sayının en büyük ortak bölenidir.
Algoritma, yalnızca sayılarla değil, doğru parçalarıyla da çalışır. Herhangi iki doğru parçası verildiğinde, bunlara tam olarak bölünebilecek ortak bir ölçü birimi bulunabilir (eğer varsa) ve bu işlem aynı algoritmayla gerçekleştirilir. Bu yöntem oldukça kullanışlıdır çünkü algoritmadaki tüm işlemler, cetvel ve pergel kullanarak yapılabilecek geometrik çizimlere karşılık gelir.
Algoritmaya “Öklid algoritması” denmesinin nedeni, Euclid’in Elementler adlı eserinin 7. kitabının 1. önermesinde yer almasıdır.
Öklid Algoritması İle İlgili Bir Örnek
Örneğin, 18/24 kesrini sadeleştirmek istiyorsak, bu iki sayının en büyük ortak bölenini (EBOB) bulmamız gerekir. a = 24 ve b = 18 olarak düşünelim. Bu durumda, a ile b’nin EBOB’u, aynı zamanda a – b’nin de bölenidir. İlk adımda 24 – 18 = 6. Şimdi elimizde 18 ve 6 var, 18 – 6 = 12. Devam edersek, 12 – 6 = 6 ve son olarak 6 – 6 = 0. Yani: EBOB(24,18) = EBOB(18,6) = EBOB(12,6) = EBOB(6,6) = EBOB(6,0) = 6.
Ancak bu yöntem küçük sayılar için uygundur. Sayılar büyüdükçe, bu kadar çok kez çıkarma yapmak verimsiz hale gelir. Bu yüzden daha hızlı olan bölme yöntemini kullanmalıyız. Yani Öklid algoritmasını bölme yoluyla uygulayarak kalanı her adımda yeni sayı olarak alabiliriz.
Örnek: EBOB(1015, 231)
- 1015 ÷ 231 → kalan 91
- 231 ÷ 91 → kalan 49
- 91 ÷ 49 → kalan 42
- 49 ÷ 42 → kalan 7
- 42 ÷ 7 → kalan 0. Son kalansız bölümde elde ettiğimiz sayı 7’dir. Yani: EBOB(1015, 231) = 7
Öklid Algoritması Neden Çalışır?
a > b olmak üzere iki sayı düşünelim. O zaman şu şekilde yazabiliriz: a = n×b + c. Burada n bir tam sayıdır ve b > c koşulu sağlanır. Eğer c = 0 ise, o zaman b sayısı hem a’nın hem de b’nin en büyük ortak bölenidir. Bu durumda, EBOB(a, b) = b olur.
Eğer c sıfır değilse, o zaman a ve b’nin ortak bölenlerinin tümü, aynı zamanda c’yi de böler. Çünkü a – n×b = c olduğundan, a ve b’yi bölen bir sayı, c’yi de böler. Bu durumda, EBOB(a, b) değeri, b ve c’nin de ortak bölenidir. Yani: EBOB(b, c) ≥ EBOB(a, b)
Öte yandan, b ve c’nin herhangi bir ortak böleni, n×b + c = a ifadesi üzerinden a’yı da böler. Bu da şunu gösterir: EBOB(a, b) ≥ EBOB(b, c). O halde, her iki eşitsizlik bir araya geldiğinde, şu sonuca varırız:
EBOB(a, b) = EBOB(b, c)
Bu işlemi, kalan sıfır olana kadar tekrar edebiliriz. Kalan sıfır olduğunda, başlangıçtaki a ve b sayılarının en büyük ortak böleni (ve işlem boyunca elde edilen her sayı çiftinin de ortak böleni), bu işlemlerde elde edilen son sıfırdan farklı kalan olur.
Bu Algoritma Ne İşimize Yarar?
İki tam sayı olan a ve b için, ax+by=c biçimindeki bir denklem verildiğinde ve x ile y’nin de tam sayı olması istendiğinde, bu tür denklemlere Diophantus (ya da doğrusal) denklemler denir. Bu tür denklemleri çözmenin ilk adımı, a ve b’nin en büyük ortak bölenini (EBOB) bulmaktır. Çünkü bu tür bir denklem ancak c, a ve b’nin EBOB’una bölünüyorsa çözülebilir.
Örneğin, 1015 ve 2312 sayıları için Öklid algoritması uygulandığında ardışık bölme ve kalan işlemleri sonucunda 7 elde edilir; bu iki sayının en büyük ortak böleni 7’dir. Bu durumda, 1015x+231y=7 denkleminin tam sayı çözümleri vardır.
Bu noktada denklemin çözümüne ulaşmak için EBOB işlemini tersten yazarız; yani son kalanı, önceki kalanlar ve bölenler cinsinden açarak ilk sayılara geri döneriz. Bu işlem, x ve y’yi açıkça veren bir çözümle sonuçlanır. Böylece denklem, tam sayı çözümleriyle çözülmüş olur.
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
