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

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

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

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

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

Эту теорему называют малой в отличие от большой теоремы Ферма о невозможности решения в целых положительных числах уравнения $x^n+y^n=z^n$ при целом n>2. Малая теорема Ферма уже давно стала одной из главных теорем для исследований не только в теории целых чисел, но и в более широких областях арифметики и алгебры.

История

Пьер Ферма сформулировал исходное утверждение теоремы около 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^p \equiv 2 \pmod {p}$ следует, что p простое), а, следовательно, и гипотеза в целом, оказались неверными (см. ниже).

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

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

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

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

Из множества доказательств этой теоремы опишем два, разного уровня.

Первое доказательство  

Докажем, что для любого простого 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)$■

Второе доказательство  

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

Напомним, что порядком конечной группы $G$ называется число ее элементов, а порядком элемента $g$∈$G$ - наименьший показатель его степени, равной единичному элементу$e$ группы $G$.

Пусть $G$ - конечная группа порядка $n$. Из того, что порядок элемента $g$∈$G$ делит $n$, из этого следует, что $g^n$=$e$.

Рассмотрим поле $Z_p$ вычетов по модулю $p$. Вычет целого числа $a$ будем обозначать через $a$. Ненулевые элементы поля $Z_p$ образуют группу относительно умножения.

Порядок этой группы, очевидно, равен $p-1$. Её единичным элементом является $1'$. Отсюда следует,что для каждого числа $a$, не делящегося на $p$, $a'^{p-1}$=$1'$, но это как раз означает сравнение $a^{p-1}=1$ $(mod p)$

Леммы

Лемма 1. Для любого простого числа p и целого числа k, не кратного p, произведения k и чисел 1, 2, 3, ..., p-1 при делении на p дают те же самые числа 1, 2, 3, ..., p-1, возможно, записанные в некотором другом порядке.

Доказательство. Произведение чисел не кратно p, следовательно, в остатке не может получиться 0. Все остатки разные. Докажем последнее утверждение от противного. Пусть два произведения ak и bk дают при делении на p одинаковые остатки, тогда разность ak-bk=(a-b)k кратна p, что невозможно, поскольку a-b не кратно p. Всего существует p-1 различных ненулевых остатков от деления на p.

Докажем малую теорему Ферма в другой формулировке.

Теорема. Если целое число k не кратно простому числу p, то k^{p-1} даёт остаток 1 при делении на p.

Доказательство. Поскольку согласно Лемме 1 остатки от деления чисел k, 2k, 3k, ..., (p-1)k - это с точностью до перестановки числа 1, 2, 3, ..., p-1, то $k\cdot 2k\cdot 3k\ldots(p-1)k\equiv1\cdot2\cdot3\ldots(p-1) (mod\ p)$. Отсюда $k^{p-1}(p-1)!\equiv(p-1)! (mod\ p)$. Последнее соотношение можно сократить на (p-1)!, поскольку все сомножители являются числами, взаимно простыми с основанием p, в результате получаем требуемое утверждение $k^{p-1}\equiv1 (mod\ p)$.

Обобщение теоремы Ферма на случай составного числа n носит название теоремы Эйлера. Если k - целое число, взаимно простое с натуральным числом n, то $k^r-1$ кратно n, где r - количество взаимно простых с n натуральных чисел, не превосходящих n.

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

Определение. Наименьшее натуральное число k, для которого $a^k\equiv1 (mod\ p)$, называется порядком (не кратного p) числа a по модулю p.

Малая теорема Ферма с помощью термина порядок формулируется следующим образом. Порядок k не кратного простому p целого числа a является делителем числа p-1.

Следствия из теоремы позволяют найти простые делители чисел вида $a^4+a^3+a^2+a+1$ и $a^{2^n}+1$.

Малая теорема Ферма для алгебраических чисел

Теорема (T.Schonemann, 1839)(теорема является обощением малой теоремы Ферма на алгебраические числа. Пусть $a_1$,...,$a_d$ - корни нормированного многочлена f ∈ Z[x]

степени d и p - простое число. Тогда

$a_2^3$+...$a_d^p$= $a_1$+...$a_d$ (mod p)

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

• Если $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$ . Этот факт используется в теории признаков делимости и периодических дробей.

Обобщения

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

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

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

Обращение малой теоремы Ферма неверно, то есть приведенные в определении формулы могут выполняться не только для простых чисел: если $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 — составное число.

Вообще, справедливы следующие два утверждения. Если пара (2, n) удовлетворяют сравнению $a^{n-1}\equiv1\pmod{n}$, то и пара чисел ($2$, $2^{n}-1$) также ему удовлетворяют. Для любого простого числа n и любого a > 2 такого, что $(a^{2}-1, n)=1$, число $\frac{a^{2n}-1}{a^{2}-1}$ является псевдопростым Ферма по основанию a.

См. также

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

Литература

• Винберг Э.Б "Малая теорема Ферма и ее обобщения". — М.: Математическое просвещение, 2008. — В. 12. — С. 43-53.

• Гиндикин С. Г. "Малая теорема Ферма". — Квант, 1972. — № 10.
• Данциг, Т. Числа - язык науки. — М.: Техносфера, 2008. — ISBN 978-5-94836-172-7.
• Александров П.C., Маркуневич А.И. Энциклопедия элементарной математики. Том I: арифметика. — 1951.
• З. И. Боревич, И. Р. Шафаревич. Теория чисел. — М.: Наука, 1972. — 510 с.

• Сендеров В, Спивак А. КВАНТ. — 2000. — № 1.

• Сендеров В, Спивак А. КВАНТ. — 2000. — № 3.