Öklid Algoritması Nedir?
Öklid algoritması, bilinen en eski algoritmalardan biridir ve MÖ 300 civarında Yunan matematikçi Öklid tarafından tanımlanmıştır. İki tam sayının en büyük ortak bölenini (OBEB) — yani her ikisini de kalansız bölen en büyük sayıyı — verimli bir şekilde bulur. Bu hesaplama aracı ayrıca, doğrudan OBEB'den türetilen en küçük ortak katı (OKEK) da verir.
Bu Aracı Nasıl Kullanırsınız?
Yukarıdaki alanlara iki tam sayı girin ve hesaplatın. Araç, girdiğiniz değerlerin mutlak değerlerini kullanır ve kalan sıfır olana kadar \(\gcd\!\left(\text{a},\,\text{b}\right) = \gcd\!\left(\text{b},\,\text{a} \bmod \text{b}\right)\) kuralını tekrar tekrar uygular. Ardından hem OBEB hem de OKEK sonucunu gösterir.
Formülün Açıklaması
Temel mantık şudur: Büyük sayıyı, küçük sayıya bölündüğünde kalan değerle değiştirirseniz iki sayının OBEB'i değişmez. Sembolik olarak:
$$\gcd\!\left(\text{a},\,\text{b}\right) = \gcd\!\left(\text{b},\,\text{a} \bmod \text{b}\right)$$Bunu b = 0 olana kadar sürdürürsünüz; sıfırdan farklı son değer OBEB'tir. OKEK ise
$$\operatorname{lcm}\!\left(\text{a},\,\text{b}\right) = \frac{\left|\text{a}\right| \times \left|\text{b}\right|}{\gcd\!\left(\text{a},\,\text{b}\right)}$$formülüyle hesaplanır, çünkü iki sayının çarpımı, bu sayıların OBEB ve OKEK çarpımına eşittir.
Çözümlü Örnek
obeb(48, 36) değerini bulalım: \(48 \bmod 36 = 12\), dolayısıyla obeb(36, 12). Ardından \(36 \bmod 12 = 0\), yani OBEB 12'dir. OKEK ise
$$\frac{48 \times 36}{12} = \frac{1728}{12} = 144$$olur.
Sık Sorulan Sorular
Sayılardan biri sıfır olursa ne olur? \(\gcd\!\left(\text{a},\,0\right) = \text{a}\). Algoritma bunu doğal olarak yönetir — döngü hemen durur ve sıfırdan farklı değeri döndürür.
a ile b'nin sırası önemli mi? Hayır. \(\gcd\!\left(\text{a},\,\text{b}\right) = \gcd\!\left(\text{b},\,\text{a}\right)\); algoritma daha ilk adımda kendini düzeltir.
Negatif sayı kullanabilir miyim? Evet. OBEB geleneksel olarak pozitif tanımlandığından, araç mutlak değerleri kullanır.
