Öklid Algoritması (Euclidean Algorithm), en büyük ortak böleni (EBOB) bulmak için kullanılan eski ve etkili bir matematiksel yöntemdir. Öklid, Antik Yunan matematikçisi Euclid’e atfedilir ve “Elements” (Öğeler) adlı eserinde 300’lü yıllarda ilk defa tanıtılmıştır. Bu algoritma, iki sayının en büyük ortak bölenini hızlı bir şekilde hesaplamak için kullanılır ve temel aritmetik kurallarına dayanır.
Algoritma, iki pozitif tam sayı olan a ve b’nin EBOB’ini bulmak üzere tasarlanmıştır. Ancak, genişletilmiş versiyonları ile negatif sayılar, rasyonel sayılar veya gerçel sayılar üzerinde de kullanılabilir. Temelde, Öklid Algoritması şu adımları içerir:
-
Başlangıç Durumu: İlk olarak, a ve b’nin değerleri belirlenir. Bu sayılar genellikle pozitif tam sayılardır.
-
Bölme Adımı: A’yı b’ye böleriz ve kalanı alırız. Yani, a = bq + r, burada q bölme sonucunu, r ise kalanı temsil eder.
-
Kalan Kontrolü: Eğer r (kalan) sıfırsa, b’nin bulunduğumuz durumda EBOB’u bulunmuş olur. Yani, b en büyük ortak böleni temsil eder.
-
Yeniden Atama: Eğer r sıfır değilse, a’nın yerine b’yi ve b’nin yerine r’yi alırız. Ardından, bu yeni a ve b değerleriyle bölme adımını tekrarlarız.
-
Tekrarlama: Kalan sıfır olana kadar 2-4 adımlarını tekrar ederiz. Bu durumda, en son b’nin değeri EBOB’u temsil eder.
Öklid Algoritması’nın basit bir örnekle açıklanması şu şekilde gerçekleşebilir:
İki sayı, a = 48 ve b = 18 olsun. İlk adımda 48’yi 18’e böleriz ve kalanı alırız:
48 = 18 * 2 + 12
Şimdi, 18’i 12’ye ve 12’yi 6’ya böleriz. Bu işlemi sıfır kalan elde edene kadar tekrarlarız:
18 = 12 * 1 + 6 12 = 6 * 2 + 0
En sonunda, kalan sıfır olduğu için EBOB bulunmuştur ve bu durumda b = 6, en büyük ortak böleni temsil eder.
Öklid Algoritması’nın etkinliği, daha büyük sayılar arasındaki en büyük ortak böleni hızlı bir şekilde bulma yeteneğiyle bilinir. Ayrıca, bu algoritmanın genişletilmiş versiyonları, modüler aritmetikte ve sayı teorisi uygulamalarında da kullanılır.
Matematikte sıkça karşılaşılan bu problemi çözme yöntemi olan Öklid Algoritması, sayı teorisinde, kriptografi alanında, bilgisayar bilimlerinde ve birçok matematiksel disiplinde önemli bir rol oynamaktadır.