Малая теорема Ферма

Ма́лая теоре́ма Ферма́ — классическая теорема теории чисел, которая утверждает, что

Если p — простое число, и $a$ не делится на $p$, то $a^{p-1}\equiv 1\pmod p.$ Другими словами, $~a^{p-1}$ при делении нацело на $p$ даёт в остатке 1.

Равносильная формулировка:

Для любого простого $p$ и целого $a$: $(a^p-a)$ делится на $p.$

Теорема называется малой во избежание путаницы с Великой теоремой Ферма.

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

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

Докажем, что для любого простого p и целого неотрицательного a, $a^p-a$ делится на p. Доказываем индукцией по a.

База. Для a=0, $a^p-a = 0$ и делится на p.

Переход. Пусть утверждение верно для a=k. Докажем его для a=k+1.

$a^p-a = (k+1)^p-(k+1) = k^p+1+\sum_{l=1}^{p-1} {p \choose l} k^l - k-1 = k^p - k + \sum_{l=1}^{p-1}k^l {p \choose l}$

Но $k^p-k$ делится на p по предположению индукции. Что же касается остальных слагаемых, то ${p \choose l} = {p! \over l!(p-l)!}$. Для $1 \le l \le p-1$, числитель этой дроби делится на p, а знаменатель — взаимно прост с p, следовательно, ${p \choose l}$ делится на $p$. Таким образом, вся сумма $k^p - k + \sum_{l=1}^{p-1}k^l {p \choose l}$ делится на p.

Для отрицательных a и нечётных p теорему легко доказать подстановкой b=-a. Для отрицательных a и p=2 истинность теоремы следует из $a^2-a=a(a-1)$■

Свойства и некоторые следствия

• Если $p$ — простое число, а $m$ и $n$ — такие положительные целые числа, что $~m\equiv n\pmod{p-1}$, тогда $a^m\equiv a^n\pmod{p} \quad\forall a\in\mathbb{Z}$. Это утверждение используется в системе шифрования с открытым ключом RSA.

• Если $p$ — простое число, отличное от 2 и 5, то число $10^{p-1} - 1$, запись которого состоит из одних девяток, делится на $p$. Отсюда легко следует, что для любого целого числа $N$, которое не делится на 2 и на 5, можно подобрать число, состоящее только из девяток, которое делится на $N$ ^[1]. Этот факт используется в теории признаков делимости и периодических дробей.

Обобщения

Малая теорема Ферма является частным случаем теоремы Эйлера, которая, в свою очередь, является частным случаем теорем Кармайкла и Лагранжа для конечных циклических групп.

Малая теорема Ферма также имеет изящное обобщение в теории конечных полей.

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

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

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

Пример: Ф. Саррус в 1820 году нашёл, что число $~N = 2^{341-1} - 1$ делится на 341 (потому что N делится на $~2^{10}-1=3 \cdot 341$). Но 341 — составное число: $~341 = 11 \cdot 31$ — это первое псевдопростое число по основанию 2.

Число p, являющееся псевдопростым по основанию a для всех a, взаимно простых с p, называется числом Кармайкла (например, 561 — наименьшее из чисел Кармайкла).

Хотя выполнение теоремы Ферма не гарантирует, что p — простое число, теорема может быть полезна для тестирования числа: если $(a^p-a)$ не делится на $p$, то p — составное число.

История

Пьер Ферма сформулировал исходное утверждение теоремы около 1636 года. Письмо от 18 октября 1640 года Пьера Ферма к французскому математику Бернару Френиклю (Bernard Frénicle de Bessy) содержало следующее положение: p делит $a^{p-1}-1$ в случае, когда p является простым числом и a не делится на p. Опубликовано в посмертном издании его трудов (1660).

Ещё в древности китайским математикам была известна гипотеза (иногда называемая «Китайской гипотезой»), что p является простым числом в том и только в том случае, когда $2^p \equiv 2 \pmod{p}$ (фактически, частный случай малой теоремы Ферма)^[2]. Тем не менее, обратное утверждение (о том, что из $2^p \equiv 2 \pmod {p}$ следует, что p простое), а, следовательно, и гипотеза в целом, оказались неверными (см. выше).

Существует также предположение, что китайская гипотеза была выдвинута примерно за 2000 лет до аналогичных работ Ферма. Стоит отметить, что гипотеза могла быть известна и другим математикам древности, даже несмотря на то, что она оказалась частично неверной. Тем не менее, в некоторых источниках^[3] утверждается, что предположение относительно столь раннего появления гипотезы является распространённым заблуждением, а в действительности гипотеза была выдвинута лишь в 1872 году.

Сам Ферма оставил свою теорему без доказательства. Первым, кому удалось его найти, был Готфрид Вильгельм Лейбниц, в рукописях которого утверждается, что доказательство ему было известно до 1683 года. Лейбниц не знал о результате Ферма и открыл теорему независимо^[1]. Но работа Лейбница не была опубликована, и доказательство (очень похожее) в 1736 году обнародовал Эйлер в статье Theorematum Quorundam ad Numeros Primos Spectantium Demonstratio.

Доказательство малой теоремы Ферма, основанное на том, что целые числа $x, 2x, 3x, \dots, (p-1)x$ сравнимы в некотором порядке с числами $1, 2, 3, \dots, p-1$, было опубликовано в 1806 году Джеймсом Айвори.

См. также

• Великая теорема Ферма
• Теорема Эйлера
• Сильное псевдопростое число
• RSA

Литература

• Винберг Э. Б. Малая теорема Ферма и ее обобщения // Математическое просвещение. — 2008. — В. 12. — С. 43–53.
• Гиндикин С. Г. Малая теорема Ферма // Квант. — 1972. — № 10.
• Данциг, Т. Числа - язык науки. — М.: Техносфера, 2008. — С. 111. — ISBN 978-5-94836-172-7

Примечания

1. ↑ ^{1 2} Данциг, Т. Числа - язык науки, 2008, с. 232-234
2. ↑ Honsberger, R. (1973), An Old Chinese Theorem and Pierre de Fermat, Mathematical Gems, I, Washington, DC: Math. Assoc. Amer., pp. 1–9.
3. ↑ Ribenboim, P. (1996), The New Book of Prime Number Records, New York: Springer-Verlag, pp. 103–105, ISBN 0387944575.