A modular inverse algorithm of Christina Doran, Shen Lu and Barry R. Smith

The underlying algorithm was published in New algorithms for modular inversion and representation by binary quadratic forms arising from structure in the Euclidean algorithm, Christina Doran, Shen Lu and Barry R. Smith.

If m and n are positive integers, perform the Euclidean algorithm with n² and mn + 1.

Let r be the first remainder less than n. Then either

(a) m × r ≡ 1 (mod n), in which case gcd(m,n) = 1 and r is the multiplicative inverse of m modulo n, or
(b) m × r ≢ 1 (mod n) , in which case gcd(m,n) > 1.

This is a BCMath version of the BC program inverse.