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

В теории чисел маленькая теорема Ферма утверждает, что если p $—$ простое число , то для любого целого числа $a$ число $a p - 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 p - 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 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 вопросом. $-1$ $-1$

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

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

Ферма не рассматривал случай, когда $а$ кратно $р$ , и не доказывал свое утверждение, лишь констатируя: ^[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 \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

=

y

+

kφ

(

n

)

k

x\equiv y{\pmod {\varphi (n)}}

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 - (n - φ (n) + 1) x + n = 0$ .

Основная идея криптосистемы RSA заключается в следующем: если сообщение $x$ зашифровано как $y = x e (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 p -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 s d$ с $s > 0$ и $d$ нечетным > 0, то для каждого $a,$ взаимно простого с $p$ , либо $a d \equiv 1 (mod p)$ , либо существует $r$ такой, что $0 ⩽ r < s$ и $а 2 р d \equiv -1 (мод п)$ .

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

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

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

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

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

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

Примечания

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

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

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

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

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