I'm sure, you should test this.  Please, test your code.
```
In [5]: modinv(10, 4)
---------------------------------------------------------------------------
TypeError                                 Traceback (most recent call last)
...
--> 157         raise Exception("%d has no invesrse modulo %d" % a, m)
...
TypeError: not enough arguments for format string
```