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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

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

Если 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. Малая теорема Ферма уже давно стала одной из главных теорем для исследований не только в теории целых чисел, но и в более широких областях арифметики и алгебры[1].[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} (фактически, частный случай малой теоремы Ферма)[3]. Тем не менее, обратное утверждение (о том, что из 2^p \equiv 2 \pmod {p} следует, что p простое), а, следовательно, и гипотеза в целом, оказались неверными (см. ниже).

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

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

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

[править] Доказательство

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

[править] Леммы

Лемма 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).[7]

Обобщение теоремы Ферма на случай составного числа 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.[8]

[править] Малая теорема Ферма для алгебраических чисел

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

[править] Обобщения

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

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

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

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

[править] См. также

[править] Литература

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

[править] Примечания

  1. Энциклопедия элементарной математики, Книга 1, Арифметика, Александров П.С., Маркушевич А.И., Хинчин А.Я., 1961.— С. 280.
  2. З. И. Боревич, И. Р. Шафаревич Теория чисел. — М: Наука, 1972. — 175 с.
  3. Honsberger, R. (1973), An Old Chinese Theorem and Pierre de Fermat, Mathematical Gems, I, Washington, DC: Math. Assoc. Amer., pp. 1–9.
  4. Ribenboim, P. (1996), The New Book of Prime Number Records, New York: Springer-Verlag, pp. 103–105, ISBN 0387944575.
  5. 1 2 Данциг, Т. Числа - язык науки, 2008, с. 232-234
  6. Винберг Э. Б. Малая теорема Ферма и ее обобщения // Математическое просвещение. — 2008. — В. 12. — С. 43
  7. КВАНТ, 2000, №1, Сендеров В, Спивак А Малая теорема Ферма.
  8. КВАНТ, 2000, №3, Сендеров В, Спивак А Малая теорема Ферма.
  9. Шитов Ю. А. Теоретико-численные методы в криптографии.