Калькулятор теоремы Эйлера
Применяйте теорему Эйлера онлайн: введите основание a и модуль n (взаимно простые), и калькулятор вычислит функцию Эйлера φ(n) и a^φ(n) mod n, что по теореме всегда равно 1 при выполнении её условий.
Вычисление степеней по модулю с помощью теоремы Эйлера
Формула теоремы Эйлера
Где:
- \(a\) — основание, целое число, взаимно простое с \(n\)
- \(n\) — модуль, положительное целое число
- \(\phi(n)\) — функция Эйлера: количество целых чисел от \(1\) до \(n\), взаимно простых с \(n\)
- \(\equiv 1 \pmod{n}\) — левая и правая части дают одинаковый остаток \(1\) при делении на \(n\)
Теорема утверждает, что если \(a\) и \(n\) не имеют общих делителей, кроме 1, то возведение \(a\) в степень \(\phi(n)\) всегда даёт \(1\) по модулю \(n\). Это позволяет сводить очень большие показатели степени в модульной арифметике к гораздо меньшим.
Теорема Эйлера — пример вычисления
Пример: проверим теорему Эйлера для \(a = 3\) и \(n = 7\) (значения по умолчанию в калькуляторе).
Шаг 1: проверим, что \(a\) и \(n\) взаимно просты:
\[ \gcd(3, 7) = 1 \quad \checkmark \]
Шаг 2: вычислим функцию Эйлера от \(n\). Среди чисел \(1, 2, \dots, 6\) взаимно простыми с \(7\) являются все шесть, поэтому:
\[ \phi(7) = 6 \]
Шаг 3: возведём основание в эту степень и приведём по модулю:
\[ 3^{6} = 729 \equiv 1 \pmod{7} \]
Результат: \(a^{\phi(n)} \bmod n = 1\), в точности как и предсказывает теорема Эйлера.
Как пользоваться калькулятором
- Введите целое основание \(a\) в поле Основание (a).
- Введите модуль \(n\) в поле Модуль (n). Для осмысленного результата используйте значение больше 1.
- Прочитайте два результата: Функция Эйлера φ(n) показывает, сколько чисел меньше \(n\) взаимно просты с ним, а a^φ(n) mod n — значение степени по модулю.
- Если вы видите сообщение «a и n должны быть взаимно простыми», выберите другую пару — теорема Эйлера неприменима при \(\gcd(a, n) > 1\).
Что такое теорема Эйлера?
Теорема Эйлера, сформулированная Леонардом Эйлером в 1763 году, — один из центральных результатов теории чисел. Она утверждает, что если целое число \(a\) не имеет с \(n\) общих делителей, кроме 1, то \(a^{\phi(n)}\) даёт остаток \(1\) при делении на \(n\). Ключевая величина здесь — функция Эйлера \(\phi(n)\), которая считает, сколько целых чисел от \(1\) до \(n\) взаимно просты с \(n\). Для простого \(p\) подходят все числа от \(1\) до \(p-1\), поэтому \(\phi(p) = p - 1\).
Теорема обобщает малую теорему Ферма: при простом \(n = p\) получается \(a^{p-1} \equiv 1 \pmod{p}\), что в точности совпадает с утверждением Ферма. В свою очередь, версия Эйлера работает для любого модуля, простого или составного, лишь бы основание и модуль были взаимно просты.
На практике теорема служит мощным вычислительным приёмом. Чтобы вычислить, например, \(a^{k} \bmod n\) с огромным показателем \(k\), можно заменить \(k\) на \(k \bmod \phi(n)\), поскольку показатели повторяются с периодом \(\phi(n)\). Именно это сведение позволяет быстро выполнять модульное возведение в степень с очень большими числами — свойство, на котором основана современная криптография.
Более того, теорема Эйлера — краеугольный камень шифрования RSA. Закрытый показатель расшифрования выбирается так, чтобы \(e \cdot d \equiv 1 \pmod{\phi(n)}\), что гарантирует восстановление исходного сообщения при возведении шифротекста в степень \(d\). Без теоремы Эйлера корректность RSA доказать невозможно.
Условия применимости, ограничения и советы
- Требуется взаимная простота. Теорема выполняется только при \(\gcd(a, n) = 1\). Калькулятор проверяет это и в случае нарушения выводит сообщение об ошибке. Например, пара \(a = 4\), \(n = 6\) не подходит, так как оба числа делятся на 2.
- Модуль должен быть не меньше 2. При \(n = 1\) любое целое число сравнимо с \(0\), и утверждение вырождается. Вводите \(n > 1\).
- Результат всегда равен 1. При выполнении условий \(a^{\phi(n)} \bmod n = 1\) по определению — калькулятор служит инструментом проверки и обучения. Чтобы действительно упростить произвольный показатель, сначала приведите его по модулю \(\phi(n)\), а затем используйте быстрое возведение в степень по модулю.
- Вычисление \(\phi(n)\). Этот калькулятор считает взаимно простые числа напрямую, что удобно для небольших модулей. Для больших \(n\) с известным разложением используйте формулу \(\phi(n) = n \prod_{p \mid n} \left(1 - \tfrac{1}{p}\right)\).
- Смежные инструменты. Чтобы найти число, которое «отменяет» умножение на \(a\) по модулю \(n\), воспользуйтесь калькулятором обратного элемента по модулю; для решения систем сравнений см. калькулятор китайской теоремы об остатках.
Часто задаваемые вопросы
Как вычислить теорему Эйлера вручную?
Сначала убедитесь, что \(\gcd(a, n) = 1\). Затем посчитайте, сколько целых чисел от 1 до \(n\) не имеют общих делителей с \(n\) — это количество и есть \(\phi(n)\). Наконец, вычислите \(a^{\phi(n)}\) и разделите на \(n\); остаток будет равен 1. Например, при \(a = 5\), \(n = 12\): взаимно простые числа — это 1, 5, 7, 11, поэтому \(\phi(12) = 4\) и \(5^4 = 625 = 52 \times 12 + 1\).
Почему калькулятор выдаёт ошибку для некоторых значений?
Ошибка появляется, когда основание и модуль не взаимно просты, то есть \(\gcd(a, n) > 1\). Например, \(a = 6\) и \(n = 9\) оба делятся на 3, поэтому теорема Эйлера к этой паре просто неприменима. Измените основание или выберите другой модуль. Также убедитесь, что \(n > 1\), поскольку при \(n = 1\) утверждение вырождается.
Как быстро вычислить функцию Эйлера φ(n) для больших чисел?
Перебор взаимно простых чисел по одному работает только для небольших \(n\). Если известно разложение на простые множители, используйте формулу произведения \(\phi(n) = n \prod_{p \mid n} \left(1 - \tfrac{1}{p}\right)\). Например, \(n = 36 = 2^2 \cdot 3^2\), поэтому \(\phi(36) = 36 \cdot \tfrac{1}{2} \cdot \tfrac{2}{3} = 12\). Если \(n\) простое, то \(\phi(n) = n - 1\), и раскладывать на множители не нужно.
Чем теорема Эйлера отличается от малой теоремы Ферма?
Малая теорема Ферма — это частный случай теоремы Эйлера, когда модуль прост: \(a^{p-1} \equiv 1 \pmod{p}\). Эйлер обобщил её в 1763 году на любой модуль \(n\), простой или составной, заменив показатель \(p-1\) на \(\phi(n)\). Таким образом, версия Эйлера охватывает и такие случаи, как \(n = 15\) или \(n = 100\), о которых исходное утверждение Ферма ничего не говорит.
Может ли результат быть отличным от 1?
Нет — при \(\gcd(a, n) = 1\) и \(n > 1\) результат гарантированно равен ровно 1. В этом и состоит весь смысл теоремы. Если получается другое значение, значит, входные данные нарушают условия (чаще всего из-за скрытого общего делителя). Если вам нужно \(a^k \bmod n\) с произвольным показателем \(k\), сначала приведите \(k\) по модулю \(\phi(n)\) и воспользуйтесь инструментом модульного возведения в степень.
Где теорема Эйлера применяется в реальной жизни?
Её самое известное применение — шифрование RSA. Закрытый ключ RSA \(d\) выбирается так, чтобы \(e \cdot d \equiv 1 \pmod{\phi(n)}\), и именно теорема Эйлера гарантирует, что расшифрование шифротекста восстанавливает исходное сообщение. Тот же приём сведения показателя \(a^k \equiv a^{k \bmod \phi(n)} \pmod{n}\) обеспечивает быстроту модульной арифметики с огромными числами в криптографии и информатике.
Каков наименьший показатель, дающий 1, и как он связан с φ(n)?
Наименьший положительный показатель \(k\), при котором \(a^k \equiv 1 \pmod{n}\), называется мультипликативным порядком \(a\) по модулю \(n\). Теорема Эйлера гарантирует, что этот порядок существует и всегда делит \(\phi(n)\), но часто он меньше. Например, \(\phi(7) = 6\), однако порядок \(2\) по модулю 7 равен всего 3, поскольку \(2^3 = 8 \equiv 1 \pmod{7}\).