--- title: Öklid Algoritması slug: oklid-algoritmasi-64e1a url: /detay/oklid-algoritmasi-64e1a type: article language: Türkçe entity: primary: Öklid Algoritması type: article disambiguation: Öklid Algoritması ile iki sayının EBOB'unu bulun. Pratik ve etkili bir yöntem. categories: - name: Matematik slug: matematik url: /kategori/matematik tags: - Bölünebilme - Euclid - Bézout Lemma - ebob - Öklid Algoritması - Kalan - Kriptografi - Modüler aritmetik - Bilgisayar - Tam sayılar - Sayılar teorisi - Matematik - Şifreleme - Öklid - Bölme - Aritmetik author: Talha Emre Çiper created_at: 2025-06-19T16:08:38.608413+03:00 updated_at: 2026-04-20T12:50:26.659576+03:00 image: https://cdn.t3pedia.org/media/uploads/2026/04/18/P7HCa8eB2quXzMEoa592ezE2J2H5InfM.png --- # Öklid Algoritması ## Article Content **Ö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. ### Tarihsel ve Teorik Temeller Ö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. ### Matematiksel Prosedür ve Formülasyon 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 \leq r_1 < b$ 2. $b = r_1 \cdot q_2 + r_2$, burada $0 \leq r_2 < r_1$ 3. $r_1 = r_2 \cdot q_3 + r_3$, burada $0 \leq 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. ### İspat ve Doğruluk 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 > \dots \geq 0$) sonlu bir dizi olduğu için mutlaka bir noktada durur. ### Hesaplamalı Karmaşıklık ve Lame Teoremi 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. ### Uygulama Alanları Ö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. ## Academic Sources and References 1. Euclid. Euclid's Elements of Geometry. Çeviren Richard Fitzpatrick. Austin: University of Texas at Austin, 2008. Erişim Tarihi: 18 Nisan 2026. https://farside.ph.utexas.edu/Books/Euclid/Elements.pdf. 2. Johar, M. Syafiq. "Minimal Number of Steps in the Euclidean Algorithm and its Application to Rational Tangles." Rose-Hulman Undergraduate Mathematics Journal 16 (1). (2015): 56-72. Erişim Tarihi: 18 Nisan 2026. https://scholar.rose-hulman.edu/cgi/viewcontent.cgi?article=1016&context=rhumj. 3. Lodder, Jerry, David Pengelley ve Desh Ranjan. "Euclid’s Algorithm for the Greatest Common Divisor." Annals of the TRIUMPHS Society 1 (2). (2025). Erişim Tarihi: 18 Nisan 2026. https://triumphsannals.journals.publicknowledgeproject.org/index.php/triumphsannals/article/view/16873/11865. ## Related Articles - [ÖKLİD](//detay/oklid-2/llms.txt) - [Algoritmalar](//detay/algoritmalar-c8bce/llms.txt)