Как пользоваться
- Выберите Действие: a mod n, обратный элемент, степень или китайскую теорему об остатках.
- Введите Число a, Показатель e и Модуль n там, где их спрашивают, или одно сравнение в строке в поле Сравнения (по одному в строке).
- Прочитайте Результат. Для обратного элемента поле Проверка показывает, существует ли он.
- Пройдите по Как получен результат; таблицы показывают строки Евклида или двоичные цифры.
Остатки, обратные элементы и степени
Остаток a по модулю n — это число r, для которого 0 ≤ r < n и a = q·n + r, поэтому a mod n никогда не бывает отрицательным: −17 mod 5 равно 3, потому что −17 = (−4)·5 + 3. Обратный элемент a по модулю n — это число x, для которого a·x ≡ 1 (mod n). Он существует именно тогда, когда НОД(a; n) = 1, и расширенный алгоритм Евклида его находит. Степень a^e mod n вычисляется возведением в квадрат с умножением: на каждую двоичную цифру e делается одно возведение в квадрат.
a mod n = a − n·⌊a ÷ n⌋
Если s·a + t·n = 1, то a⁻¹ ≡ s (mod n)- Многие калькуляторы выдают −2 для −17 mod 5 — это остаток усечённого деления. Это не остаток по модулю, который всегда лежит от 0 до n − 1.
- Степень с отрицательным показателем использует обратный элемент a, поэтому она существует только при НОД(a; n) = 1.
- Таблица Евклида и таблица двоичных цифр показывают каждое промежуточное число, поэтому расчёт можно проверить вручную.
Китайская теорема об остатках и что не охватывает калькулятор
Китайская теорема об остатках находит одно число x, которое даёт остаток rᵢ при делении на mᵢ для каждого сравнения системы. Если модули попарно взаимно просты, решение единственно по модулю их произведения. Если нет, остатки должны согласовываться по модулю НОД модулей, иначе решения нет.
- Очень большие показатели, у которых больше 64 двоичных цифр, не принимаются, чтобы расчёт оставался читаемым.
- Сравнения с переменной, отличной от x, полиномиальные сравнения и модульные квадратные корни не охватываются.
- Калькулятор работает только с целыми числами; десятичное число не принимается.
Пример: 4¹³ mod 497 и другие действия
Показатель 13 в двоичной записи равен 1101. Начиная с 1 и возводя в квадрат на каждом шаге, с умножением на 4 на каждой единице, получаем 4, 64, 120 и затем 445, поэтому 4¹³ mod 497 = 445. Тот же метод выполняет калькулятор, с таблицей цифр.
Другие примеры: −17 mod 5 = 3; обратный элемент 4 по модулю 7 равен 2, потому что 4 × 2 = 8 ≡ 1; а система x ≡ 2 (mod 3), x ≡ 3 (mod 5), x ≡ 2 (mod 7) имеет решение x ≡ 23 (mod 105).
| Вопрос | Ответ |
|---|---|
| 4^13 mod 497 | 445 |
| −17 mod 5 | 3 |
| Обратный элемент 4 по модулю 7 | 2 |
| x ≡ 2 (mod 3), 3 (mod 5), 2 (mod 7) | x ≡ 23 (mod 105) |
Частые вопросы
Почему −17 mod 5 равно 3, а не −2?
Остаток по модулю никогда не бывает отрицательным: 0 ≤ r < n. Так как −17 = (−4) × 5 + 3, остаток равен 3. Многие калькуляторы показывают −2 — это остаток усечённого деления, а не остаток по модулю.
Когда у числа есть обратный элемент по модулю n?
Когда наибольший общий делитель числа и n равен 1. Например, у 4 есть обратный элемент по модулю 7, это 2, но у 4 его нет по модулю 6, потому что НОД(4; 6) = 2.
Зачем степень считается возведением в квадрат, а не повторным умножением?
Возведение в квадрат с приведением на каждой двоичной цифре держит все числа небольшими. Для 4¹³ самое большое промежуточное значение равно 484 × 4 = 1936, тогда как длинное произведение дало бы число примерно из восьми цифр.
Что делать, если модули сравнений имеют общий множитель?
Система может иметь решение. Остатки должны согласовываться по модулю НОД двух модулей: x ≡ 2 (mod 4) и x ≡ 8 (mod 6) согласованы, и решение x ≡ 2 (mod 12).
Отправляются ли мои числа на сервер?
Нет. Расчёт выполняется в вашем браузере, и ничего из введённого не передаётся на сервер.
Источники
- Wikipedia (на английском): Modular arithmetic
- Wikipedia (на английском): Modular exponentiation
- Wikipedia (на английском): Extended Euclidean algorithm
- Wikipedia (на английском): Chinese remainder theorem
Цифры и текст в последний раз проверены вторник, 10 ноября 2026 г..