Малая теорема Ферма
англ. Fermat's little theorem
Если p простое и a не делится на p, то a^(p−1) ≡ 1 (mod p); главный инструмент быстрого вычисления остатков степеней и математическая основа шифра RSA.
Малая теорема Ферма — фундаментальное утверждение арифметики остатков: если — простое число, а не делится на , то . Иначе говоря, возведение в степень «сбрасывает» остаток до единицы. Ферма сформулировал теорему в 1640 году в письме к Френиклю и обещал прислать доказательство — но не прислал; первое опубликованное доказательство дал Эйлер почти сто лет спустя, в 1736-м.
Теорема — рабочая лошадка быстрых вычислений: чтобы найти остаток по модулю , понижаем степень и считаем лишь . Тот же приём — сердце шифра RSA, вероятностных тестов простоты и признаков делимости. Вторая форма удобна тем, что верна для любых , включая кратные . Для составных модулей аналог даёт теорема Эйлера с функцией Эйлера, а приложения к целочисленным уравнениям связывают теорему с диофантовыми уравнениями.
Чему равен остаток при делении на ?
Частые вопросы
Почему теорема называется «малой»?
Чтобы отличать её от Великой теоремы Ферма . Обе принадлежат одной переписке Ферма, обе остались без авторских доказательств: малую доказал Эйлер в 1736 году, великую — Уайлс только в 1995-м, через 358 лет.
Если — значит ли это, что простое?
Нет. Для составных сравнение может случайно выполняться: числа Кармайкла, наименьшее — , удовлетворяют ему для всех взаимно простых с оснований. Поэтому «тест Ферма» усилён до теста Миллера–Рабина, который такие имитаторы распознаёт.