найти мод A / B C

Question

Я знаю, что это может показаться математическим вопросом, но я только что видел это на конкурсе и очень хочу знать, как его решить.

У нас есть

а (мод с)

и

b (mod c)

и мы ищем значение частного

(а / б) (мод с)

Есть идеи?

Answer 1

В кольце целых чисел по модулю C эти уравнения эквивалентны:

A / B (mod C)
A * (1/B) (mod C)
A * B ^-1 (mod C).

Таким образом, вам нужно найти B ^-1 , мультипликативную инверсию B по модулю C. Вы можете найти его, например, с помощью расширенный алгоритм Евклида.

Обратите внимание, что не каждое число имеет мультипликативный обратный для данного модуля.

В частности, B ^-1 существует тогда и только тогда, когда gcd(B, C) = 1 (т.е. B и C взаимно просты).

Смотри также

• Википедия / Модульное мультипликативное обратное
• Википедия / Расширенный евклидов алгоритм

---

Модульное мультипликативное обратное: пример

Предположим, мы хотим найти мультипликативную инверсию 3 по модулю 11.

То есть мы хотим найти

x = 3 ^-1 (mod 11)
x = 1/3 (mod 11)
3x = 1 (mod 11)

Используя расширенный алгоритм Евклида, вы обнаружите, что:

x = 4 (mod 11)

Таким образом, модульное мультипликативное обратное 3 по модулю 11 равно 4. Другими словами:

A / 3 == A * 4 (mod 11)

---

Наивный алгоритм: поиск методом перебора

Один из способов решить эту проблему:

3x = 1 (mod 11)

Нужно просто попробовать x для всех значений 0..11 и посмотреть, верно ли уравнение. Для небольшого модуля этот алгоритм может быть приемлемым, но расширенный алгоритм Евклида намного лучше асимптотически.

Answer 2

Я думаю, это можно записать как (но не уверен)

(a/b)%c = ((a)%(b*c))/b

Answer 3

Существует много возможных ответов. Когда все, что у вас есть, это k = B mod C, то B может быть любым k + CN для всех целых чисел N.

Это означает, что B потенциально может быть очень большим. Настолько велико, что A / B приближается к нулю.

Однако это только один из способов ответа.