euclid algoritması

• 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.