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

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

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

Если pпростое число и aцелое число, не делящееся на p, то  a^{p-1}-1 делится на p, то есть a^{p-1}\equiv 1 \pmod p .

Другими словами:

~a^{p-1} при делении нацело на p даёт в остатке 1.

К примеру, если a = 2; p = 7, то 2^6 = 64, и 64-1 = 63 = 7 * 9.

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

Малая теорема Ферма уже давно стала одной из главных теорем для исследований не только в теории целых чисел, но и в более широких областях.[1][2].

История[править | править вики-текст]

Пьер Ферма

Пьер Ферма сформулировал исходное утверждение теоремы около 1636 года. Письмо от 18 октября 1640 года Пьера Ферма к французскому математику Бернару Френиклю (Bernard Frénicle de Bessy) содержало следующее положение[3]:

Каждое простое число делит [в оригинале — «измеряет»] одну из степеней любой прогрессии минус 1, для которой показатель степени является делителем данного простого числа минус 1; и после того, как была найдена первая степень, удовлетворяющая этому свойству, все числа, имеющие показатели степени, кратные показателю первой, удовлетворяют тому же свойству.

В качестве примера Ферма приводит прогрессию 3, 9, 27, 81, 243, 729… и простое число 13. 13 делит 27 − 1 (показатель степени для 27 равен 3, а 3 делит 13 − 1), из чего следует, что 13 также делит 729 − 1 (показатель степени для 729 равен 6 и кратен 3).

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

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

Сам Ферма оставил свою теорему без доказательства. Первым, кому удалось его найти, был Готфрид Вильгельм Лейбниц, в рукописях которого утверждается, что доказательство ему было известно до 1683 года. Лейбниц не знал о результате Ферма и открыл теорему независимо[6]. Но работа Лейбница не была опубликована, и доказательство (очень похожее) в 1736 году обнародовал Эйлер в статье Theorematum Quorundam ad Numeros Primos Spectantium Demonstratio[7]. Доказательство малой теоремы Ферма, основанное на том, что целые числа x, 2x, 3x, \dots, (p-1)x сравнимы в некотором порядке с числами 1, 2, 3, \dots, p-1, было опубликовано в 1806 году Джеймсом Айвори[8].

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

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

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

Следствия[править | править вики-текст]

  • Если p — простое число, то в кольце Zp выполняется равенство a^{-1} = a^{p-2}[12].
  • Если p — простое число, отличное от 2 и 5, то число 10^{p-1} - 1, запись которого состоит из одних девяток, делится на p. Отсюда легко следует, что для любого целого числа N, которое не делится на 2 и на 5, можно подобрать число, состоящее только из девяток, которое делится на N. Этот факт используется в теории признаков делимости и периодических дробей[13].
  • Малая теорема Ферма позволяет находить простые делители чисел вида a^4+a^3+a^2+a+1 и a^{2^n}+1.[14].
  • Обобщение малой теоремы Ферма на алгебраические числа (теорема T. Schonemann, 1839): Пусть a_1,\dots,a_d — корни нормированного многочлена f\in \mathbb Z[x] степени d и p — простое число. Тогда a_1^p + a_2^p + \dots + a_d^p \equiv a_1 + \dots + a_d\pmod p [15].

Примеры[править | править вики-текст]

Пример. Найти остаток от деления числа 3^{28} на 7.

Взаимосвязь между малой теоремой Ферма и теоремой Вильсона[править | править вики-текст]

Теорема Лагранжа: если многочлен степени n делится на p при более чем n неконгруэнтных значениях переменной x, то он делится на p при любом значении x.

Рассмотрим многочлен

 G(x) = (x - 1)(x - 2)(x - 3)... (x - (p - 1)) - (x^{p-1}- 1), где p — простое число.

Тогда мы находим:

G(1) = 0,G(2) = 2^{p-1}-1, G(3) = 3^{p-1}-1, ..., G(p-1) = (p-1)^{p-1}.

В силу малой теоремы все эти числа делятся на простое число p, поэтому сравнение G(x) = 0\pmod p имеет p-1 неконгруэнтных решений. С другой стороны, степень многочлена равна всего лишь p-2; отсюда следует, что многочлен G(x) делится на p при всех значениях x, и в частности при x = 0.

Значит G(0) = [(p- 1)! + 1] = 0\pmod p.

А это и есть теорема Вильсона.

Тесты простоты[править | править вики-текст]

Тест Соловея — Штрассена[править | править вики-текст]

Тест Соловея — Штрассена опирается на малую теорему Ферма и свойства символа Якоби[16]:

  • Если n — нечетное составное число, то количество целых чисел a, взаимнопростых с n и меньших n, удовлетворяющих сравнению \textstyle a^{(n-1)/2} \equiv \left( \frac{a}{n} \right)\pmod{n}, не превосходит \frac{n}{2}.

Составные числа n удовлетворяющие этому сравнению называются псевдопростыми Эйлера-Якоби по основанию a.

Тест Миллера — Рабина[править | править вики-текст]

Тест Миллера — Рабина опирается на малую теорему Ферма[17]:

  • Для любого нечетного простого  n = 2^{s}*t, где t нечетное и для любого числа  a, 0< a < n, последовательность  a^{t}\pmod n, a^{2t}\pmod n, a^{2^2{t}}\pmod n, ... ,a^{2^s{t}}\pmod n также имеет либо все 1 или пары −1,1, встречающихся где-то в последовательности.

Свидетели простоты

  • Пусть ~m — нечётное число большее 1. Число ~{m-1} однозначно представляется в виде m-1 = 2^s \cdot t, где ~t нечётно. Целое число ~a, ~1 < a < m, называется свидетелем простоты числа ~m, если выполняется одно из условий:
  • ~a^t\equiv 1\pmod m

или

  • существует целое число ~k, ~0\leq k<s, такое, что ~ a^{2^kt}\equiv m-1\pmod m.

Теорема Рабина утверждает, что составное нечётное число m имеет не более \varphi(m)/4 различных свидетелей простоты, где \varphi(m) — функция Эйлера.

Тест Агравала — Каяла — Саксены[править | править вики-текст]

Тест Агравала — Каяла — Саксены опирается на малую теорему Ферма[17]:

  • Если n простое, то для любого r>0 и любого  a, 0<a<n;  (x+a)^n = x^n + a\pmod {n,x^r-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 — составное число.

Вообще, справедливы следующие два утверждения. Если пара (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.[18]


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

Примечания[править | править вики-текст]

  1. Энциклопедия элементарной математики, Книга 1, Арифметика, Александров П. С., Маркушевич А. И., Хинчин А. Я., 1961.— С. 280
  2. З. И. Боревич, И. Р. Шафаревич Теория чисел. — М: Наука, 1972. — 175 с.
  3. Письмо от 18 октября 1640 года Пьера Ферма к французскому математику Бернару Френиклю. Архивировано из первоисточника 22 декабря 2006.
  4. Honsberger, R. (1973), An Old Chinese Theorem and Pierre de Fermat, Mathematical Gems, I, Washington, DC: Math. Assoc. Amer., pp. 1-9.
  5. Ribenboim, P. (1996), The New Book of Prime Number Records, New York: Springer-Verlag, pp. 103—105, ISBN 0-387-94457-5.
  6. Данциг, Т. Числа — язык науки, 2008
  7. David C. Marshall, Edward Odell, Michael Starbird. Number Theory Through Inquiry. — 2006. — pp. 62-63
  8. Джон Дж. О’Коннор и Эдмунд Ф. Робертсон. Малая теорема Ферма (англ.) — биография в архиве MacTutor.
  9. Данциг, Т. Числа — язык науки, 2008, с. 231-234
  10. Винберг, 2008, с. 43
  11. КВАНТ, 2000, №1, Сендеров В, Спивак А. Малая теорема Ферма.
  12. Акритас А. Основы компьютерной алгебры с приложениями, стр. 83.
  13. Данциг, Т. Числа — язык науки, 2008, с. 232-234
  14. КВАНТ, 2000, № 3, Сендеров В, Спивак А Малая теорема Ферма
  15. Винберг, 2008
  16. Нестеренко, 2011
  17. 1 2 Manindra Agrawal. Primality Tests Based on Fermat’s Little Theorem // Lecture Notes in Computer Science. — 2006. — Vol. 4308. — P. 288-293.
  18. Шитов Ю. А. Теоретико-численные методы в криптографии.

Литература[править | править вики-текст]