В теории чисел малая теорема Ферма утверждает, что если p — простое число , то для любого целого числа a число a p − a является целым кратным p . В обозначениях модульной арифметики это выражается как
Например, если a = 2 и p = 7 , то 2 · 7 = 128 , а 128 − 2 = 126 = 7 × 18 является целым числом, кратным 7 .
Если a не делится на p , то есть если a взаимно просто с p , то малая теорема Ферма эквивалентна утверждению, что a p − 1 − 1 является целым кратным p , или в символах: [1] [2]
Например, если a = 2 и p = 7 , то 2 · 6 = 64 , а 64 − 1 = 63 = 7 × 9 кратно 7 .
Малая теорема Ферма является основой для теста Ферма на простоту и является одним из фундаментальных результатов элементарной теории чисел . Теорема названа в честь Пьера де Ферма , который сформулировал ее в 1640 году. Она называется «малой теоремой», чтобы отличать ее от Великой теоремы Ферма . [3]
Пьер де Ферма впервые сформулировал теорему в письме от 18 октября 1640 года своему другу и доверенному лицу Френикле де Бесси . Его формулировка эквивалентна следующей: [3]
Если p — простое число, а a — любое целое число, не делящееся на p , то a p − 1 − 1 делится на p .
Первоначальное утверждение Ферма было
Tout nombre premier mesure infailliblement une des puissance de quelque Progressive que ce soit, et l'exposant de la dite puissance est sous-multiple du nombre Premier Donné ; И, после того, как нашел премьеру силы, которая удовлетворяет вопрос, toutes celles dont les exposants sont Multiples de l'exposant de la première satisfont tout de même à la вопросом.
Это можно перевести, добавив в скобках пояснения и формулы для облегчения понимания, как:
Каждое простое число [ p ] обязательно делит одну из степеней минус один любой [геометрической] прогрессии [ a , a2 , a3 , … ] [то есть существует t такое, что p делит at – 1 ] , и показатель этой степени [ t ] делит данное простое число минус один [делит p – 1 ]. После того, как найдена первая степень [ t ], удовлетворяющая вопросу, все те, показатели степени которых кратны показателю первой, удовлетворяют аналогично вопросу [то есть все кратные первого t обладают тем же свойством].
Ферма не рассматривал случай, когда a кратно p, и не доказал своего утверждения, а лишь указал: [4]
Et cette proposition est généralement vraie en toutes Progressions et en tous nombres Premieres; de quoi je vous envoierois la démonstration, si je n'apprehendois d'etre trop long.
(И это утверждение в целом верно для всех рядов [ sic ] и для всех простых чисел; я бы послал вам его демонстрацию, если бы не боялся, что это будет слишком долго.) [5]
Эйлер представил первое опубликованное доказательство в 1736 году в статье под названием «Theorematum Quorundam ad Numeros Primos Spectantium Demonstratio» (на английском языке: «Доказательство некоторых теорем о простых числах») в Трудах Санкт -Петербургской академии [6] [7], но Лейбниц дал практически такое же доказательство в неопубликованной рукописи, датированной примерно 1683 годом. [3]
Термин «Малая теорема Ферма» был, вероятно, впервые использован в печати в 1913 году в работе Курта Гензеля «Zahlentheorie » : [8]
Для лучшей группы, которая занимается фундаментальными вопросами, если вы хотите, чтобы ферма была рождена для вас, мы должны быть специально обучены, чтобы узнать больше о Фермате.
(В каждой конечной группе существует фундаментальная теорема, обычно называемая малой теоремой Ферма, поскольку Ферма был первым, кто доказал ее весьма частную часть.)
Раннее использование этого термина в английском языке встречается в работе А. А. Альберта « Современная высшая алгебра» (1937), где на странице 206 упоминается «так называемая „малая“ теорема Ферма». [9]
Некоторые математики независимо друг от друга выдвинули связанную гипотезу (иногда неправильно называемую китайской гипотезой), что 2 p ≡ 2 (mod p ) тогда и только тогда, когда p — простое число. Действительно, часть «если» верна, и это частный случай малой теоремы Ферма. Однако часть «только если» ложна: например, 2 341 ≡ 2 (mod 341) , но 341 = 11 × 31 является псевдопростым числом по основанию 2. См. ниже.
Известно несколько доказательств малой теоремы Ферма. Часто ее доказывают как следствие теоремы Эйлера .
Теорема Эйлера является обобщением малой теоремы Ферма: для любого модуля n и любого целого числа a, взаимно простого с n , имеем
где φ ( n ) обозначает функцию Эйлера (которая подсчитывает целые числа от 1 до n , которые взаимно просты с n ). Малая теорема Ферма действительно является особым случаем, потому что если n — простое число, то φ ( n ) = n − 1 .
Следствием теоремы Эйлера является: Для каждого положительного целого числа n , если целое число a взаимно просто с n , то для любых целых чисел x и y . Это следует из теоремы Эйлера, поскольку, если , то x = y + kφ ( n ) для некоторого целого числа k , и имеем
Если n — простое число, это также является следствием малой теоремы Ферма. Это широко используется в модульной арифметике , поскольку позволяет сократить модульное возведение в степень с большими показателями до показателей, меньших n .
Теорема Эйлера используется с n, не являющимся простым числом, в криптографии с открытым ключом , в частности в криптосистеме RSA , обычно следующим образом: [10] если извлечение x из значений y , e и n легко, если известно φ ( n ) . [11] Фактически, расширенный алгоритм Евклида позволяет вычислить модульное обратное число e по модулю φ ( n ) , то есть целое число f такое, что Из этого следует, что
С другой стороны, если n = pq — произведение двух различных простых чисел, то φ ( n ) = ( p − 1)( q − 1) . В этом случае нахождение f по n и e так же сложно, как вычисление φ ( n ) (это не доказано, но не известен ни один алгоритм для вычисления f без знания φ ( n ) ). Зная только n , вычисление φ ( n ) по сути имеет ту же сложность, что и факторизация n , поскольку φ ( n ) = ( p − 1)( q − 1) , и наоборот, множители p и q являются (целыми) решениями уравнения x 2 – ( n − φ ( n ) + 1) x + n = 0 .
Основная идея криптосистемы RSA заключается в следующем: если сообщение x зашифровано как y = x e (mod n ) с использованием общедоступных значений n и e , то, имея текущие знания, его невозможно расшифровать, не найдя (секретные) множители p и q числа n .
Малая теорема Ферма также связана с функцией Кармайкла и теоремой Кармайкла , а также с теоремой Лагранжа в теории групп .
Обратное утверждение малой теоремы Ферма неверно для чисел Кармайкла . Однако, немного более слабым вариантом обратного утверждения является теорема Лемера :
Если существует целое число a такое, что и для всех простых чисел q, делящих p − 1, то p является простым числом.
Эта теорема лежит в основе теста простоты Лукаса , важного теста простоты , и сертификата простоты Пратта .
Если a и p — взаимно простые числа, такие, что a p −1 − 1 делится на p , то p не обязательно должно быть простым. Если это не так, то p называется псевдопростым числом (Ферма) по основанию a . Первое псевдопростое число по основанию 2 было найдено в 1820 году Пьером Фредериком Саррюсом : 341 = 11 × 31. [12] [13]
Число p, которое является псевдопростым числом Ферма по основанию a для каждого числа a, взаимно простого с p, называется числом Кармайкла . С другой стороны, любое число p, удовлетворяющее равенству, является либо простым числом, либо числом Кармайкла.
Тест на простоту Миллера-Рабина использует следующее расширение малой теоремы Ферма: [14]
Если p — нечетное простое число и p − 1 = 2 s d , где s > 0 , а d нечетное > 0, то для любого числа a , взаимно простого с p , либо a d ≡ 1 (mod p ) , либо существует r такое, что 0 ≤ r < s и a 2 r d ≡ −1 (mod p ) .
Этот результат можно вывести из малой теоремы Ферма с помощью того факта, что если p — нечетное простое число, то целые числа по модулю p образуют конечное поле , в котором 1 по модулю p имеет ровно два квадратных корня: 1 и −1 по модулю p .
Обратите внимание, что a d ≡ 1 (mod p ) выполняется тривиально для a ≡ 1 (mod p ) , поскольку отношение конгруэнтности совместимо с возведением в степень . И a d = a 2 0 d ≡ −1 (mod p ) выполняется тривиально для a ≡ −1 (mod p ), поскольку d нечетно, по той же причине. Вот почему обычно выбирают случайное a в интервале 1 < a < p − 1 .
Тест Миллера–Рабина использует это свойство следующим образом: дано нечетное целое число p, для которого необходимо проверить простоту, записать p − 1 = 2 s d, где s > 0 и d нечетное > 0, и выбрать случайное a такое, что 1 < a < p − 1 ; затем вычислить b = a d mod p ; если b не равно 1 и не равно −1, то возвести его в квадрат по модулю p несколько раз , пока не получите −1 или не возведете s − 1 раз. Если b ≠ 1 и −1 не было получено возведением в квадрат, то p является составным числом , а a является свидетелем составности p . В противном случае p является сильным вероятным простым числом по основанию a ; то есть оно может быть простым или нет. Если p является составным числом, вероятность того, что тест в любом случае объявит его сильным вероятным простым числом, не превышает 1 ⁄ 4 , в этом случае p является сильным псевдопростым числом , а a является сильным лжецом . Таким образом, после k неокончательных случайных тестов вероятность того, что p является составным числом, не превышает 4 − k , и, таким образом, может быть сделана сколь угодно низкой путем увеличения k .
Вкратце, тест либо доказывает, что число является составным, либо утверждает, что оно является простым с вероятностью ошибки, которая может быть выбрана сколь угодно низкой. Тест очень прост в реализации и вычислительно более эффективен, чем все известные детерминированные тесты. Поэтому его обычно используют перед началом доказательства простоты.