Öklid Algoritması (OBEB)

Matematik / Sayı Teorisi O(log min(a, b)) O(1)

(a, b) çiftini kalan sıfır olana dek (b, a mod b) ile değiştirerek en büyük ortak böleni hesaplar.

gcd(252,105)

1/12

gcd(252, 105) bulunuyor.

Değişmezgcd(a, b) = gcd(b, a mod b) olduğundan her adım cevabı değiştirmeden çifti küçültür.

euclidean-gcd.c

int gcd(int a, int b) {
    while (b != 0) {
        int r = a % b;    /* a = q*b + r */
        a = b;
        b = r;
    }
    return a;
}

Öklid Algoritması (OBEB) nasıl çalışır?

gcd(a, b) = gcd(b, a mod b): a ve b'nin her ortak böleni kalanı da böler. Kalanlar hızla küçülür — her iki adımda en az yarıya — zincir logaritmiktir.

Ne zaman kullanılır?

Kesir sadeleştirme, a·b/gcd ile OKEK, modüler aritmetik rutinlerinin temeli.