21 lines
270 B
Text
21 lines
270 B
Text
func mod_inv a b .
|
|
b0 = b
|
|
x1 = 1
|
|
if b = 1
|
|
return 1
|
|
.
|
|
while a > 1
|
|
q = a div b
|
|
t = b
|
|
b = a mod b
|
|
a = t
|
|
t = x0
|
|
x0 = x1 - q * x0
|
|
x1 = t
|
|
.
|
|
if x1 < 0
|
|
x1 += b0
|
|
.
|
|
return x1
|
|
.
|
|
print mod_inv 42 2017
|