OBEB ve OKEK

EBOB ve EKOK Hesaplama

Bir sayı kümesinin En Büyük Ortak Böleni (EBOB), hepsini tam olarak bölen en büyük sayıdır ve En Küçük Ortak Katı (EKOK), hepsinin tam olarak böldüğü en küçük sayıdır. İki veya daha fazla tam sayı girin, bu hesaplayıcı ikisini de anında bulur.

Yöntem

EBOB, 2000 yılı aşkın süredir bilinen bir yöntem olan Öklid algoritması kullanılarak bulunur: kalan sıfıra ulaşana kadar tekrar tekrar büyük sayıyı küçüğe bölün ve büyük sayıyı kalanla değiştirin. Son sıfır olmayan değer EBOB’dur.

EBOB bilindiğinde, iki sayının EKOK’u doğrudan takip eder:

$$\text{EKOK}(\vA{a}, \vB{b}) = \frac{\vA{a} \times \vB{b}}{\vC{\text{EBOB}(\vA{a}, \vB{b})}}$$

İkiden fazla sayı için, bu hesaplayıcı her iki yöntemi de tüm liste boyunca ikili olarak uygular.

Örnek Hesaplama

12 ve 18’in EBOB ve EKOK’unu bulma:

1. Öklid algoritması: 18 ÷ 12’nin kalanı 6’dır; 12 ÷ 6’nın kalanı 0’dır. EBOB $\vC{6}$‘dır.
2. $\text{EKOK}(\vA{12}, \vB{18}) = (12 \times 18) \div \vC{6} = 216 \div \vC{6} = 36$.

Dikkate Alınması Gereken Önemli Faktörler

• EBOB’u 1 olan iki sayıya “aralarında asal” denir; bu gerçekten kullanışlı bir sınıflandırmadır. EBOB 1 olduğunda, iki sayı 1’den başka ortak faktör paylaşmaz — bu, kriptografi ve sayılar teorisi gibi alanlarda önemlidir ve ayrıca EKOK’larının basitçe çarpımları olduğu anlamına gelir.
• Öklid algoritması, büyük sayılar için her faktörü listelemekten çarpıcı biçimde daha hızlıdır. Her sayının tüm faktörlerini listeleyip karşılaştırarak EBOB bulmak büyük sayılar için elverişsiz hale gelir — Öklid algoritması, sayılar ne kadar büyük olursa olsun yalnızca birkaç adımda cevabı bulur; bu tam olarak 2000 yılı aşkın süredir standart yöntem olmasının nedenidir.
• EBOB ve EKOK, aynı ikili yapı taşını kullanarak ikiden fazla sayıya temiz bir şekilde genelleşir. İki sayılık formülü bir liste boyunca uygulamak — EBOB(EBOB(a,b), c) ve EKOK için de benzer şekilde — her iki kavramı da herhangi bir sayıda girdiye doğru şekilde genişletir; bu tam olarak bu hesaplayıcının ikiden uzun bir listeyi nasıl ele aldığıdır.
• Bu kavramlar, saf matematiğin dışında, zamanlama ve kaynak paylaştırma problemlerinde sürekli ortaya çıkar. Kesirleri sadeleştirmenin ötesinde, EKOK “iki tekrarlayan olay bir sonraki ne zaman hizalanır” (otobüs tarifeleri veya yanıp sönen ışıklar gibi) sorusuna cevap verir ve EBOB “bunları eşit boyutlu en büyük gruba nasıl bölebilirim” (öğeleri hiçbir şey kalmadan özdeş gruplara bölmek gibi) sorusuna cevap verir.

Yaygın Hatalar

• Hangisinin EBOB, hangisinin EKOK olduğunu karıştırmak. İsimler benzer duyulur ve yanlışlıkla birbirinin yerine kullanılması kolaydır — EBOB her zaman iki sonuçtan küçüğüdür (ortak bir bölen olduğu için en küçük girdi sayısını aşamaz), EKOK ise her zaman büyüğüdür (ortak bir kat olduğu için en büyük girdi sayısı kadar büyüktür).
• EBOB’un karşılaştırılan sayılardan biri olması gerektiğini varsaymak. Yukarıda belirtildiği gibi, EBOB her girdiyi tam olarak bölen en büyük sayıdır — 12 ve 18 için bu 6’dır, 12 veya 18’in kendisi değildir, her ikisi de girdilerden en az birini tam olarak bölse bile.
• Öklid algoritmasını kullanmak yerine büyük sayılar için her faktörü elle listelemek. Yukarıda belirtildiği gibi, sayılar büyüdükçe bu yavaş ve hataya açık hale gelir — bu hesaplayıcının kullandığı Öklid algoritması, boyuttan bağımsız olarak yalnızca birkaç adımda aynı cevabı bulur.
• Önce EBOB’a bölmeden EKOK’u elde etmek için iki sayıyı çarpmak. Yukarıda belirtildiği gibi, doğrudan çarpma yalnızca iki sayı aralarında asalsa (EBOB 1) doğru EKOK’u verir — ortak bir faktörü paylaşan sayılar için, EBOB’a bölmeyi atlamak gerçek EKOK’un bir katını üretir, EKOK’un kendisini değil.

Bilinmesi Faydalı Olanlar

• Bir kesri en sade haline indirgemek tam olarak bir EBOB hesaplamasıdır — Kesir Hesaplayıcı, bu hesaplayıcının doğrudan hesapladığı aynı EBOB’u kullanarak kesirleri sadeleştirir.
• Kesirleri toplamak veya çıkarmak için ortak bir payda bulmak tam olarak bir EKOK hesaplamasıdır — ters yönde aynı ilişki.
• Asal Çarpanlara Ayırma Hesaplayıcı ve Oran Hesaplayıcı, ikisi de farklı bir açıdan aynı ortak faktör fikrine dayanır — biri bir sayıyı asal yapı taşlarına ayırır, diğeri bir oranı en sade tam sayı biçimine indirger.