Modular inverse function, with obligatory EGCD implementation.

invmod.rb

# Extended Euclidean GCD algorithm
# Outputs k, u, and v such that ua + vb = k where k is the gcd of a and b
def egcd(a, b)
  u_a, v_a, u_b, v_b = [ 1, 0, 0, 1 ]
  while a != 0
    q = b / a
    a, b = [ b - q*a, a ]
    u_a, v_a, u_b, v_b = [ u_b - q*u_a, v_b - q*v_a, u_a, v_a ]
    # Each time, `u_a*a' + v_a*b' = a` and `u_b*a' + v_b*b' = b`
  end
  [ b, u_b, v_b ]
end

# Solve ax = 1 mod p
def invmod(a, mod)
  gcd, inverse, _ = egcd(a, mod)
  raise "No multiplicative inverse" unless gcd == 1

  inverse % mod
end