Algoritmo per calcolare l'inverso di un numero modulo n in Python

Questo algoritmo calcola l'inverso modulo n di un numero

1. def esteso_euclide(a, n):
2. x0, x1, y0, y1 = 1, 0, 0, 1
3. while n != 0:
4. q, a, n = a // n, n, a % n
5. x0, x1 = x1, x0 - q * x1
6. y0, y1 = y1, y0 - q * y1
7. return a, x0, y0
9. def inverso_modulo(a, n):
10. mcd, x, y = esteso_euclide(a, n)
11. if mcd != 1:
12. return None # a non ha un inverso modulo n
13. else:
14. return x % n
16. y=inverso_modulo(5,7)
17. print(y)