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

```
PROGRAM:MODINV
1→V:A→D
A=1→U
not(U)→T
If T:Then
int(M/A)→U
M–AU→C
While C≠1 and T
int(D/C)→Q
D–CQ→D
V+QU→V
D≠1→T
If T:Then
int(C/D)→Q
C–DQ→C
U+QV→U
End:End
Vnot(T)+T(M–U)→U
End
U
```

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).

thornahawk

P.S. Modular roots are an even harder problem… :)