Математика
Регистрация
Advertisement

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

Если простое число, целое число, не делящееся на , то делится на .

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

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

Разбор частных случаев[]

Из любых двух последовательных целых чисел и одно четное, а другое нечетное. Поэтому произведение четно при любом целом .

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

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

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

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

.

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

Многочлен при и принимает значения и . Никаких общих делителей кроме и у них нет. Впрочем, число составное, а малая теорема Ферма говорит только о многочленах вида , где — простое число.

Пусть . Вычислим несколько значений многочлена . При и при получаем . Далее: , , , , ,... Все эти значения кратны числу .

Поскольку , доказательство делимости на распадается на три части: во-первых, надо доказать, что кратно ; во-вторых, кратно ; в-третьих, кратно .

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

,

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

Чуть сложнее третья часть. Так как , то . Отсюда:

,

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

Можно было поступить иначе и перебрать все остатки от деления числа на . Если , то само делится на . Если , то делится на . Если , то делится на . Наконец, если или , то делится на . Получается, что произведение кратно в любом случае.

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

.

Поскольку

и

,

то:

.

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

.

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

и

.

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

.

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

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

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

База. Если , то и делится на .

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

Заметим, что делится на по предположению индукции. Что же касается остальных слагаемых, то . Для , числитель этой дроби делится на , а знаменатель — не делится, следовательно, делится на . Таким образом, вся сумма делится на .

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

Обобщения теоремы[]

Небольшое обобщение теоремы, которое из неё следует, таково: если p простое число, а m и n — такие положительные целые числа, что , тогда . В данной форме теорема используется в системе шифрования с открытым ключом RSA.

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

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

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

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

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

История[]

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

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

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

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

См. также[]

  • Система шифрования с открытым ключом RSA

Ссылки[]


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

Advertisement