Öklid Algoritması

Öklid algoritması, iki pozitif tam sayının en büyük ortak bölenini (EBOB) hesaplamak için kullanılan, aritmetik tarihinin en eski ve temel algoritmalarından biridir. Algoritma, ismini İskenderiyeli matematikçi Öklid’den almakla birlikte, temel prensipleri Öklid’in Elemanlar (Elements) adlı eserinin VII. kitabında yer alan Önerme 1 ve 2'ye dayanmaktadır.

Öklid’in Elemanlar eserinde algoritma, iki büyüklüğün ortak bir ölçüsünü bulma süreci olarak tanımlanır. Antik Yunan matematiğinde sayılar, doğru parçaları (büyüklükler) olarak temsil edilmekteydi. Algoritma, "karşılıklı çıkarma" (anthyphairesis) süreci üzerinden işler: İki sayıdan büyük olanından küçük olanı ardışık olarak çıkarılır; bu işlem, bir kalan diğerini tam bölene kadar devam eder.

Öklid, VII. kitap Önerme 2’de süreci şu şekilde kurar:

• Eğer iki sayı verilmişse ve küçük olan büyük olanı tam bölmüyorsa, büyük sayıdan küçük sayı çıkarılır.
• Kalan sayı ile önceki küçük sayı arasında aynı işlem tekrarlanır.
• Bu süreç, bir sayı diğerini tam bölene kadar sürer. Kalan son sıfır dışı sayı, orijinal iki sayının ortak ölçüsüdür.

Modern matematiksel gösterimde Öklid algoritması, ardışık bölme işlemi (bölme algoritması) kullanılarak ifade edilir. $a$ ve $b$ ($a>b$) iki pozitif tam sayı olsun. Algoritma aşağıdaki adımları takip eder:

1. $a=b\cdot q_1+r_1$, burada $0\le r_1<b$

2. $b=r_1\cdot q_2+r_2$, burada $0\le r_2<r_1$

3. $r_1=r_2\cdot q_3+r_3$, burada $0\le r_3<r_2$

4. Bu işlem $r_n=0$ olana kadar devam eder.

Sıfırdan farklı en son kalan ($r_{n-1}$), $a$ ve $b$ sayılarının en büyük ortak bölenidir.

Algoritmanın doğruluğu, "Eğer $a=bq+r$ ise, o halde $ebob(a,b)=ebob(b,r)$" teoremine dayanır.

1. $d$ sayısı hem $a$ hem de $b$'yi bölüyorsa ($d|a$ ve $d|b$), o halde $d$, $r=a-bq$ ifadesini de bölmek zorundadır. Dolayısıyla $a$ ve $b$'nin her ortak böleni, $b$ ve $r$'nin de ortak bölenidir.

2. Benzer şekilde, $b$ ve $r$'yi bölen herhangi bir sayı $a=bq+r$ ifadesini de bölmelidir.

3. Bu iki kümenin ortak bölenleri tamamen aynı olduğundan, en büyük ortak bölenleri de aynıdır. Algoritma, kalanların kesin olarak azaldığı ($b>r_1>r_2>\cdots \ge 0$) sonlu bir dizi olduğu için mutlaka bir noktada durur.

Algoritmanın verimliliği, adım sayısı ile Fibonacci dizisi arasındaki ilişki üzerinden analiz edilir. Gabriel Lame tarafından 1844'te kanıtlandığı üzere, Öklid algoritmasındaki adım sayısı, ondalık basamak sayısının yaklaşık beş katını geçemez. En kötü durum senaryosu, ardışık iki Fibonacci sayısının EBOB'unun hesaplanması durumunda ortaya çıkar; çünkü bu sayıların bölümlerinden elde edilen katsayılar ($q_i$) her zaman 1'dir ve kalanlar mümkün olan en yavaş hızda azalır.

Öklid algoritması, rasyonel sayıların en sade biçimine getirilmesinden, şifrelemede kullanılan modüler aritmetik işlemlerine kadar geniş bir yelpazede kullanılır. Ayrıca, rasyonel düğümlerin (rational tangles) sınıflandırılması gibi topolojik problemlerin çözümünde pay ve paydanın en büyük ortak böleni üzerinden yapısal bir araç olarak işlev görür.