Модульная Инверсный с участием деление двух чисел

Question

Я знаю, что (A/B) по модулю М = аб^-1 по модулю M

, а также, что, когда М простое, то Ь^-1 = Ь^(М-2)

Я должен вычислить (121/2) по модулю М, где М = 1000000007 (1e9 + 7)

Используя простое разделение: (121/2) МПМ = (60) по модулю М = 60% M =

Использование модуля r Inverse: (121/2) mod M = ((121 mod M) * (2^(M-2) mod M)) mod M.

2^(M-2) mod M здесь 500000004 (ссылка: http://www.cs.princeton.edu/~dsri/modular-inversion-answer.php?n=2&p=1000000007)

поэтому приведенное выше выражение становится (121 мод M * 500000004) по модулю М = 60500000484 мод M =

Что я, возможно, делают неправильно?

Answer 1

Вы не можете выполнить целочисленное деление и ожидать получить тот же результат. You расчет должен быть действительно:

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

и не

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

Поскольку не существует определение floor функции из рациональных чисел Q в группу Z_n (определяется только для рациональных чисел в натуральные числа, floor: Q -> N), вы должны относиться к разделам в Z_n так же, как с рациональными, используя остатки.