def modinv(k, prime)
      k = k % prime
      r = (k < 0) ? -gcd_decomposition(prime,-k)[2] : gcd_decomposition(prime,k)[2]
      return (prime + r) % prime
    end
def modinv(k, prime)
      k = k % prime
      r = (k < 0) ? -gcd_decomposition(prime,-k)[2] : gcd_decomposition(prime,k)[2]
      return (prime + r) % prime
    end
Gives the multiplicative inverse of k mod prime. In other words (k * modInverse(k)) % prime = 1 for all prime > k >= 1