Викия

Математика

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

1457статей на
этой вики
Добавить новую страницу
Обсуждение0 Share

Обнаружено использование расширения AdBlock.


Викия — это свободный ресурс, который существует и развивается за счёт рекламы. Для блокирующих рекламу пользователей мы предоставляем модифицированную версию сайта.

Викия не будет доступна для последующих модификаций. Если вы желаете продолжать работать со страницей, то, пожалуйста, отключите расширение для блокировки рекламы.

Малая теорема Ферма — классическая теорема теории чисел. Она была открыта в 1640 году французом Пьером Ферма (1601—1665). Теорема утверждает, что:

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

Или, что то же самое:

Если p — простое число, a — целое число, то a^p-a делится на p.

Разбор частных случаевПравить

Из любых двух последовательных целых чисел a и a+1 одно четное, а другое нечетное. Поэтому произведение a(a+1)=a^2+a четно при любом целом a.

Делимость числа a^2+a на 2 можно доказать и по-другому, разобрав два случая:

  • Если a четно, то a^2 тоже четно, а сумма двух четных чисел a и a^2 четна.
  • Если a нечетно, то a^2 тоже нечетно, а сумма двух нечетных чисел a и a^2 четна.

При p=2 в малой теореме Ферма фигурирует другой многочлен: a^2-a=(a-1)a. Все его значения в целых точках — четные числа (доказательство аналогично приведенному выше).

Теперь рассмотрим многочлен a^3-a. Его легко разложить на множители:

a^3-a=a(a^2-1)=a(a-1)(a+1).

Получается произведение трех последовательных целых чисел: a-1, a и a+1. Как мы уже знаем, это произведение четно. Поскольку из любых трех последовательных целых чисел одно кратно 3, их произведение (a-1)a(a+1)=a^3-a кратно 3 (и, значит, даже кратно 6).

Многочлен a^4-a при a=2 и a=3 принимает значения 2^4-2=14 и 3^4-3=78. Никаких общих делителей кроме 2 и 1 у них нет. Впрочем, число 4 составное, а малая теорема Ферма говорит только о многочленах вида a^p-a, где p — простое число.

Пусть p=5. Вычислим несколько значений многочлена a^5-a. При a=\pm1 и при a=0 получаем 0. Далее: 2^5-2=30, 3^5-3=240, 4^5-4=1020, 5^5-5=3120, 6^5-6=7770,... Все эти значения кратны числу 30.

Поскольку 30=2\cdot3\cdot5, доказательство делимости на 30 распадается на три части: во-первых, надо доказать, что a^5-a кратно 2; во-вторых, a^5-a кратно 3; в-третьих, a^5-a кратно 5.

Первая часть очевидна: числа a^5 и a либо оба четны, либо оба нечетны. Не вызывает затруднений и вторая часть:

a^5-a=a(a^4-1)=a(a^2-1)(a^2+1)=(a-1)a(a+1)(a^2+1),

произведение трех последовательных целых чисел всегда кратно 3.

Чуть сложнее третья часть. Так как a^2+1=a^2-4+5=(a-2)(a+2)+5, то a^2+1\equiv(a-2)(a+2)\ \left(\mathrm{mod}\ 5\right). Отсюда:

(a-1)a(a+1)(a^2+1)\equiv(a-2)(a-1)a(a+1)(a+2)\equiv0\ \left(\mathrm{mod}\ 5\right),

потому что среди пяти подряд идущих целых чисел есть одно, делящееся на 5.

Можно было поступить иначе и перебрать все остатки от деления числа a на 5. Если a\equiv0\ \left(\mathrm{mod}\ 5\right), то само a делится на 5. Если a\equiv1\ \left(\mathrm{mod}\ 5\right), то a-1 делится на 5. Если a\equiv4\ \left(\mathrm{mod}\ 5\right), то a+1 делится на 5. Наконец, если a\equiv2\ \left(\mathrm{mod}\ 5\right) или a\equiv3\ \left(\mathrm{mod}\ 5\right), то a^2+1 делится на 5. Получается, что произведение (a-1)a(a+1)(a^2+1) кратно 5 в любом случае.

Теперь рассмотрим разложение на множители многочлена a^7-a:

a^7-a=a(a^6-1)=a(a^3-1)(a^3+1)=a(a-1)(a^2+a+1)(a+1)(a^2-a+1).

Поскольку

a^2+a+1=(a^2+a-6)+7\equiv a^2+a-6=(a-2)(a+3)\ \left(\mathrm{mod}\ 7\right)

и

a^2-a+1=(a^2-a-6)+7\equiv a^2-a-6=(a+2)(a-3)\ \left(\mathrm{mod}\ 7\right),

то:

a^7-a\equiv(a-3)(a-2)(a-1)a(a+1)(a+2)(a+3)\equiv0\ \left(\mathrm{mod}\ 7\right).

Пусть p=11. Очевидно:

a^{11}-a=a(a^5-1)(a^5+1)=a(a-1)(a^4+a^3+a^2+a+1)(a+1)(a^4-a^3+a^2-a+1).

По-прежнему легко проверить, что:

(a-3)(a-4)(a-5)(a-9)\equiv a^4+a^3+a^2+a+1\ \left(\mathrm{mod}\ 11\right)

и

(a-2)(a-6)(a-7)(a-8)\equiv a^4-a^3+a^2-a+1\ \left(\mathrm{mod}\ 11\right).

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

a^{11}-a\equiv(a-9)(a-8)...(a-1)a(a+1)\equiv0\ \left(\mathrm{mod}\ 11\right).

Чем больше p, тем больше приходится перебирать остатков от деления на p и раскрывать скобок. Теперь проще рассмотреть доказательства общего случая, приведенные ниже.

Доказательство по индукцииПравить

Сначала докажем теорему для любого простого p и натурального a (напомним, что теорема верна для всех целых a). Доказываем индукцией по a при помощи бинома Ньютона.

База. Если a=1, то 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^{p-l}-k-1=k^p-k+\sum_{l=1}^{p-1}{p \choose l}k^{p-l}

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

Теорема доказана для всех натуральных a. В случае a=0 утверждение теоремы очевидно. Для отрицательных же 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.

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

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

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

Eсли a и p взаимно простые числа, такие что a^{p-1} - 1 делится на p, то число p может не быть простым. В случае, когда p является составным, p называется псевдопростым по основанию a. Ф.Саррус в 1820 году нашёл 341 = 11×31 — первое псевдопростое число, по основанию 2.

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

История Править

Пьер Ферма сформулировал исходное утверждение теоремы около 1636 года. Письмо от 18 октября 1640 года Пьера Ферма к Френиклю содержало следующее положение: p делит a^{p-1} в случае, когда p является простым числом и a взаимно простое с p.

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

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

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

См. также Править

Ссылки Править


bg:Малка теорема на Фермаhe:המשפט הקטן של פרמה hu:Kis Fermat-tétel id:Teorema kecil Fermatnl:Kleine stelling van Fermat sl:Fermatov mali izrek sv:Fermats lilla sats

Викия-сеть

Случайная вики