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

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

Например, если $a = 2$ и $p = 7$ , то $27 = 128$ и $128 - 2 = 126 = 7 \times 18$ — целое число, кратное $7$ .

Если $a$ не делится на $p$ , то есть если $a$ взаимно просто с $p$ , то малая теорема Ферма эквивалентна утверждению, что $a п - 1 - 1$ — целое число, кратное $p$ , или в символах: ^{[ 1 ]}^{[ 2 ]} $a^{p-1}\equiv 1{\pmod {p}}.$

Например, если $a = 2$ и $p = 7$ , то $26 = 64$ и $64 - 1 = 63 = 7 \times 9$ кратно $7$ .

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

История

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

Если $p$ — простое число и $a$ — любое целое число, не делящееся на $p$ , то $a п - 1 - 1$ делится на $p$ .

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

Каждое простое число безошибочно измеряет одну из степеней. $-1$ любой прогрессии, а показатель указанной степени является дробным данного простого числа $-1$ ; и после того, как мы нашли первую степень, которая удовлетворяет вопросу, все те, показатели которых кратны показателю первой степени, по-прежнему удовлетворяют вопросу.

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

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

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

И это положение вообще верно во всех прогрессиях и во всех простых числах; демонстрацию которого я бы послал вам, если бы не боялся, что это займет слишком много времени.

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

Эйлер представил первое опубликованное доказательство в 1736 году в статье под названием «Theorematum Quorundam ad Numeros Primos Spectantium Demonstratio» (по-английски: «Демонстрация некоторых теорем, касающихся простых чисел») в Трудах Санкт -Петербургской академии. ^{[ 6 ]}^{[ 7 ]} но Лейбниц привел практически такое же доказательство в неопубликованной рукописи, датированной где-то до 1683 года. ^{[ 3 ]}

Термин «малая теорема Ферма», вероятно, впервые был использован в печати в 1913 году в Zahlentheorie Куртом Хензелем : ^{[ 8 ]}

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

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

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

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

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

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

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

Обобщения

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

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

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

Следствием теоремы Эйлера является: для каждого положительного целого числа $n$ , если целое число $a$ взаимно просто с $n$ , то $x\equiv y{\pmod {\varphi (n)}}\quad {\text{implies}}\quad a^{x}\equiv a^{y}{\pmod {n}},$ для любых целых чисел $x$ и $y$ . Это следует из теоремы Эйлера, поскольку, если $x\equiv y{\pmod {\varphi (n)}}$ , то $x = y + kφ (n)$ для некоторого целого числа $k$ и имеем $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 ]} если $y=x^{e}{\pmod {n}},$ Получить $x$ из значений $y$ , $e$ и $n$ легко, если известно $φ (n)$ . ^{[ 11 ]} Фактически, расширенный алгоритм Евклида позволяет вычислить модульное обратное значение e $по$ модулю $φ (n)$ , то есть целое число $f$ такое, что $ef\equiv 1{\pmod {\varphi (n)}}.$ Отсюда следует, что $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 2 - (п - φ (п) + 1) Икс + п знак равно 0$ .

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

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

Конверсы

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

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

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

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

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

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

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

Критерий простоты Миллера-Рабина использует следующее расширение малой теоремы Ферма: ^{[ 14 ]}

Если $p$ — нечетное простое число и $p - 1 = 2 с d$ с $s > 0$ и $d$ нечетным > 0, то для каждого $a,$ взаимно простого с $p$ , либо $a д \equiv 1 (mod p)$ или существует $r$ такой, что $0 ⩽ r < s$ и $a 2 р д \equiv -1 (мод п)$ .

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

Обратите внимание, $что д \equiv 1 (mod p)$ тривиально выполняется для $a \equiv 1 (mod p)$ , поскольку отношение сравнения совместимо с возведением в степень . И $ д = а 20 д \equiv -1 (mod p)$ тривиально выполняется для $a \equiv -1 (mod p),$ поскольку $d$ нечетно по той же причине. Вот почему обычно выбирают случайное значение $a$ в интервале $1 < a < p - 1$ .

Тест Миллера-Рабина использует это свойство следующим образом: учитывая нечетное целое число $p,$ для которого необходимо проверить простоту, напишите $p - 1 = 2. с d$ с $s > 0$ и $d$ нечетным > 0 и выберите случайное $a$ такое, что $1 < a < p - 1$ ; затем вычислите $b = a д мод р$ ; если $b$ не равно 1 и не -1, то возведите его в квадрат по модулю $p,$ пока не получите -1 или не возведете в квадрат $s - 1$ раз. Если $b \neq 1$ и −1 не получено возведением в квадрат, то $p$ является составным , а $a$ является свидетелем составности $p$ . В противном случае $p$ — сильное вероятное простое число для основания a ; то есть оно может быть простым или нет. Если $p$ составное, вероятность того, что тест все равно объявит его сильным вероятным простым числом, не превышает 1/4 p — , и в этом случае $сильное$ псевдопростое число , а $a$ — сильный лжец . Следовательно, после $k$ неубедительных случайных тестов вероятность того, что $p$ является составным, не превышает 4. ^{- к}, и, таким образом, может быть уменьшено до желаемого путем увеличения $k$ .

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

См. также

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

Примечания

^ Лонг 1972 , стр. 87–88.
^ Петтофреззо и Биркит 1970 , стр. 110–111.
^ Jump up to: ^а ^б ^с Бертон 2011 , с. 514.
^ Ферма, Пьер (1894), Таннери, П.; Генри, К. (ред.), Работы Ферма. Том 2: Переписка , Париж: Готье-Виллар, стр. 206–212 (на французском языке)
^ Махони 1994 , с. 295 за английский перевод
^ Эйлер, Леонард (1736). «Демонстрация некоторых теорем, касающихся простых чисел» [Доказательство некоторых теорем, касающихся простых чисел]. Воспоминания об Императорской Академии наук в Петербурге (на латыни) 8 : 141–146.
^ Часы работы 1988 , с. 273
^ Хензель, Курт (1913). Теория чисел ( на немецком языке). Берлин и Лейпциг, Германия: Г. Дж. Гёшен. п. 103.
^ Альберт 2015 , с. 206
^ Траппе, Уэйд; Вашингтон, Лоуренс К. (2002), Введение в криптографию с теорией кодирования , Прентис-Холл, стр. 78, ISBN 978-0-13-061814-6
^ Если $y$ не является взаимно простым с $n$ , теорема Эйлера не работает, но этот случай достаточно редок, чтобы его не рассматривать. Фактически, если бы это произошло случайно, это обеспечило бы легкую факторизацию $n$ и, таким образом, сломало бы рассматриваемый экземпляр RSA.
^ Слоан, Нью-Джерси (ред.). «Последовательность A128311 (остаток после деления 2 ^{п -1}−1 на n .)" . Интернет -энциклопедия целочисленных последовательностей . Фонд OEIS.
^ Саррус, Фредерик (1819–1820). «Демонстрация ложности теоремы, изложенной на стр. 320 9-го тома этого сборника» . Анналы чистой и прикладной математики (на французском языке). 10 : 184–187.
^ Ремпе-Гиллен, Лассе; Вальдекер, Ребекка (11 декабря 2013 г.). «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), Элементы теории чисел , Энглвуд Клиффс: Прентис Холл , LCCN 71081766

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

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

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

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

[1] Лонг 1972 , стр. 87–88.

[2] Петтофреззо и Биркит 1970 , стр. 110–111.

[Burton-3] Jump up to: ^а ^б ^с Бертон 2011 , с. 514.

[4] Ферма, Пьер (1894), Таннери, П.; Генри, К. (ред.), Работы Ферма. Том 2: Переписка , Париж: Готье-Виллар, стр. 206–212 (на французском языке)

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

[6] Эйлер, Леонард (1736). «Демонстрация некоторых теорем, касающихся простых чисел» [Доказательство некоторых теорем, касающихся простых чисел]. Воспоминания об Императорской Академии наук в Петербурге (на латыни) 8 : 141–146.

[7] Часы работы 1988 , с. 273

[8] Хензель, Курт (1913). Теория чисел ( на немецком языке). Берлин и Лейпциг, Германия: Г. Дж. Гёшен. п. 103.

[9] Альберт 2015 , с. 206

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

[11] Если $y$ не является взаимно простым с $n$ , теорема Эйлера не работает, но этот случай достаточно редок, чтобы его не рассматривать. Фактически, если бы это произошло случайно, это обеспечило бы легкую факторизацию $n$ и, таким образом, сломало бы рассматриваемый экземпляр RSA.

[12] Слоан, Нью-Джерси (ред.). «Последовательность A128311 (остаток после деления 2 ^{п -1}−1 на n .)" . Интернет -энциклопедия целочисленных последовательностей . Фонд OEIS.

[13] Саррус, Фредерик (1819–1820). «Демонстрация ложности теоремы, изложенной на стр. 320 9-го тома этого сборника» . Анналы чистой и прикладной математики (на французском языке). 10 : 184–187.

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

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

[ 8 ]

[ 9 ]

[ 10 ]

[ 11 ]

[ 12 ]

[ 13 ]

[ 14 ]