euclid algoritması

• 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.
• (bkz: öklid bölme algoritması)
• 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.
• rsa (bkz: asimetrik şifreleme)