19 lines
524 B
Python
19 lines
524 B
Python
>>> def extended_gcd(aa, bb):
|
|
lastremainder, remainder = abs(aa), abs(bb)
|
|
x, lastx, y, lasty = 0, 1, 1, 0
|
|
while remainder:
|
|
lastremainder, (quotient, remainder) = remainder, divmod(lastremainder, remainder)
|
|
x, lastx = lastx - quotient*x, x
|
|
y, lasty = lasty - quotient*y, y
|
|
return lastremainder, lastx * (-1 if aa < 0 else 1), lasty * (-1 if bb < 0 else 1)
|
|
|
|
>>> def modinv(a, m):
|
|
g, x, y = extended_gcd(a, m)
|
|
if g != 1:
|
|
raise ValueError
|
|
return x % m
|
|
|
|
>>> modinv(42, 2017)
|
|
1969
|
|
>>>
|