13 lines
226 B
Text
13 lines
226 B
Text
|
import integers.egcd
|
||
|
|
|
||
|
|
def modinv( a, m ) =
|
||
|
|
val (g, x, _) = egcd( a, m )
|
||
|
|
|
||
|
|
if g != 1 then error( a + ' and ' + m + ' not coprime' )
|
||
|
|
|
||
|
|
val res = x % m
|
||
|
|
|
||
|
|
if res < 0 then res + m else res
|
||
|
|
|
||
|
|
println( modinv(42, 2017) )
|