mod p の世界における割り算とは(Ruby)

qiita.com
mod p における「逆元」を考えるとよいそう。

Ruby で実装する(元は C++)。

def modinv(a, m)
  b, u, v = m, 1, 0
  until b.zero?
    t = a / b
    a -= t * b
    a, b = b, a
    u -= t * v
    u, v = v, u
  end
  u %= m
  u += m if u < 0
  u
end