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

редактировать
По поводу других теорем, названных в честь Пьера де Ферма, см . Теорему Ферма.

Маленькая теорема Ферма утверждает, что если 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.

Если не делится на р, малая теорема Ферма равносильно утверждению, что р - 1 - 1 является целым числом, кратным р, или в символах:

а п - 1 1 ( мод п ) . {\ displaystyle a ^ {p-1} \ Equiv 1 {\ pmod {p}}.}

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

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

СОДЕРЖАНИЕ

  • 1 История
    • 1.1 Дальнейшая история
  • 2 Доказательства
  • 3 Обобщения
  • 4 кеды
  • 5 псевдопричин
  • 6 критерий простоты Миллера – Рабина
  • 7 См. Также
  • 8 Примечания
  • 9 ссылки
  • 10 Дальнейшее чтение
  • 11 Внешние ссылки

История

Пьер де Ферма

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

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

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

Tout nombre premier mesure infailliblement une des peissances de quelque progression que ce soit, et l'exposant de la dite puissance est sous-multiple du nombre premier donné ; 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 удовлетворит все мысли о вопросе. - 1 {\ displaystyle -1} - 1 {\ displaystyle -1}

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

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

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

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 ] и всех простых чисел; я бы послал вам демонстрацию этого, если бы я не боялся, что это будет продолжаться слишком долго.)

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

Термин «малая теорема Ферма», вероятно, был впервые использован в печати в 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.

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

Основная статья: китайская гипотеза

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

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

Основная статья: Доказательства маленькой теоремы Ферма

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

Обобщения

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

а φ ( п ) 1 ( мод п ) , {\ 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. Это следует из теоремы Эйлера, поскольку, если, то x = y + kφ ( n) для некоторого целого k, и Икс у ( мод φ ( п ) ) {\ Displaystyle х \ эквив у {\ pmod {\ varphi (п)}}}

а Икс знак равно а у + φ ( п ) k знак равно а у ( а φ ( п ) ) k а у 1 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 следующим образом: если

у знак равно Икс е ( мод п ) , {\ Displaystyle у = х ^ {е} {\ pmod {п}},}

получить x из значений e и n легко, если известно φ ( n). В самом деле, расширенный алгоритм Евклида позволяет вычисления модульный обратный из е по модулю φ ( п), то есть целое число е такие. Следует, что е ж 1 ( мод φ ( п ) ) {\ 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 2 - ( n - φ ( n) + 1) x + n = 0.

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

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

Converse

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

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

а п - 1 1 ( мод п ) {\ Displaystyle а ^ {р-1} \ эквив 1 {\ pmod {p}}}

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

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

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

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

Псевдопричины

Основная статья: Псевдопремия

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

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

gcd ( п , а знак равно 1 п - 1 а п - 1 ) знак равно 1 {\ displaystyle \ gcd \ left (p, \ sum _ {a = 1} ^ {p-1} a ^ {p-1} \ right) = 1}

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

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

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

Если р является нечетным простым, а р - 1 = 2 с d с d нечетно, то для каждого в расцвете к р, либо в D ≡ 1 по модулю р, либо существует т такое, что 0 ≤ т lt;с и 2т d ≡ −1 mod p.

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

Тест Миллера – Рабина использует это свойство следующим образом: если p = 2 s d + 1, с d нечетным, нечетное целое число, для которого необходимо проверить простоту, выберите случайным образом a такое, что 1 lt; a lt; 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.

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

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

Примечания

использованная литература

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

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

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

Последняя правка сделана 2023-04-16 05:45:13
Содержание доступно по лицензии CC BY-SA 3.0 (если не указано иное).
Обратная связь: support@alphapedia.ru
Соглашение
О проекте