Чему равно (7^-5) mod 17
Мне нужно решить данный пример, ответом которого должно быть натуральное число - найти значение
Я пробовал решать так: 7 в степени -5 - это дробь 1/16807, но дальше ничего не могу сделать - эту дробь никак не поделишь с остатком на 17, чтобы получилось целое число.
Ответы (1 шт):
Автор решения: Harry
→ Ссылка
Ну, обратим 7 по модулю 17. Можно поиграться подбором, можно воспользоваться тем, что 7 и 17 взаимно простые и использовать функцию Эйлера (см., например, тут) - в результате при обращении 7 по модулю 17 получаем 5 (чтоб было понятнее: 7*5 == 1 (mod 17)):
Дальше просто ищем
Вот и ответ:
