Modular Inverse

Given a and modulus m, compute the modular inverse a^{-1} such that:

a * a^{-1} = 1 (mod m)

The inverse exists iff gcd(a, m) = 1.

Function signature

func ModInverse(a, m int64) (inv int64, ok bool)

Requirements

• Return ok=false if inverse does not exist or m <= 1.
• If ok=true, return inv in the range [0, m-1].

Constraints

• 1 <= |a|, m <= 1e12