Matematik tarihi boyunca insanlığın en çok kafa yorduğu konulardan biri sayılar arasındaki gizli uyum ve bölünebilirlik ilişkileridir. Milattan önce yaklaşık 300 yılında İskenderiyeli Öklid (Euclid) tarafından kaleme alınan ünlü *Elemanlar (Elements)* adlı eserde tarif edilen **Öklid Algoritması (Euclidean Algorithm)**, bilgisayar bilimleri tarihinin bilinen en eski ve en zarif algoritmalarından biridir. İki tamsayının En Büyük Ortak Bölenini (EBOB / GCD - Greatest Common Divisor) çılgınca asal çarpanlara ayırmakla uğraşmadan göz açıp kapayıncaya kadar bulan bu algoritma, günümüzde modern bankacılık şifrelemelerinden (RSA kriptografisi) otonom robotların dişli oranlarının hesaplanmasına kadar pek çok ileri teknolojinin çekirdeğinde yer alır.
---
1. En Büyük Ortak Bölen (EBOB) Nedir ve Klasik Yöntem Neden Yetersizdir?
Matematiksel olarak sıfırdan farklı iki $a$ ve $b$ tamsayısının her ikisini de kalansız bölen en büyük pozitif tamsayıya $EBOB(a, b)$ denir.
Klasik Okul Yöntemi (Asal Çarpanlara Ayırma):
Ortaokulda öğretilen yöntem şudur: Her iki sayıyı da asal çarpanlar çizgisiyle 2, 3, 5 gibi asallara böleriz:
**Sorun Nedir?** Küçük sayılarda bu yöntem kolaydır. Fakat 300 basamaklı iki devasa sayının EBOB'unu bulmak istediğinizde, sayıları asal çarpanlarına ayırmak günümüzün en güçlü süper bilgisayarlarıyla bile binlerce yıl sürer! (Zaten modern RSA şifrelemesi de bu asal çarpanlara ayırma zorluğuna dayanır). İşte Öklid, asal çarpanlara hiç bulaşmadan bölme işlemiyle bu problemi anında çözen bir dahiydi!
---
2. Öklid Algoritmasının Matematiksel Çalışma Prensibi
Öklid'in temel matematiksel gözlemi son derece sadedir:
> "İki sayının en büyük ortak böleni, büyük sayıdan küçük sayıyı çıkardığınızda kalan fark ile küçük sayının en büyük ortak bölenine eşittir."
Matematiksel Teorem:
$$EBOB(a, b) = EBOB(b, a \pmod b)$$
(Burada $a \pmod b$, $a$'nın $b$'ye bölümünden kalan sayıdır).
Bu işlem kalan sıfır ($0$) olana kadar tekrarlanır. Kalan sıfır olduğunda, bir önceki adımda bölen durumundaki sayı doğrudan aranan EBOB'dur!
Adım Adım Örnek Simülasyon: $EBOB(252, 105)$
1. **Adım 1:** 252'yi 105'e bölün: $252 = 2 imes 105 + 42$ (Kalan: 42).
2. **Adım 2:** 105'i 42'ye bölün: $105 = 2 imes 42 + 21$ (Kalan: 21).
3. **Adım 3:** 42'yi 21'e bölün: $42 = 2 imes 21 + 0$ (Kalan: 0).
Sadece 3 adımda yüzlerce çarpanı eleyerek doğru sonuca ulaştık.
---
3. Geometrik Yorum: Fayans Döşeme Problemi
Öklid bu algoritmayı geometrik olarak düşünmüştü:
Elinizde $252 imes 105$ cm boyutlarında dikdörtgen bir banyo zemini olduğunu düşünün. Bu zemini hiç kesme yapmadan tamamen kaplayacak en büyük kare fayansların bir kenarı kaç cm olmalıdır?
---
4. Zaman Karmaşıklığı ve Lamé Teoremi
Fransız matematikçi Gabriel Lamé (1844), bilgisayar bilimleri tarihinin ilk karmaşıklık analizini Öklid algoritması üzerinde yapmıştır:
---
5. EKOK (En Küçük Ortak Kat) ile Bağıntı
İki sayının En Küçük Ortak Katı (EKOK / LCM), EBOB bilindiğinde tek bir formülle $O(1)$ sürede anında bulunur:
$$EKOK(a, b) = rac{|a imes b|}{EBOB(a, b)}$$
*Örnek:* $EBOB(252, 105) = 21$ olduğuna göre;
$$EKOK(252, 105) = rac{252 imes 105}{21} = 252 imes 5 = 1260$$
---
6. Tam ve Çalışan Kodlar
Python ile Özyinelemeli ve Döngüsel Öklid Algoritması:
def ebob_oklid(a, b):
# Kalan 0 olana kadar b sayısı a'nın yerine geçer, kalan ise b'nin yerine
while b != 0:
a, b = b, a % b
return a
def ekok_hesapla(a, b):
return abs(a * b) // ebob_oklid(a, b)
# Test Senaryosu
sayi1 = 252
sayi2 = 105
ebob = ebob_oklid(sayi1, sayi2)
ekok = ekok_hesapla(sayi1, sayi2)
print(f"Sayılar: {sayi1} ve {sayi2}")
print(f"EBOB (En Büyük Ortak Bölen) : {ebob}")
print(f"EKOK (En Küçük Ortak Kat) : {ekok}")C++ ile Öklid Algoritması:
#include <iostream>
// Özyinelemeli (Recursive) Tek Satırlık Öklid
long long ebob(long long a, long long b) {
return (b == 0) ? a : ebob(b, a % b);
}
long long ekok(long long a, long long b) {
if (a == 0 || b == 0) return 0;
return (a / ebob(a, b)) * b; // Taşkın (overflow) önleyici çarpma sırası
}
int main() {
long long x = 1071, y = 462;
std::cout << "EBOB(" << x << ", " << y << ") = " << ebob(x, y) << std::endl;
std::cout << "EKOK(" << x << ", " << y << ") = " << ekok(x, y) << std::endl;
return 0;
}---
7. Siber Güvenlik ve RSA Şifrelemesindeki Yeri
Modern internetin güvenliğini sağlayan HTTPS ve SSL sertifikaları, RSA açık anahtarlı şifreleme algoritmasını kullanır. RSA algoritmasında özel anahtarın (Private Key) hesaplanabilmesi için **Genişletilmiş Öklid Algoritması (Extended Euclidean Algorithm)** kullanılır. Bu algoritma, $a \cdot x + b \cdot y = EBOB(a, b)$ eşitliğini sağlayan $x$ ve $y$ katsayılarını bularak modüler tersi (Modular Multiplicative Inverse) hesaplar. 2300 yıl önce yaşamış bir Yunan filozofunun fikri, bugün kredi kartı bilgilerinizin internette çalınmasını engellemektedir!
---
8. Kendini Geliştirme Görevi (Challenge)
**Görev:** İki sayının EBOB'unu bulan fonksiyonu temel alarak, bir dizi içerisindeki $N$ adet sayının (örneğin `[36, 60, 96, 120]`) ortak EBOB'unu ve EKOK'unu bulan genel bir Python fonksiyonu geliştirin! (İpucu: $EBOB(a, b, c) = EBOB(EBOB(a, b), c)$ mantığını zincirleme döngüyle uygulayın).
---
Sonuç
Öklid Algoritması, basit bir matematiksel sezginin nasıl zamansız bir mühendislik şaheserine dönüşebileceğinin en çarpıcı kanıtıdır. Gereksiz hesaplamaları budayarak problemi adım adım küçültme stratejisi, algoritmik düşüncenin özünü oluşturur. Daha fazla veri yapısı ve algoritma örneği için sitemizdeki [Algoritma Kütüphanesini](/dersler) inceleyebilirsiniz!