Малая теорема Ферма — одно из ключевых утверждений теории чисел, сформулированное Пьером де Ферма в 1640 году. Теорема утверждает: если p — простое число, а a — целое число, не делящееся на p, то a^(p-1) ≡ 1 (mod p). В более общей форме: a^p ≡ a (mod p) для любого целого a.
Представьте часы с p делениями. Если вы умножаете число само на себя p раз, результат по модулю p совпадает с исходным числом. Это как если бы стрелка часов после полного оборота вернулась на то же место.
История открытия
Ферма сформулировал теорему в письме к Фрейнклю де Бесси 18 октября 1640 года, но не оставил доказательства. Первое полное доказательство опубликовал Эйлер в 1736 году, спустя почти столетие. Эйлер обобщил теорему Ферма, создав функцию φ(n) (функция Эйлера), которая работает для составных чисел.
Математическая формулировка
Основная форма: Если p — простое число и a не делится на p, то a^(p-1) ≡ 1 (mod p).
Общая форма: Для любого целого a и простого p справедливо a^p ≡ a (mod p).
Пример: Возьмём p = 7 и a = 2. Тогда 2^6 = 64 ≡ 1 (mod 7), так как 64 = 9 × 7 + 1. Это подтверждает теорему: 2^(7-1) даёт остаток 1 при делении на 7.
Применение в криптографии
Малая теорема Ферма — основа алгоритма RSA, который защищает интернет-платежи и электронную почту. В RSA используется свойство: если ed ≡ 1 (mod φ(n)), то (m^e)^d ≡ m (mod n). Это позволяет зашифровать сообщение открытым ключом e и расшифровать закрытым ключом d.
Тест простоты Ферма: Если для числа n выполняется 2^(n-1) ≡ 1 (mod n), то n с большой вероятностью простое. Тест работает быстро, но не гарантирует точность: числа Кармайкла (561, 1105) проходят тест, но не являются простыми.
Доказательство через комбинаторику
Рассмотрим p бусин a цветов. Количество способов составить ожерелье — a^p. Если вращать ожерелье, получаем p одинаковых позиций. Вычитаем однотонные ожерелья (их a штук) и делим на p: (a^p - a) / p — целое число. Следовательно, a^p ≡ a (mod p).
Обобщения
Теорема Эйлера: Если НОД(a, n) = 1, то a^φ(n) ≡ 1 (mod n), где φ(n) — количество чисел от 1 до n, взаимно простых с n. Малая теорема Ферма — частный случай для простых p, где φ(p) = p - 1.
Китайская теорема об остатках: Позволяет решать систему сравнений по разным модулям, используя малую теорему Ферма для нахождения обратных элементов.
Связь с большой теоремой Ферма
Несмотря на схожесть названий, малая и большая теоремы Ферма не связаны математически. Большая теорема (x^n + y^n = z^n не имеет решений для n > 2) доказана Эндрю Уайлсом в 1995 году после 358 лет попыток. Малая теорема доказана Эйлером уже в XVIII веке и активно применяется в вычислительной математике.
Практическое значение
Малая теорема Ферма используется в современных процессорах для быстрого вычисления степеней по модулю. Алгоритм бинарного возведения в степень с малой теоремой Ферма позволяет шифровать данные в банкоматах за миллисекунды. Без этой теоремы онлайн-банкинг работал бы в сотни раз медленнее.