Глава

Ферма и Эйлер

Малая теорема Ферма, функция Эйлера, теорема Эйлера, обратные элементы и вычисления больших степеней по модулю.

Теория

1. Малая теорема Ферма Если \(p\) - простое число и \(p\nmid a\), то \[ a^{p-1}\equiv1\pmod p. \] Равносильная форма: для любого целого \(a\) \[ a^p\equiv a\pmod p. \] Эта теорема позволяет быстро упрощать большие степени по простому модулю. 2. Обратные элементы Если \(\gcd(a,m)=1\), то у \(a\) есть обратный элемент по модулю \(m\). Это значит, что существует целое \(b\), такое что \[ ab\equiv1\pmod m. \] Малая теорема Ферма дает удобный обратный элемент по простому модулю: \[ a^{-1}\equiv a^{p-2}\pmod p. \] 3. Функция Эйлера Функция Эйлера \(\varphi(n)\) считает положительные числа от \(1\) до \(n\), взаимно простые с \(n\). Например, \[ \varphi(10)=4, \] потому что \(1,3,7,9\) взаимно просты с \(10\). Если \[ n=p_1^{a_1}p_2^{a_2}\cdots p_k^{a_k}, \] то \[ \varphi(n)=n\left(1-\frac1{p_1}\right)\left(1-\frac1{p_2}\right)\cdots\left(1-\frac1{p_k}\right). \] 4. Теорема Эйлера Если \(\gcd(a,n)=1\), то \[ a^{\varphi(n)}\equiv1\pmod n. \] Малая теорема Ферма - это частный случай, когда \(n\) простое. 5. Стратегия для больших степеней Чтобы найти \(a^k\pmod n\): Проверьте, что \(\gcd(a,n)=1\). Если да, уменьшите показатель по модулю \(\varphi(n)\) или найдите более короткий цикл. Если нет, используйте разложение, простые степени или другой модуль.

Примеры

Пример 1. Ферма по модулю пять Это самый простой первый расчет по малой теореме Ферма. Задача. Найдите \(3^{2026}\pmod5\). Решение. По малой теореме Ферма \(3^4\equiv1\pmod5\). Так как \(2026\equiv2\pmod4\), получаем \(3^{2026}\equiv3^2=9\equiv4\pmod5\). Пример 2. Быстрая степень по модулю семь Короткие циклы иногда удобнее теоремы. Задача. Найдите \(2^{100}\pmod7\). Решение. Так как \(2^3=8\equiv1\pmod7\), уменьшаем показатель по модулю \(3\). Так как \(100\equiv1\pmod3\), получаем \(2^{100}\equiv2\pmod7\). Пример 3. Функция Эйлера списком Список перед формулой сохраняет смысл функции. Задача. Найдите \(\varphi(12)\), выписав положительные числа от \(1\) до \(12\), взаимно простые с \(12\). Решение. Это числа \(1,5,7,11\). Поэтому \(\varphi(12)=4\). Пример 4. Формула функции Эйлера Требуйте разложение на простые множители перед применением формулы. Задача. Найдите \(\varphi(45)\). Решение. \(\varphi(45)=45\left(1-\frac13\right)\left(1-\frac15\right)=45\cdot\frac23\cdot\frac45=24\). Пример 5. Эйлер по модулю десять Свяжите теорему Эйлера с привычными задачами на последнюю цифру. Задача. Найдите последнюю цифру числа \(7^{100}\). Решение. По теореме Эйлера \(7^4\equiv1\pmod{10}\). Так как \(100\equiv0\pmod4\), получаем \(7^{100}\equiv1\pmod{10}\). Последняя цифра равна \(1\). Пример 6. Обратный элемент по модулю одиннадцать Сначала решайте подбором, до формулы Ферма для обратного. Задача. Найдите обратный элемент к \(3\) по модулю \(11\). Решение. \(3\cdot4=12\equiv1\pmod{11}\), значит обратный элемент равен \(4\). Пример 7. Обратный через Ферма Это концептуально важно для решения сравнений. Задача. Используйте малую теорему Ферма, чтобы объяснить, почему \(a^{p-2}\) является обратным к \(a\pmod p\), если \(p\) простое и \(p\nmid a\). Решение. По малой теореме Ферма \(a^{p-1}\equiv1\pmod p\). Но \(a\cdot a^{p-2}=a^{p-1}\), значит \(a\cdot a^{p-2}\equiv1\pmod p\). Поэтому \(a^{p-2}\) является обратным к \(a\pmod p\). Пример 8. Степень через Эйлера И снова короткие циклы часто эффективнее полной теоремы Эйлера. Задача. Найдите \(5^{123}\pmod8\). Решение. Так как \(5^2=25\equiv1\pmod8\), нечетные степени \(5\) сравнимы с \(5\pmod8\). Поэтому \(5^{123}\equiv5\pmod8\).

Задачи

Пока нет опубликованных задач.

Лестницы

Опубликованных лестниц пока нет.

Предыдущая глава

Следующая глава