Маленькая теорема Ферма

Маленькая теорема Ферма утверждает, что если p - простое число , то для любого целого a число a ^p - a является целым кратным p . В обозначениях модульной арифметики это выражается как

${\ displaystyle a ^ {p} \ Equiv a {\ pmod {p}}.}$

Например, если a = 2 и p = 7, то 2 ⁷ = 128, а 128 - 2 = 126 = 7 × 18 является целым числом, кратным 7.

Если a не делится на p , малая теорема Ферма эквивалентна утверждению, что a ^{p - 1} - 1 является целым кратным p , или в символах: ^{[1] [2]}

${\ displaystyle a ^ {p-1} \ Equiv 1 {\ pmod {p}}.}$

Например, если a = 2 и p = 7, то 2 ⁶ = 64 и 64 - 1 = 63 = 7 × 9, таким образом, делится на 7.

Маленькая теорема Ферма лежит в основе критерия простоты Ферма и является одним из фундаментальных результатов элементарной теории чисел . Теорема названа в честь Пьера де Ферма , который сформулировал ее в 1640 году. Ее называют «маленькой теоремой», чтобы отличить ее от последней теоремы Ферма . ^[3]

Пьер де Ферма

Пьер де Ферма впервые изложил теорему в письме от 18 октября 1640 года своему другу и доверенному лицу Френкле де Бесси . Его формулировка эквивалентна следующему: ^[3]

Если р является простым и любое целое число не делится на р , то в ^{р - 1} - 1 делится на р .

Первоначальное заявление Ферма было

Tout nombre premier mesure infailliblement une des puissances ${\ displaystyle -1}$ de quelque progression que ce soit, et l'exposant de la dite puissance est sous-multiple du nombre premier donné ${\ displaystyle -1}$; et, après qu'on a try la première puissance quiisfait a la question, toutes celles dont les exposants sont multiple de l'exposant de la première удовлетворит все мысли о вопросе.

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

Каждое простое число [ p ] обязательно делит одну из степеней за вычетом одной любой [геометрической] прогрессии [ a , a ² , a ³ , ... ] [то есть существует t такое, что p делит a ^t - 1 ], и показатель этой степени [ t ] делит данное простое число минус один [делит p - 1 ]. После того, как кто-то нашел первую степень [ t ], которая удовлетворяет вопросу, все те, чьи показатели кратны показателю первой степени, аналогичным образом удовлетворяют вопросу [то есть, все кратные первой степени t обладают одинаковым свойством].

Ферма не рассматривал случай, когда a делится на p, и не доказывал свое утверждение, а только констатировал: ^[4]

Et cette proposition est généralement vraie en toutes progressions et en tous nombres premiers; de quoi je vous envoierois la démonstration, si je n'appréhendois d'être trop long.

(И это утверждение обычно верно для всех серий [ sic ] и всех простых чисел; я бы послал вам его демонстрацию, если бы я не боялся, что это будет продолжаться слишком долго.) ^[5]

Эйлер представил первое опубликованное доказательство в 1736 году в статье под названием «Теоретум Quorundam ad Numeros Primos Spectantium Demonstratio» в Трудах Санкт-Петербургской академии ^[6], но Лейбниц дал практически такое же доказательство в неопубликованной рукописи, написанной ранее. 1683. ^[3]

Термин «малая теорема Ферма», вероятно , был впервые использован в печати в 1913 году в Zahlentheorie по Курт Hensel :

Für jede endliche Gruppe besteht nun ein Fundamentalsatz, welcher der kleine Fermatsche Satz genannt zu werden pflegt, weil ein ganz spezieller Teil desselben zuerst von Fermat bewiesen worden ist.

(В каждой конечной группе есть фундаментальная теорема, обычно называемая маленькой теоремой Ферма, потому что Ферма был первым, кто доказал очень особую ее часть.)

Одно из первых употреблений на английском языке встречается в « Современной высшей алгебре А.А. Альберта » (1937), где упоминается «так называемая« маленькая »теорема Ферма» на странице 206. ^[7]

Дальнейшая история

Некоторые математики независимо друг от друга выдвинули связанную гипотезу (иногда неправильно называемую китайской гипотезой), что 2 ^p ≡ 2 (mod p ) тогда и только тогда, когда p простое число. Действительно, часть «если» верна, и это частный случай маленькой теоремы Ферма. Однако часть «только если» неверна: например, 2 ³⁴¹ 2 (mod 341) , но 341 = 11 × 31 является псевдопервичным . См. Ниже .

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

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

${\ Displaystyle а ^ {\ varphi (п)} \ эквив 1 {\ pmod {п}},}$

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

Следствие теоремы Эйлера является: для любого натурального числа п , если число является взаимно просто с п , то

${\ Displaystyle х \ экви у {\ pmod {\ varphi (n)}} \ quad {\ text {implies}} \ quad a ^ {x} \ Equiv a ^ {y} {\ pmod {n}},}$

для любых целых чисел x и y . Это следует из теоремы Эйлера, поскольку, если${\ Displaystyle х \ эквив у {\ pmod {\ varphi (п)}}}$, то x = y + kφ ( n ) для некоторого целого k , и

${\ 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 следующим образом: ^[8] if

${\ Displaystyle у = х ^ {е} {\ pmod {п}},}$

получить x из значений e и n легко, если известно φ ( n ) . Фактически, расширенный алгоритм Евклида позволяет вычислить модульное обратное к e по модулю φ ( n ) , то есть целое число f, такое${\ Displaystyle ef \ Equiv 1 {\ pmod {\ varphi (n)}}}$. Следует, что

${\ Displaystyle х \ эквив х ^ {еф} \ эквив (х ^ {е}) ^ {е} \ эквив у ^ {е} {\ 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 .

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

Обратный из малой теоремы Ферма как правило , не верно, так как он не для чисел Кармайкли . Однако верна несколько более сильная форма теоремы, известная как теорема Лемера. Теорема следующая:

Если существует такое целое число a , что

${\ Displaystyle а ^ {р-1} \ эквив 1 {\ pmod {p}}}$

и для всех простых чисел q, делящих p - 1 ,

${\ Displaystyle а ^ {(р-1) / д} \ not \ эквив 1 {\ pmod {р}},}$

тогда p простое число.

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

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

Число р , что является Ферма псевдопростым числом к базовому а для каждого числа взаимно простые с р называется число Кармикаэл (например , 561). Как вариант, любое число p, удовлетворяющее равенству

${\ displaystyle \ gcd \ left (p, \ sum _ {a = 1} ^ {p-1} a ^ {p-1} \ right) = 1}$

является простым числом или числом Кармайкла.

Тест на простоту Миллера – Рабина использует следующее расширение малой теоремы Ферма: ^[11]

Если р нечетное простое число, а р - 1 = 2 ^сек d , с д нечетно, то для каждого простое с р , либо ^д ≡ 1 по модулю р , либо существует т такое , что 0 ≤ т <с и ^{2 t d} ≡ −1 mod p

Этот результат может быть выведен из маленькой теоремы Ферма тем фактом, что если p - нечетное простое число, то целые числа по модулю p образуют конечное поле , в котором 1 имеет ровно два квадратных корня, 1 и −1.

Тест Миллера – Рабина использует это свойство следующим образом: если p = 2 ^s d + 1 , с d нечетным, нечетное целое число, для которого необходимо проверить простоту, выберите случайным образом a такое, что 1 < a < p ; затем вычислить b = a ^d mod p ; если b не равно 1 и не -1, то возвести его в квадрат по модулю p, пока вы не получите 1, -1 или возведете в квадрат s раз. Если b ≠ 1 и −1 не получено, то p не простое число. В противном случае p может быть простым или нет. Если p не является простым числом, вероятность того, что это доказано тестом, выше 1/4. Следовательно, после k неокончательных случайных тестов вероятность того, что p не является простым, меньше, чем (3/4) ^k , и, таким образом, может быть сделана настолько низкой, насколько желательно, путем увеличения k .

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

• Альберт, А. Адриан (2015) [1938], Современная высшая алгебра , Cambridge University Press , ISBN 978-1-107-54462-8
• Бертон, Дэвид М. (2011), История математики / Введение (7-е изд.), McGraw-Hill, ISBN 978-0-07-338315-6
• Лонг, Кальвин Т. (1972), Элементарное введение в теорию чисел (2-е изд.), Лексингтон: Хит энд Компани , округ Колумбия , 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.

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