УказательРазделыОбозначенияАвторО проекте


Вспомогательная страница к пункту ☞ ТЕОРЕМА ФЕРМА.


Т

Теорема [Ферма (малая)]. Если p_{} простое и A_{} не делится на p_{}, то

A^{p-1} \equiv 1 \pmod{p} \ .

Доказательство основано на одном свойстве биномиальных коэффициентов. Если внимательно рассмотреть треугольник Паскаля:

\begin{array}{l|cccccccccccccccc} &&&&&&&&1 \\ n=1&&&&&&& 1 && 1 \\ n=2&&&&&& 1 && 2 && 1 \\ n=3&&&&&1 && 3 && 3 && 1 \\ n=4&&&&1 && 4 && 6 && 4 && 1 \\ n=5&&&1 && 5 && 10 && 10 && 5 && 1 \\ n=6&&1 && 6 && 15 && 20 && 15 && 6 && 1 \\ n=7&1 && 7 && 21 && 35 && 35 && 21 && 7 && 1 \\ \dots& \dots && && && \dots && && && \end{array}

то можно увидеть, что при некоторых показателях n_{} все элементы в строках (за исключением крайних единиц) делятся на n_{}.

Лемма. Для простого числа p_{} и k\in \{1,\dots,p-1 \} биномиальный коэффициент C_p^k делится на p_{}.

Доказательство. Действительно,

C_p^k= \frac{p\overbrace{(p-1)\times \dots \times (p-k+1)}^{=q}}{k!} \ .

По теореме, приведенной ☞ ЗДЕСЬ, это число — целое, следовательно, произведение p\cdot q должно делиться на k! . Но поскольку p_{} простое, то оно взаимно просто с каждым из чисел 1,2,\dots,k и, следовательно (по теореме 2, приведенной ☞ ЗДЕСЬ ), \operatorname{HOD} (p,k!)=1. Тогда (по теореме 3, приведенной ☞ ЗДЕСЬ ), число q_{} должно делиться на k!: q=k! \, q_1, \ q_1\in \mathbb N, что и доказывает C_p^k=pq_1\in \mathbb Z.

Доказательство теоремы Ферма. Имеем для любых целых A_1,A_2,\dots :

(A_1+A_2)^p=A_1^p+\underbrace{C_p^1A_1^{p-1}A_2+C_p^2A_1^{p-2}A_2^2+\dots+ C_p^{p-1}A_1A_2^{p-1}}+A_2^p \ ,

где отмеченные скобкой слагаемые, в соответствии с леммой, делятся на p_{}. Следовательно, справедливо

(A_1+A_2)^p \equiv A_1^p +A_2^p \pmod{p} \ .

Обобщаем этот результат:

(A_1+A_2+A_3)^p \equiv \ (A_1 +A_2)^p+A_3^p\ \equiv \ A_1^p +A_2^p+A_3^p \pmod{p} \ ,

и далее по индукции:

(A_1+A_2+\dots+A_n)^p \equiv A_1^p +A_2^p+\dots+A_n^p \pmod{p} \ .

Подставляем в это соотношение наборы значений A_1=A_2=\dots=A_n=1 и A_1=A_2=\dots=A_n=-1 :

n^p \equiv n \pmod{p}\ , \ (-n)^p \equiv (-1)^p n \pmod{p}\ \ .

Все простые числа p_{}, за исключением 2_{} — нечетные, для них (-1)^p=-1. Для p=2: n\equiv -n \pmod{p}. Таким образом, имеем справедливость формулы

A^{p} \equiv A \pmod{p}

как для положительных, так и для отрицательных чисел A\in \mathbb Z.

При дополнительном предположении, что A_{} не делится на p_{}, справедливость утверждения теоремы очевидна.

=>

Для простого числа p_{} мультиномиальный коэффициент

\frac{p!}{n_1!\, n_2! \times \dots \times n_K!} \quad npu \quad n_1+n_2+\dots+n_K=p, n_1<p,n_2<p,\dots,n_K<p

делится на p_{}.

Еще одним интересным следствием леммы и теоремы Ферма является следующий результат.

Т

Теорема [Шлёмильх]. Для произвольного полинома F_{}(x) с целыми коэффициентами и простого числа p_{} выполняется

\left[F(x)\right]^p \equiv F(x^p) \pmod{p} \ .

ДоказательствоЗДЕСЬ.


2013/11/11 15:43 редактировал au