Возведение в степень по модулю
Вычислить a^b mod m напрямую невозможно, если показатель имеет пятнадцать знаков. Калькулятор раскладывает b на двоичные разряды и последовательно возводит основание в квадрат, умножая накопленный результат на нужные степени. Количество шагов равно числу бит показателя, то есть не больше пятидесяти.
Две последние цифры и последняя цифра числа a^b выводятся отдельно: это типичная олимпиадная задача, которую можно проверить за секунды. Если a и m взаимно просты, показатель можно заменить остатком по модулю φ(m) по теореме Эйлера, и калькулятор показывает такую редукцию.
Обратный элемент и расширенный алгоритм Евклида
Число a обратимо по модулю m тогда и только тогда, когда НОД(a, m) = 1. Обратный элемент находится расширенным алгоритмом Евклида: он даёт коэффициенты Безу x и y из равенства a·x + m·y = НОД. Тогда x по модулю m и есть искомое число, а в таблице видны все шаги алгоритма.
Обратные элементы нужны в криптографии RSA, при расшифровке аффинных шифров и в алгоритмах на конечных полях. Если НОД больше единицы, калькулятор сообщает об отсутствии обратного и называет общий делитель, чтобы было понятно, как изменить задачу.
Линейные сравнения a·x ≡ b (mod m)
Сравнение разрешимо, когда НОД(a, m) делит b. После деления на g = НОД получается сравнение по модулю m/g, которое имеет единственное решение, а исходное сравнение имеет ровно g решений по модулю m, отличающихся на кратные m/g.
Калькулятор перечисляет решения, показывает приведённое сравнение и проверяет каждое умножением. Такие задачи возникают при расчёте календарных циклов, при синхронизации периодических процессов и в школьных олимпиадах по теории чисел.
Китайская теорема об остатках
Система сравнений x ≡ r₁ (mod m₁), x ≡ r₂ (mod m₂) решается объединением условий по очереди. Если модули взаимно просты, решение единственно по модулю их произведения. Если нет, система может быть несовместной, и тогда проверяется делимость разности остатков на НОД модулей.
Результат записывается в виде x ≡ x₀ (mod L), где L — наименьшее общее кратное модулей. Дополнительно показано, сколько решений попадает в отрезок от нуля до миллиона. Типичная область применения — расписания, в которых события повторяются с разными периодами.
Функции Эйлера и Кармайкла, порядок элемента
Функция Эйлера φ(m) считает числа, взаимно простые с m, а функция Кармайкла λ(m) — наименьший показатель, при котором в степени λ(m) любое число, взаимно простое с m, даёт единицу. Мультипликативный порядок конкретного a всегда делит λ(m).
Первообразный корень — элемент порядка φ(m); такие корни существуют только для m = 2, 4, pᵏ и 2pᵏ при нечётном простом p. Калькулятор определяет, существуют ли они, считает их количество и находит наименьший, а в таблице показывает степени a по модулю m до возврата к единице.
Формула расчёта
aᵇ mod m; a·x + m·y = НОД(a, m); a·x ≡ b (mod m); x ≡ rᵢ (mod mᵢ); a^φ(m) ≡ 1 (mod m)
Проверенные примеры
a = 7, b = 222, m = 1000.
7²²² mod 1000 = 49, то есть две последние цифры 49.
x ≡ 2 (mod 3), x ≡ 3 (mod 5), x ≡ 2 (mod 7).
Решение x ≡ 23 (mod 105).
a = 17, m = 3120.
Обратный элемент 2753: 17·2753 = 46801 = 15·3120 + 1.
Как пользоваться онлайн-калькулятором
- Выберите тип задачи.
- Введите число, модуль и при необходимости показатель или правую часть.
- Для системы сравнений заполните остатки и модули, при необходимости включите третье условие.
- Прочитайте ответ и изучите таблицу шагов алгоритма.