Маленькая теорема Ферма - Fermats little theorem

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

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

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

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

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

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

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

История

Пьер де Ферма

Пьер де Ферма впервые изложил теорему в письме от 18 октября 1640 года своему другу и доверенному лицу. Frénicle de Bessy. Его формулировка эквивалентна следующему:^[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 Trouvé la première puissance quiisfait a la question, toutes celles dont les exposants sont multiple de l'exposant de la première удовлетворит все мысли о вопросе.

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

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

Ферма не рассматривал случай, когда $а$ кратно $п$ ни доказывать свое утверждение, только констатируя:^[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 году в статье под названием «Теорематум кворундам ad Numeros Primos Spectantium Demonstratio» в Труды Санкт-Петербургской Академии,^[6] но Лейбниц дал практически такое же доказательство в неопубликованной рукописи примерно до 1683 года.^[3]

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

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 п \equiv 2 (мод п)$ если и только если $п$ простое. Действительно, часть «если» верна, и это частный случай маленькой теоремы Ферма. Однако часть "только в том случае, если" неверна: например, $2341 \equiv 2 (мод. 341)$ , но 341 = 11 × 31 является псевдопремия. Видеть ниже.

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

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

Обобщения

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

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

куда ${ Displaystyle varphi (п)}$ обозначает Функция Эйлера (который считает целые числа от 1 до $п$ которые взаимно просты с $п$ ). Маленькая теорема Ферма - действительно частный случай, потому что если ${ displaystyle n}$ простое число, то ${ Displaystyle varphi (п) = п-1}$ .

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

{ Displaystyle х Equiv Y { pmod { varphi (n)}} quad { text {implies}} quad a ^ {x} Equiv a ^ {y} { pmod {n}},}

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

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

Если $п$ не является простым, это используется в криптография с открытым ключом, как правило, в Криптосистема RSA следующим образом:^[8] если

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

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

{ Displaystyle х эквив х ^ {еф} эквив (х ^ {е}) ^ {е} эквив у ^ {е} { pmod {n}}.}

С другой стороны, если $п = pq$ является произведением двух различных простых чисел, то ${ displaystyle varphi (n) = (p-1) (q-1).}$ В этом случае нахождение $ж$ из $п$ и $е$ нужно знать ${ Displaystyle varphi (п)}$ (это не доказано, но алгоритм вычисления $ж$ не зная ${ Displaystyle varphi (п)}$ ). Если кто знает $п$ и ${ Displaystyle varphi (п),}$ факторы $п$ и $q$ легко вывести, поскольку каждый знает их продукт $п$ и их сумма ${ displaystyle n- varphi (n) +1.}$ Основная идея криптосистемы RSA такова: если сообщение $Икс$ зашифрован как ${ Displaystyle у = х ^ {е} { pmod {п}},}$ использование общественных ценностей $п$ и $е$ , то при текущих знаниях его нельзя расшифровать, не найдя (секретных) факторов $п$ и $q$ из $п$ .

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

Converse

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

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

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

и для всех простых чисел $q$ разделение $п - 1$ надо

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

тогда $п$ простое.

Эта теорема лежит в основе Тест Лукаса-Лемера, важно тест на простоту.

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

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

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

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

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

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

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

Если $п$ нечетное простое число и $п - 1 = 2 s d$ , с $d$ нечетное, то на каждый $а$ премьер к $п$ , либо $а d \equiv 1 мод п$ , или существует $т$ такой, что $0 \leq т и а 2 т d \equiv -1 мод п$

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

Тест Миллера – Рабина использует это свойство следующим образом: задано $п = 2 s d + 1$ , с $d$ odd, нечетное целое число, для которого необходимо проверить простоту, выбрать случайным образом $а$ такой, что $1 < а < п$ ; затем вычислить $б = а d мод п$ ; если $б$ не равно 1 и не −1, то возведем его в квадрат повторно по модулю $п$ пока вы не получите 1, -1 или возведете в квадрат $s$ раз. Если $б \neq 1$ и −1 не получено, то $п$ не простое. Иначе, $п$ может быть простым или нет. Если $п$ не является простым, вероятность того, что это доказано тестом, выше 1/4. Поэтому после $k$ неокончательные случайные тесты, вероятность того, что $п$ не простое меньше чем $(3/4) k$ , и, таким образом, его можно сделать желаемо низким за счет увеличения $k$ .

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

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

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

Примечания

^ Длинный 1972 С. 87–88.
^ Петтофреццо и Биркит 1970 С. 110–111.
^ ^а ^б ^c Бертон 2011, п. 514.
^ Ферма, Пьер (1894), Кожевенный завод, П .; Генри, К. (ред.), Oeuvres de Fermat. Том 2: Соответствие, Paris: Gauthier-Villars, стр. 206–212. (На французском)
^ Махони 1994, п. 295 за английский перевод
^ Руда 1988, п. 273
^ Альберт 2015, п. 206
^ Трапп, Уэйд; Вашингтон, Лоуренс К. (2002), Введение в криптографию с теорией кодирования, Прентис-Холл, стр. 78, ISBN 978-0-13-061814-6
^ Слоан, Н. Дж. А. (ред.). "Последовательность A128311 (Остаток после деления 2^п−1−1 по п.)". В Он-лайн энциклопедия целочисленных последовательностей. Фонд OEIS.
^ Саррус, Фредерик (1819–1820). "Démonstration de la fausseté du théorème énoncé á la page 320 du IXe volume de ce recueil" [Доказательство ложности теоремы, изложенной на странице 320 9 тома этого сборника]. "Анналы чистой математики и аппликации" (На французском). 10: 184–187.
^ Ремпе-Жиллен, Лассе; Вальдекер, Ребекка (2013-12-11). «4.5.1. Лемма (Корни из единицы по простому модулю)». Тест на первичность для начинающих. American Mathematical Soc. ISBN 9780821898833.

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

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

внешняя ссылка

[1] Длинный 1972 С. 87–88.

[2] Петтофреццо и Биркит 1970 С. 110–111.

[Burton-3] а ^б ^c Бертон 2011, п. 514.

[4] Ферма, Пьер (1894), Кожевенный завод, П .; Генри, К. (ред.), Oeuvres de Fermat. Том 2: Соответствие, Paris: Gauthier-Villars, стр. 206–212. (На французском)

[5] Махони 1994, п. 295 за английский перевод

[6] Руда 1988, п. 273

[7] Альберт 2015, п. 206

[8] Трапп, Уэйд; Вашингтон, Лоуренс К. (2002), Введение в криптографию с теорией кодирования, Прентис-Холл, стр. 78, ISBN 978-0-13-061814-6

[9] Слоан, Н. Дж. А. (ред.). "Последовательность A128311 (Остаток после деления 2^п−1−1 по п.)". В Он-лайн энциклопедия целочисленных последовательностей. Фонд OEIS.

[10] Саррус, Фредерик (1819–1820). "Démonstration de la fausseté du théorème énoncé á la page 320 du IXe volume de ce recueil" [Доказательство ложности теоремы, изложенной на странице 320 9 тома этого сборника]. "Анналы чистой математики и аппликации" (На французском). 10: 184–187.

[11] Ремпе-Жиллен, Лассе; Вальдекер, Ребекка (2013-12-11). «4.5.1. Лемма (Корни из единицы по простому модулю)». Тест на первичность для начинающих. American Mathematical Soc. ISBN 9780821898833.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]