两个数除法的模逆

Question

我知道(a/b)mod M= ab^-1 mod M

并且当M是素数时，b^-1 = b^(M-2)

我必须计算(121/2)模M，其中M= 1000000007 (1e9 + 7)

使用简单除法：(121/2)modM = (60)mod M= 60%M = 60

模逆：(121/2)mod M = (121 mod M) *(2 ^(M-2) mod M)

2 ^(M-2) mod M这里是500000004 (链接：http://www.cs.princeton.edu/~dsri/modular-inversion-answer.php?n=2&p=1000000007)

因此，上述表达式为(121 mod M* 500000004)mod M= 60500000484 mod M= 500000064。

我到底做错什么了？

Answer 1

您不能执行整数除法，并期望得到相同的结果。你的计算实际上应该是：

121/2 (mod M) = 60 + 1/2 (mod M) = 60 + 50000004 = (mod M) = 50000064

而不是

121/2 (mod M) = 60 (mod M)

由于没有关于floor函数的定义，从有理数Q到群N (仅为有理数定义为自然数，floor: Q -> N)，您应该像对待理性主义那样对待N中的除法，即使用剩馀数。