Ма́лая теоре́ма Ферма́ — теорема теории чисел, которая утверждает, что[1]:
|
На языке теории сравнений: сравнимо с 1 по простому модулю . Формальная запись:
К примеру, если то и
Малая теорема Ферма является частным случаем теоремы Эйлера[2], которая, в свою очередь, является частным случаем теоремы Кармайкла и теоремы Лагранжа для групп для конечных циклических групп. Теорему высказал без доказательства Пьер Ферма, первое доказательство дали Леонард Эйлер и Готфрид Вильгельм Лейбниц.
Малая теорема Ферма стала одной из главных теорем для исследований не только в теории целых чисел, но и в более широких областях[3][4].
Пьер Ферма сформулировал исходное утверждение теоремы к 1640 году. «Меня озарило ярким светом», — писал Ферма, впервые сообщая об этом своём открытии в письме (1640)[5]. Интересно, что данная фраза — «mi par di veder un gran lume»[6] написана по-итальянски, хотя всё письмо на французском языке.
Письмо от 18 октября 1640 года Пьера Ферма к французскому математику Бернару Френиклю[fr] содержало следующее положение[7]:
Каждое простое число делит [в оригинале — «измеряет»] одну из степеней любой прогрессии минус 1, для которой показатель степени является делителем данного простого числа минус 1; и после того, как была найдена первая степень, удовлетворяющая этому свойству, все числа, имеющие показатели степени, кратные показателю первой, удовлетворяют тому же свойству.
Оригинальный текст (фр.)Tout nombre premier mesure infailliblement une des puissances −1 de quelque progression que ce soit, et l’exposant de la dite puissance est sous-multiple du nombre premier donné −1; et, après qu’on a trouvé la première puissance qui satisfait à la question, toutes celles dont les exposants sont multiples de l’exposant de la première satisfont tout de même à la question.
В качестве примера Ферма приводит прогрессию 3, 9, 27, 81, 243, 729… и простое число 13. 13 делит 27 − 1 (показатель степени для 27 равен 3, а 3 делит 13 − 1), из чего следует, что 13 также делит 729 − 1 (показатель степени для 729 равен 6 и кратен 3).
Сам Ферма оставил свою теорему без доказательства. Первым математиком, нашедшим доказательство, был Готфрид Вильгельм Лейбниц, из рукописей которого следует, что доказательство ему было известно до 1683 года. Лейбниц не знал о результате Ферма и открыл теорему независимо[8]. Однако работа Лейбница не была опубликована, и доказательство в 1736 году обнародовал Эйлер в статье Theorematum Quorundam ad Numeros Primos Spectantium Demonstratio[9]. Доказательство малой теоремы Ферма, основанное на том, что если пробегает полную систему вычетов по модулю , то для любого произведение также пробегает полную систему вычетов по модулю , было опубликовано в 1806 году Джеймсом Айвори[10].
Число называется частным Ферма. Русский математик Д. А. Граве предположил, что частное Ферма никогда не делится на Для простых чисел, не превышающих 1000, это действительно так, однако вскоре был обнаружен контрпример: для частное Ферма делится на 1093[11].
Следующая формулировка отличается отсутствием требования, чтобы число не делилось на :
|
К примеру, если , то и .
Легко показать что эта формулировка сводится к изначальной. Так, если делится на , то и , т.е. . Если же не делится на , то выражение эквивалентно выражению [2].
Рассмотрим однородный многочлен степени p с n переменными:
Раскрывая скобки, получим коэффициент при одночлене (где хотя бы две из степеней не равны нулю, а сумма всех степеней равна p) называется мультиномиальным коэффициентом и вычисляется по формуле
Поскольку степени меньше, чем то знаменатель мультиномиального коэффициента не содержит множителей, которые могли бы сократиться с следовательно, все коэффициенты многочлена кратны Таким образом, верно следующее тождество:
где — многочлен с положительными целыми коэффициентами.
Пусть теперь в этом тождестве тогда (здесь n — число переменных в исходном полиномиальном выражении), следовательно, кратно . Если не делится на простое число то на него делится [12].
Докажем, что для любого простого p и целого неотрицательного a, ap − a делится на p. Доказываем индукцией по a.
База. Для a = 0, ap − a = 0 и делится на p.
Переход. Пусть утверждение верно для a = k. Докажем его для a = k + 1.
Но kp − k делится на p по предположению индукции. В остальных слагаемых присутствует множитель . Для , числитель этой дроби делится на p, а знаменатель — взаимно прост с p, следовательно, делится на p. Так как все отдельные слагаемые делятся на p, вся сумма также делится на p.
Для отрицательных a и нечётных p теорему легко доказать подстановкой b = −a. Для отрицательных a и p = 2 истинность теоремы следует из a2 − a = a(a − 1)[13].
Одно из самых простых доказательств Малой теоремы Ферма основано на следствии теоремы Лагранжа из теории групп, утверждающей, что порядок элемента конечной группы делит порядок группы.
Напомним, что порядком конечной группы называется число её элементов, а порядком элемента — наименьший показатель его степени, равной единичному элементу группы .
Пусть — конечная группа порядка . Из того, что порядок элемента делит , следует, что .
Рассмотрим поле вычетов по модулю . Вычет целого числа будем обозначать через . Ненулевые элементы поля образуют группу относительно умножения.
Порядок этой группы, очевидно, равен . Её единичным элементом является . Отсюда следует, что для каждого числа , не делящегося на , , но это как раз означает сравнение [1]
Лемма. Для любого простого числа и целого числа , не кратного , произведения и чисел при делении по модулю на в остатке дают те же самые числа возможно, записанные в некотором другом порядке.
Произведение и любого из чисел не кратно , следовательно, в остатке не может получиться . Все остатки разные. Докажем последнее утверждение от противного. Пусть два произведения и дают при делении на одинаковые остатки, тогда разность кратна , что невозможно, поскольку не кратно . Всего существует различных ненулевых остатков от деления на .
Поскольку согласно вышеприведенной лемме остатки от деления чисел a, 2a, 3a, ..., (p − 1)a — это с точностью до перестановки числа 1, 2, 3, ..., p − 1, то . Отсюда . Последнее соотношение можно сократить на (p − 1)!, поскольку все сомножители являются числами, взаимно простыми с основанием p, в результате получаем требуемое утверждение [14].
Теорема Лагранжа в теории чисел[en] утверждает, что если многочлен степени делится на простое число при более чем неконгруэнтных по модолю (т.е. имеющих разные остатки при делении на ) значениях переменной , то он делится на при любом значении .
Рассмотрим многочлен
Тогда мы находим:
В силу малой теоремы Ферма все эти числа делятся на простое число , поэтому сравнение имеет неконгруэнтных решений. С другой стороны, степень многочлена равна всего лишь отсюда следует, что многочлен делится на при всех значениях и в частности при
Значит
А если в дополнение к этому доказать, что для всех непростых натуральных , кроме , , то получим доказательство теоремы.[19]
Малая теорема Ферма может быть использована для тестирования числа на простоту: если не делится на , то p — составное число. Однако обращение малой теоремы Ферма в общем случае неверно: если и — взаимно простые числа и делится на p, то число может быть как простым, так и составным. В случае, когда является составным, оно называется псевдопростым Ферма по основанию a.
К примеру, китайская гипотеза утверждает, что является простым числом тогда и только тогда, когда [20]. Здесь прямое утверждение о том, что если простое, то , является частным случаем малой теоремы Ферма. Обратное же утверждение о том, что если , то простое, есть частный случай обращения малой теоремы Ферма. Это обращение ложно: Саррус в 1820 году нашёл, что число делится на , так как делится на . Однако — составное число: . Таким образом, 341 — псевдопростое число по основанию 2[21].
В общем случае обращение малой теоремы Ферма также не выполняется. Контрпримером в общем случае являются числа Кармайкла: это числа p, являющиеся псевдопростыми по основанию a для всех a, взаимно простых с p. Наименьшим из чисел Кармайкла является 561.
Ввиду того, что обращение малой теоремы Ферма неверно, выполнение её условия не гарантирует что p — простое число. Тем не менее, малая теорема Ферма лежит в основе теста Ферма на простоту[22]. Тест Ферма является вероятностным тестом на простоту: если теорема не выполняется, то число точно составное, а если выполняется — то число простое с некоторой вероятностью. Среди других вероятностных методов можно отметить: тест Соловея — Штрассена и тест Миллера — Рабина, последний в некоторой степени опирается на малую теорему Ферма[23]. Также существует и детерминированный алгоритм: Тест Агравала — Каяла — Саксены.
Кроме того, справедливы следующие два утверждения. Если пара (2, n) удовлетворяют сравнению , то и пара чисел также ему удовлетворяют. Для любого простого числа n и любого a > 2 такого, что , значение является псевдопростым числом Ферма по основанию a[24].
Малая теорема Ферма также используется при доказательстве корректности алгоритма шифрования RSA[2].
Эта статья входит в число добротных статей русскоязычного раздела Википедии. |
Данная страница на сайте WikiSort.ru содержит текст со страницы сайта "Википедия".
Если Вы хотите её отредактировать, то можете сделать это на странице редактирования в Википедии.
Если сделанные Вами правки не будут кем-нибудь удалены, то через несколько дней они появятся на сайте WikiSort.ru .