Ah Ed H., the good ol' Russian peasant algorithm… :D
I am rather surprised no one has put up code for the modular inverse. :P
While C≠1 and T
The inverse of A modulo M is stored in U.
gives 5, as expected.
A divide-by-zero error will occur if and only if there exists no modular inverse for A for the chosen modulus M.
This is an ingenious modification of the extended Euclidean algorithm (extended GCD), adapted for computing the modular inverse. I do not have my number theory books at hand so I cannot say where I got this program.
It shouldn't take much trouble for somebody determined enough to write a mongrel program that uses both the Russian peasant algorithm and extended GCD to compute things like 3ֿ³ (mod 13) (hint: take the inverse first before powering).
P.S. Modular roots are an even harder problem… :)