объяснение модульного задания?

Question

Я использую назначение python для своего класса программирования. вопрос требует, чтобы мы вносили некоторый вклад и делали его в виде a/b mod N, возвращая a/b mod N как целое число от 0 до n-1. Если b имеет мультипликативный обратный мод N

здесь что я сделал: например, вход >>> a = 3, b = 2, n = 7 введите вход и оцените 3/2, затем оцените 1.5mod7

однако, это не тот ответ, который хочет учитель , правильный ответ равен 5.

То, что я думал делать, это найти целое число в диапазоне (1, n), такое, что целое число * 1 mod N., что мы и хотим. однако из всех тестовых случаев, которые я получил, только пример работает таким образом. вот примеры ввода и правильного вывода

input1: 3,2,7 
input2: 14, 67, 88 
input3: 10, 3, 40 

out1:5 
out2:58 
out3:30 

я знаю ответы на некоторые вопросы не определены, и я знаю, как получить те,

я полностью потерял о том, как сделать эти три и получить он отвечает обязательный.

Answer 1

В обычной арифметике деление может быть выполнено путем умножения на инверсию. Например, инверсия 2 равна 1/2, поэтому для разделения 3 на 2 вы можете умножить 3 на 1/2. Заметим, что 2 и его обратный 1/2 умножаются на 1, что всегда верно; это определение обратного.

Модульная арифметика не допускает деления, поэтому вы должны умножить на инверсию. При работе mod 7 инверсия 2 равна 4, так как 2 * 4 = 8 = 1 (mod 7); обратным всегда является число, которое при умножении равно 1, как и в обычной арифметике. Итак, чтобы разделить 3 на 2 (mod 7), вы умножаете 3 на 4 (mod 7). Теперь 3 * 4 = 12 = 5 (мода 7), поэтому результат 5, как сказал ваш инструктор.

Вычисление модулярного инверсного числа с использованием расширенного евклидова алгоритма. Я оставлю это вам, чтобы это исправить. Есть много мест, где вы можете найти расширенный алгоритм Евклида (возможно, включая ваш учебник или заметки класса, предоставленные вам вашим инструктором). Или вы можете вернуться сюда и задать другой вопрос, если у вас возникли проблемы с вашим кодом.