Öklid Algoritması ile EBOB Hesaplama (Adım Adım)
Öklid (Euclid) algoritması nedir, EBOB nasıl bulunur? Bölme adımları, ispatın mantığı ve büyük sayılarla çözümlü örnekler.
Öklid algoritması, iki sayının EBOB'unu bulmanın en eski ve en hızlı yoludur. MÖ 300 civarında Öklid'in Elementler adlı eserinde yer alan bu yöntem, bugün hâlâ bilgisayarların EBOB hesaplamak için kullandığı standart algoritmadır. Asal çarpanlara ayırmaya gerek kalmadan, yalnızca bölme ve kalan işlemleriyle çalışır — bu yüzden çok büyük sayılarda bile ışık hızındadır.
Algoritmanın Kuralı
Yöntem tek bir gözleme dayanır:
Yani büyük sayıyı küçükle böldüğünüzde, EBOB değişmeden "bölen ve kalan" çiftine taşınır. Kalan 0 olana dek tekrar edilir; son sıfırdan önceki kalan, EBOB'dur.
Neden çalışır? d sayısı hem a'yı hem b'yi bölüyorsa, a = q·b + r eşitliğinden r = a − q·b'nin de d ile bölündüğü çıkar. Tersine d hem b'yi hem r'yi bölüyorsa a = q·b + r'den a'yı da böler. Dolayısıyla (a, b) çiftinin ortak bölenleri ile (b, r) çiftinin ortak bölenleri birebir aynıdır; en büyüğü de öyle.
Adım Adım Uygulama
Örnek — EBOB(180, 48):
Adım 1: 180 = 3 × 48 + 36 → yeni çift (48, 36)
Adım 2: 48 = 1 × 36 + 12 → yeni çift (36, 12)
Adım 3: 36 = 3 × 12 + 0 → kalan 0, dur!
Sonuç: EBOB(180, 48) = 12 (son sıfırdan önceki kalan)
Örnek — EBOB(1071, 462):
1071 = 2 × 462 + 147
462 = 3 × 147 + 21
147 = 7 × 21 + 0
EBOB = 21
Algoritmayı kendiniz denemek için EBOB EKOK hesaplama aracımız iki sayı girdiğinizde Öklid adımlarını otomatik olarak gösterir.
Pratik Kurallar ve İpuçları
- Sayıların sırası önemli değildir; yine de büyük olanı önce yazmak ilk adımı kısaltır: EBOB(a, b) = EBOB(b, a).
- Kalan 0 çıkarsa (b, a'yı tam bölüyorsa) EBOB doğrudan b'dir: EBOB(6, 18) = 6.
- Algoritma daima sonludur: her adımda kalan bir öncekinden küçüldüğü için en geç b adım içinde 0'a ulaşılır. Pratikte adım sayısı, sayıların basamak sayısıyla orantılıdır (Lamé teoremi: adım sayısı, küçük sayının basamak sayısının 5 katını geçmez).
- Üç sayı için algoritmayı zincirleyin: EBOB(a, b, c) = EBOB(EBOB(a, b), c).
Asal Çarpan Yöntemiyle Karşılaştırma
| Ölçüt | Öklid Algoritması | Asal Çarpanlara Ayırma |
|---|---|---|
| Gereken işlem | Bölme ve kalan | Sayıları çarpanlarına ayırma |
| Büyük sayılarda hız | Çok hızlı | Yavaş (çarpanlara ayırmak zor) |
| Öğrenme kolaylığı | Orta | Kolay (görsel) |
| EKOK'u da verir mi? | Doğrudan hayır; ama EKOK = a·b/EBOB ile bulunur | Evet, aynı tablodan |
| Sınav kullanımı | KPSS/ALES'te pratik | 6. sınıf/LGS'de standart |
İpucu: EBOB'u Öklid ile bulduktan sonra EKOK'u asal çarpanlara hiç girmeden hesaplayabilirsiniz: EKOK(a, b) = (a × b) / EBOB(a, b). Örneğin EBOB(180, 48) = 12 ise EKOK = 180·48/12 = 720. Bu köprü eşitliğin ispatı: [EBOB × EKOK kuralı](/rehber/ebob-carpi-ekok-kurali/)
Algoritmanın Modern Kullanımları
Öklid algoritması yalnızca bir okul konusu değildir:
- Kesir sadeleştirme motorları (pay ve paydanın EBOB'u) bu algoritmayı kullanır → Kesir sadeleştirme aracı
- Kriptografi: RSA şifrelemesinde modüler tersinir hesaplamaların temeli, genişletilmiş Öklid algoritmasıdır.
- Bilgisayar bilimi: Yazılımlarda GCD fonksiyonları (ör. Python'daki
math.gcd) Öklid algoritmasını uygular. - Müzik teorisi ve ritim: Öklidyen ritimler, vuruşların eşit dağıtımında bu algoritmanın kalıp yapısını kullanır.
Sık Sorulan Sorular
Öklid algoritması EKOK'u da bulur mu?
Doğrudan EBOB'u bulur; EKOK ise bulunan EBOB üzerinden tek adımda gelir: EKOK(a,b) = (a × b) / EBOB(a,b). Sitemizdeki araç bu iki adımı birlikte gösterir.
Algoritma neden "genişletilmiş" hâlde de öğretilir?
Genişletilmiş Öklid algoritması, EBOB'u a ve b'nin tam sayı katlarının toplamı olarak da yazar: EBOB(a,b) = x·a + y·b (Bézout özdeşliği). Bu biçim, modüler aritmetikte ters eleman bulmak için kullanılır; ortaöğretimde zorunlu değildir.
Kalan negatif çıkabilir mi?
Hayır. Bölme algoritmasında kalan daima 0 ≤ r < b aralığındadır. Negatif sayılarla çalışırken önce mutlak değer alın: EBOB(−12, 18) = EBOB(12, 18) = 6.
LGS'de Öklid algoritması kullanmak zorunda mıyım?
Hayır; müfredat ağırlıklı olarak asal çarpanlara ayırmayı esas alır. Ancak Öklid, işlem hatası riskini azaltan hızlı bir sağlamadır ve büyük sayılı sorularda ciddi zaman kazandırır: LGS'de EBOB EKOK soruları
Matematik eğitim içerikleri üzerinde çalışan editör ekibimiz; her yazıyı güncel müfredata göre hazırlar, örnekleri tek tek doğrular ve düzenli olarak günceller. Yayın politikamız →