Инструменты сайта


§

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


Т

Теорема [Ферма (малая)]. Если $ 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} \ . $$

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

modular/vspom5.txt · Последние изменения: 2020/09/22 21:08 — au