Малая теорема Ферма

Простое число p делит a^p–a для любого целого числа a

В теории чисел малая теорема Ферма утверждает, что если p — простое число , то для любого целого числа a число a ^p − a является целым кратным p . В обозначениях модульной арифметики это выражается как $${\displaystyle a^{p}\equiv a{\pmod {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]} $${\displaystyle a^{p-1}\equiv 1{\pmod {p}}.}$$

Например, если 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 вопросом. ${\displaystyle -1}$ ${\displaystyle -1}$

Это можно перевести, добавив в скобках пояснения и формулы для облегчения понимания, как:

Каждое простое число [ 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 ³⁴¹ ≡ 2 (mod 341) , но 341 = 11 × 31 является псевдопростым числом по основанию 2. См. ниже.

Доказательства

Известно несколько доказательств малой теоремы Ферма. Часто ее доказывают как следствие теоремы Эйлера .

Обобщения

Теорема Эйлера является обобщением малой теоремы Ферма: для любого модуля n и любого целого числа a, взаимно простого с n , имеем

$${\displaystyle a^{\varphi (n)}\equiv 1{\pmod {n}},}$$

где φ ( n ) обозначает функцию Эйлера (которая подсчитывает целые числа от 1 до n , которые взаимно просты с n ). Малая теорема Ферма действительно является особым случаем, потому что если n — простое число, то φ ( n ) = n − 1 .

Следствием теоремы Эйлера является: Для каждого положительного целого числа n , если целое число a взаимно просто с n , то для любых целых чисел x и y . Это следует из теоремы Эйлера, поскольку, если , то x = y + kφ ( n ) для некоторого целого числа k , и имеем $${\displaystyle x\equiv y{\pmod {\varphi (n)}}\quad {\text{implies}}\quad a^{x}\equiv a^{y}{\pmod {n}},}$$ ${\displaystyle x\equiv y{\pmod {\varphi (n)}}}$ $${\displaystyle a^{x}=a^{y+\varphi (n)k}=a^{y}(a^{\varphi (n)})^{k}\equiv a^{y}1^{k}\equiv a^{y}{\pmod {n}}.}$$

Если n — простое число, это также является следствием малой теоремы Ферма. Это широко используется в модульной арифметике , поскольку позволяет сократить модульное возведение в степень с большими показателями до показателей, меньших n .

Теорема Эйлера используется с n, не являющимся простым числом, в криптографии с открытым ключом , в частности в криптосистеме RSA , обычно следующим образом: ^[10] если извлечение x из значений y , e и n легко, если известно φ ( n ) . ^[11] Фактически, расширенный алгоритм Евклида позволяет вычислить модульное обратное число e по модулю φ ( n ) , то есть целое число f такое, что Из этого следует, что $${\displaystyle y=x^{e}{\pmod {n}},}$$ $${\displaystyle ef\equiv 1{\pmod {\varphi (n)}}.}$$ $${\displaystyle x\equiv x^{ef}\equiv (x^{e})^{f}\equiv y^{f}{\pmod {n}}.}$$

С другой стороны, если n = pq — произведение двух различных простых чисел, то φ ( n ) = ( p − 1)( q − 1) . В этом случае нахождение f по n и e так же сложно, как вычисление φ ( n ) (это не доказано, но не известен ни один алгоритм для вычисления f без знания φ ( n ) ). Зная только n , вычисление φ ( n ) по сути имеет ту же сложность, что и факторизация n , поскольку φ ( n ) = ( p − 1)( q − 1) , и наоборот, множители p и q являются (целыми) решениями уравнения x ² – ( n − φ ( n ) + 1) x + n = 0 .

Основная идея криптосистемы RSA заключается в следующем: если сообщение x зашифровано как y = x ^e (mod n ) с использованием общедоступных значений n и e , то, имея текущие знания, его невозможно расшифровать, не найдя (секретные) множители p и q числа n .

Малая теорема Ферма также связана с функцией Кармайкла и теоремой Кармайкла , а также с теоремой Лагранжа в теории групп .

Конверс

Обратное утверждение малой теоремы Ферма неверно для чисел Кармайкла . Однако, немного более слабым вариантом обратного утверждения является теорема Лемера :

Если существует целое число a такое, что и для всех простых чисел q, делящих p − 1, то p является простым числом. $${\displaystyle a^{p-1}\equiv 1{\pmod {p}}}$$ $${\displaystyle a^{(p-1)/q}\not \equiv 1{\pmod {p}},}$$

Эта теорема лежит в основе теста простоты Лукаса , важного теста простоты , и сертификата простоты Пратта .

Псевдопростые числа

Если a и p — взаимно простые числа, такие, что a ^{p −1} − 1 делится на p , то p не обязательно должно быть простым. Если это не так, то p называется псевдопростым числом (Ферма) по основанию a . Первое псевдопростое число по основанию 2 было найдено в 1820 году Пьером Фредериком Саррюсом : 341 = 11 × 31. ^{[12] [13]}

Число p, которое является псевдопростым числом Ферма по основанию a для каждого числа a, взаимно простого с p, называется числом Кармайкла . С другой стороны, любое число p, удовлетворяющее равенству, является либо простым числом, либо числом Кармайкла. $${\displaystyle \gcd \left(p,\sum _{a=1}^{p-1}a^{p-1}\right)=1}$$

Тест Миллера-Рабина на простоту

Тест на простоту Миллера-Рабина использует следующее расширение малой теоремы Ферма: ^[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 .

Вкратце, тест либо доказывает, что число является составным, либо утверждает, что оно является простым с вероятностью ошибки, которая может быть выбрана сколь угодно низкой. Тест очень прост в реализации и вычислительно более эффективен, чем все известные детерминированные тесты. Поэтому его обычно используют перед началом доказательства простоты.

Смотрите также

• частное Ферма
• Эндоморфизм Фробениуса
• p -вывод
• Дроби с простыми знаменателями : числа с поведением, соответствующим малой теореме Ферма
• ЮАР
• Таблица сравнений
• Модульная мультипликативная обратная

Примечания

1. Лонг 1972, стр. 87–88.
2. Петтофреццо и Биркит 1970, стр. 110–111.
3. Burton 2011, стр. 514.
4. Ферма, Пьер (1894), Таннери, П.; Генри, К. (ред.), Oeuvres de Fermat. Том 2: Переписка, Париж: Готье-Виллар, стр. 206–212.(на французском)
5. Mahoney 1994, стр. 295 для английского перевода.
6. Эйлер, Леонард (1736). «Theorematum quorundam ad numeros primos spectantium demostratio» [Доказательство некоторых теорем, касающихся простых чисел]. Commentarii Academiae Scientiarum Imperialis Petropolitanae (Воспоминания об Императорской Академии наук в Петербурге) (на латыни). 8 : 141–146.
7. Оре 1988, стр. 273
8. Хензель, Курт (1913). Zahlentheorie [ Теория чисел ] (на немецком языке). Берлин и Лейпциг, Германия: Г. Дж. Гёшен. п. 103.
9. Альберт 2015, стр. 206
10. Трапп, Уэйд; Вашингтон, Лоуренс К. (2002), Введение в криптографию с теорией кодирования , Prentice-Hall, стр. 78, ISBN 978-0-13-061814-6
11. Если y не является взаимно простым с n , теорема Эйлера не работает, но этот случай достаточно редок, чтобы его не рассматривать. Фактически, если бы это произошло случайно, это обеспечило бы простую факторизацию n , и таким образом нарушило бы рассматриваемый случай RSA.
12. Слоан, Н. Дж. А. (ред.). "Последовательность A128311 (Остаток от деления 2n−1−1 на n.)". Онлайновая энциклопедия целочисленных последовательностей . Фонд OEIS.
13. Саррус, Фредерик (1819–1820). «Демонстрация ложности теоремы, изложенной на странице 320 9-го тома этого сборника». Annales de Mathématiques Pures et Appliquées (на французском языке). 10 : 184–187.
14. Rempe-Gillen, Lasse; Waldecker, Rebecca (2013-12-11). "4.5.1. Лемма (Корни из единицы по модулю простого числа)". Тестирование простоты для начинающих . Американское математическое общество. ISBN 9780821898833.

Ссылки

• Альберт, А. Адриан (2015) [1938], Современная высшая алгебра, Cambridge University Press , ISBN 978-1-107-54462-8
• Бертон, Дэвид М. (2011), История математики / Введение (7-е изд.), McGraw-Hill, ISBN 978-0-07-338315-6
• Лонг, Кэлвин Т. (1972), Элементарное введение в теорию чисел (2-е изд.), Лексингтон: DC Heath and Company , LCCN  77171950
• Махони, Майкл Шон (1994), Математическая карьера Пьера де Ферма, 1601–1665 (2-е изд.), Princeton University Press, ISBN 978-0-691-03666-3
• Оре, Эйстейн (1988) [1948], Теория чисел и ее история , Довер, ISBN 978-0-486-65620-5
• Петтофреццо, Энтони Дж.; Биркит, Дональд Р. (1970), Элементы теории чисел , Englewood Cliffs: Prentice Hall , LCCN  71081766

Дальнейшее чтение

• Пауло Рибенбойм (1995). Новая книга записей простых чисел (3-е изд.). Нью-Йорк: Springer-Verlag. ISBN 0-387-94457-5 . С. 22–25, 49. 

Внешние ссылки

• Медиа, связанные с малой теоремой Ферма на Wikimedia Commons
• Янош Бойяи и псевдопростые числа (на венгерском языке)
• Малая теорема Ферма в Cut-the-Knot
• Функция и теорема Эйлера в Cut-the-Knot
• Малая теорема Ферма и доказательство Софи
• «Малая теорема Ферма», Энциклопедия математики , EMS Press , 2001 [1994]
• Вайсштейн, Эрик В. «Малая теорема Ферма». MathWorld .
• Вайсштейн, Эрик В. «Обратная малая теорема Ферма». MathWorld .