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

Самая известная теорема, действительно доказанная Ферма (1640а) и известная так «малая» или «меньшая» теорема, чтобы отличить ее от его «последней» или «великой» теоремы (следующий раздел), — следующая.

Если простое число и взаимно простое число к тогда

Эквивалентные формулировки этого результата, которые избегают использование языка «конгруэнтно неизвестного во времена Ферма, имеют вид:

или

Последнее выполняется, потому что делится на только тогда, когда , поскольку простое число и не делит

Малая теорема Ферма недавно стала незаменимой в некоторых областях прикладной математики, таких как криптография, поэтому узнать, что она берет начало в одной из наименее применяемых задач в математике, построении совершенных чисел, наводит на размышления. Как мы видели в разделе 3.2, оно зависит от построения простых чисел вида и именно по этой причине Ферма вначале заинтересовался условиями, при которых имеет делители. В то же самое время (середина 1630-х гг.) он исследовал биномиальные коэффициенты, и сочетание этих двух интересов, весьма вероятно, привело к открытию его малой теоремы для

Его собственное доказательство неизвестно, но различные авторы [например, Вейль (1984), с. 56] указывали, что теорема непосредственно следует из того, что Для простого, делятся на

следовательно,

делится на поэтому, тоже.

Но так доказать, что делятся на Это естественно следует из формулы Леви бен Гершона

которая показывает, что простое число это множитель числителя, но не знаменателя. Знаменатель, тем не менее, делит числитель, поскольку — целое число, поэтому множитель должен оставаться целым после того, как имело место деление. Ферма, возможно, не получил именно этого результата, поскольку у него еще не было комбинаторной интерпретации биномиальных коэффициентов Паскаля, но у него была формула

которая косвенно ее выражает, и, из которой можно легко извлечь свойство делимости [см. Вейль (1984), с. 47].

До сих пор мы имеем доказательство малой теоремы Ферма для Вейль (1984) предполагает два возможных пути из этого пункта к общей теореме. Один — итерацией биномиальной теоремы, метод, который использовался Эйлером (1736) в первом опубликованном доказательстве теоремы Ферма. Другой — непосредственным применением полиномиальной теоремы, метод самого раннего известного доказательства, которое содержится в неопубликованной статье Лейбница от конца 1670-х гг. [см. Вейль (1984), с. 56].

Точно также как коэффициент

где (упражнение 11.2.4). Этот полиномиальный коэффициент делится на по той же аргументации, что и выше, в том случае, если нет Таким образом, коэффициенты всех членов, кроме делятся на простое число Отсюда следует, заменяя каждый из членов на 1, что

то есть, делится на Тогда, если само взаимно простое число (следовательно, не делится на мы имеем пр делимое на или общую малую теорему Ферма.

Упражнения

(см. скан)

(см. скан)