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

Рассмотрим однородный многочлен степени p с n переменными:

${\displaystyle S(x,y,z,\dots ,w)=(x+y+z+\dots +w)^{p}-(x^{p}+y^{p}+z^{p}+\dots +w^{p}).}$

Раскрывая скобки, получим коэффициент при одночлене ${\displaystyle Mx^{\alpha }y^{\beta }z^{\gamma }\cdot \ldots \cdot w^{\nu }}$ (где хотя бы две из степеней ${\displaystyle \alpha ,\beta ,\gamma \ldots \nu }$ не равны нулю, а сумма всех степеней равна p) называется мультиномиальным коэффициентом и вычисляется по формуле

${\displaystyle M={\frac {p!}{\alpha$ !\beta !\gamma !\dots \nu !}}.}

Поскольку степени ${\displaystyle \alpha ,\beta ,\gamma ...}$ меньше, чем ${\displaystyle p,}$ то знаменатель мультиномиального коэффициента не содержит множителей, которые могли бы сократиться с ${\displaystyle p,}$ следовательно, все коэффициенты многочлена ${\displaystyle S}$ кратны ${\displaystyle p.}$ Таким образом, верно следующее тождество:

${\displaystyle (x+y+z+\dots +w)^{p}-(x^{p}+y^{p}+z^{p}+\dots +w^{p})=pH(x,y,z,\dots ,w),}$

где ${\displaystyle H(x,y,z,...,w)}$ — многочлен с положительными целыми коэффициентами.

Пусть теперь в этом тождестве ${\displaystyle x=y=...=w=1,H(1,1,1,...,1)=N,}$ тогда ${\displaystyle n^{p}-n=Np}$ (здесь n — число переменных в исходном полиномиальном выражении), следовательно, ${\displaystyle n(n^{p-1}-1)}$ кратно ${\displaystyle p}$. Если ${\displaystyle n}$ не делится на простое число ${\displaystyle p,}$ то на него делится ${\displaystyle n^{p-1}-1}$[10].

Докажем, что для любого простого p и целого неотрицательного a, a^p − a делится на p. Доказываем индукцией по a.

База. Для a = 0, a^p − a = 0 и делится на p.

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

${\displaystyle a^{p}-a=(k+1)^{p}-(k+1)=k^{p}+1+\sum _{l=1}^{p-1}{p \choose l}k^{l}-k-1=k^{p}-k+\sum _{l=1}^{p-1}k^{l}{p \choose l}}$

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

Для отрицательных a и нечётных p теорему легко доказать подстановкой b = −a. Для отрицательных a и p = 2 истинность теоремы следует из a² − a = a(a − 1)[11].

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

Напомним, что порядком конечной группы ${\displaystyle G}$ называется число её элементов, а порядком элемента ${\displaystyle g\in G}$ — наименьший натуральный показатель его степени, равной единичному элементу ${\displaystyle e}$ группы ${\displaystyle G}$.

Пусть ${\displaystyle G}$ — конечная группа порядка ${\displaystyle n}$. Из того, что порядок элемента ${\displaystyle g\in G}$ делит ${\displaystyle n}$, следует, что ${\displaystyle g^{n}=e}$.

Рассмотрим поле ${\displaystyle \mathbb {Z} _{p}}$ вычетов по модулю ${\displaystyle p}$. Вычет целого числа ${\displaystyle a}$ будем обозначать через ${\displaystyle a}$. Ненулевые элементы поля ${\displaystyle \mathbb {Z} _{p}}$ образуют группу относительно умножения.

Порядок этой группы, очевидно, равен ${\displaystyle p-1}$. Её единичным элементом является ${\displaystyle 1}$. Отсюда следует, что для каждого числа ${\displaystyle a}$, не делящегося на ${\displaystyle p}$, ${\displaystyle a^{p-1}=1}$, но это как раз означает сравнение ${\displaystyle a^{p-1}\equiv 1{\pmod {p}}}$[1]

Лемма. Для любого простого числа ${\displaystyle p}$ и целого числа ${\displaystyle k}$, не кратного ${\displaystyle p}$, произведения ${\displaystyle k}$ и чисел ${\displaystyle 1,2,3,\ldots ,p-1}$ при делении на ${\displaystyle p}$ в остатке дают те же самые числа ${\displaystyle 1,2,3,\ldots ,p-1,}$ возможно, записанные в некотором другом порядке.

Поскольку согласно вышеприведённой лемме остатки от деления чисел a, 2a, 3a, ..., (p − 1)a — это с точностью до перестановки числа 1, 2, 3, ..., p − 1, то ${\displaystyle a\cdot 2a\cdot 3a\ldots (p-1)a\equiv 1\cdot 2\cdot 3\ldots (p-1){\pmod {p}}}$. Отсюда ${\displaystyle a^{p-1}(p-1)!\equiv (p-1)!{\pmod {p}}}$. Последнее соотношение можно сократить на (p − 1)!, поскольку все сомножители являются числами, взаимно простыми с основанием p, в результате получаем требуемое утверждение ${\displaystyle a^{p-1}\equiv 1{\pmod {p}}}$[12].

Теорема Лагранжа в теории чисел утверждает, что если многочлен степени ${\displaystyle n}$ делится на простое число ${\displaystyle p}$ при более чем ${\displaystyle n}$ несравнимых по модулю ${\displaystyle p}$ (т. е. имеющих разные остатки при делении на ${\displaystyle p}$ ) значениях переменной ${\displaystyle x}$, то он делится на ${\displaystyle p}$ при любом значении ${\displaystyle x}$.

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

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

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

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

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

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

А если в дополнение к этому доказать, что для всех непростых натуральных ${\displaystyle n}$, кроме ${\displaystyle n=4}$, ${\displaystyle (n-1)!\equiv 0{\pmod {n}}}$, то получим доказательство теоремы.[17]