şükela:  tümü | bugün
  • a ile b iki tamsayi olsun obeb'ini ariyoruz diyelim. bolme kuralina gore, her x y tamsayilari oyle q ve r tamsayilari vardir ki x = q*y + r ve 0 <= r <= b dogru olur.
    buna itinaden, oyle q0 ve r0 vardir ki
    a = b*q0 + r0
    simdi, oyle q1 ve r1 sayilari vardir ki
    b = r0*q1 + r1
    ayni sekilde
    r0 = r1*q2 + r2
    boyle devam ederekten, herhangi bir n icin
    r(n-1) = r(n)*q(n+1) + r(n+1)
    r(n) = r(n+1)*q(n+2) + 0

    bu durumda r(n+1) a ile b'nin obebidir

    mesela 480 ile 84
    480 = 84*5 + 60
    84 = 60*1 + 24
    60 = 24*2 + 12
    24 = 12*2 + 0

    bu durumda 480 ile 84'un obebi 12'dir.
  • bu algoritma kullanılarak a sayısının mod* m'deki tersi bulunabilir (a ve m sayılarının aralarında asal olma koşuluyla)
    bunun için obeb bulmak için yapılan işlemlerin tersi yapılır.

    elde ettiğimiz denklemler
    r(n+1) = r(n-1) - r(n)*q(n+1)
    r(n) = r(n-2) - r(n-1)*q(n)
    ...
    r1 = b - r0*q1
    ro = a - b*q0
    şeklinde yazılıp sırasıyla bir üstteki denklemdeki uygun yere konulunca
    (örnek: r1 = b - r0*q1 & ro = a - b*q0 => r1 = b - (a - b*q0)*q1)
    obeb(a,m) = s*a + t*m şeklinde bir denklem elde edilir.

    a ve m aralarında asal oldukları için obeb(a,m)=1 dir
    1 = s*a + t*m olur
    bu denklem mod m'de yazılırsa
    1 = s*a (mod m) olur (m sayısı mod m'de 0 olduğu için t*m de sıfırdır)
    s burada a'nın mod m'deki tersidir.
  • pascal da ise soyle

    var i, j : integer;
    begin
    read (i, j);
    while i <> j do
    if i > j then i := i – j
    else j := j – i;
    writeln (i)
    end.
  • iyi bir universitede bilgisayar muhendisligi okudum ve bu kuraldan universiteden mezun olana kadar haberim olmadi. egitim sistemimiz bu kadar boktanmis demek ki.

    scheme versiyonu:

    (define (gcd a b) (if (= b 0) a (gcd b (=remainder a b))))
  • cisim üzerindeki polinomlar için de geçerlidir. tam sayılarda sayılar birbirinden küçük ya da büyük olmalarına göre kıyaslanırken, polinomlar için dereceler kıyaslanmalıdır.
  • iki sayının eboblarını bulmanın dışında, lineer çarpım şeklinde yazılmalarını da sağlar.

    örneğin : 38 ile 111y sayılarını ebobunu bularak ebobu sayıların lineer birleşimi şeklinde yazacak olursak ;

    38x+111y=z olacak şekilde x y ve z arıyoruz.

    111=2.38+35
    38=1.35+3
    35=11.3+2
    3=1.2+1
    2=2.1+0

    sıfırdan bir önceki kalan ebob olmak üzere ebobu tersten yazmaya başlarsak ;

    1=3-1.2=3-(35-11.3)=12.3-1.35=12.(1.38-1.35)-1.35=12.38-13.35=12.38-13(1.111-2.38)=38.38-13.111=38.38-111.13

    olup 111.(-13)+38.38=1 yazılırsa x=-13, y=38 ve z=1 bulunur.
  • iki dogal sayinin en buyuk ortak bolenini bulmak icin kullanilir.

    ornegin 36 ve 15'in ebob'unu oklid algoritmasina gore bulalim.
    36=2.15+6
    15=2.6+3
    6=2.3+0 oldugundan ebob(36,15)=3'tur.

    (bkz: ebob)
    (bkz: obeb)
  • http://people.cis.ksu.edu/…xercises/euclid_alg.html

    ilgili linkteki son implementasyonu bir hos.
  • rekürsif olarak şöyledir:

    euclid(a, b)
    if b=0 return a
    else return euclid(b, amodb)