Такое x, что a × x даёт остаток 1
Поиск идёт расширенным алгоритмом Евклида. Если общий делитель больше 1, обратного нет.
a × x ≡ 1 (mod m)
Только если числа взаимно просты
3 × 5 = 15, остаток от деления на 7 равен 1. Значит, обратное к 3 по модулю 7 — это 5. Если НОД(a, m) больше 1, обратного нет, и страница не подбирает «ближайшее».
Это не обычная дробь 1/a. Для сокращения обыкновенных дробей есть дроби, для НОД — НОД и НОК.
Откуда брать числа
- Число
- Модуль
Пример
3 × 5 = 15, остаток от деления на 7 равен 1. Значит, обратное к 3 по модулю 7 — это 5.
Вопросы
Чем это отличается от обычной дроби 1/a?
Остаток — целое от 0 до m − 1, а не десятичная дробь.
Отрицательное a?
Сначала оно приводится к неотрицательному остатку.
Где пригодится?
В шифрах и в решении сравнений. Для бытовой арифметики обычно хватает обычного деления.