Условие
Найдите x из диапазона 0≤x<43, для которого 17x≡1 (mod 43). Почему обратный элемент существует?
Решение по шагам
Числа 17 и 43 взаимно просты. Деления Евклида: 43=2·17+9; 17=9+8; 9=8+1. Обратная подстановка даёт 1=9−8=2·9−17=2·43−5·17. Поэтому коэффициент при 17 равен −5, и x≡−5≡38 (mod 43).
Существование следует из тождества Безу. Если бы общий делитель был больше единицы, левая часть 17x и число 43 делились бы на него, а остаток 1 — нет.
Проверка результата
17·38=646=15·43+1. Перебор 43 остатков находит ровно одно решение в заданном диапазоне.
Типичная ошибка
Деление по модулю не является обычным делением действительных чисел. Оно требует существования обратного элемента.
Что даёт этот метод
Обратный к a по модулю m существует ровно при НОД(a,m)=1. При его наличии сравнение ax≡b решается умножением на обратный элемент.
Дальше по теме
Комбинаторика и дискретная математика: другие задачи и разборы.
Учебное условие и объяснение сформулированы редакцией damirock.com. Это самостоятельный разбор, а не официальный билет или ключ экзамена. Числа относятся к модели задачи.