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


§

Вспомогательные результаты к разделу МОДУЛЯРНАЯ АРИФМЕТИКА.


Критерий Вильсона

Т

Теорема [Вильсон]. Для того чтобы число p>2 было простым, необходимо и достаточно, чтобы выполнялось сравнение

(p-1)! \equiv -1 \pmod{p} \ .

Доказательство. Необходимость. Если p_{} — простое, то для любого A\in \{1,\dots, p-1 \} существует единственное решение сравнения Ax\equiv 1 \pmod{p} (см. результат ЗДЕСЬ). Обозначим его \tilde A_{} и назовем числа A_{} и \tilde A_{} дополнительными. Равенство A = \tilde A_{} дополнительных чисел между собой возможно только когда A =1 или A =p-1. В самом деле, сравнение

A^2 \equiv 1 \pmod{p}

равносильно

(A-1)(A+1) \equiv 0 \pmod{p} \quad \iff \quad A \equiv 1 \pmod{p} или \ A \equiv -1 \pmod{p} \ .

Итак, все оставшиеся числа 2, 3,\dots, p-2 могут быть объединены в пары дополнительных. Например, для p=13:

2\cdot 7 \equiv_{_{13}} 1,\ 3\cdot 9 \equiv_{_{13}} 1,\ 4\cdot 10 \equiv_{_{13}} 1,\ 5\cdot 8 \equiv_{_{13}} 1,\ 6\cdot 11 \equiv_{_{13}} 1

Понятно, что и в общем случае перемножение всех подобных сравнений в левой части даст произведение всех чисел 2, 3,\dots, p-2, а в правой части — единицу:

2\cdot 3 \times \cdots \times (p-2) \equiv 1 \pmod{p} \ .

Домножив последнее сравнение на p-1 \equiv -1 \pmod{p}, получим условие теоремы.

Достаточность. Пусть условие теоремы выполняется, но, тем не менее, число p_{} — составное, т.е. у него имеется нетривиальный делитель q:\ 1< q <p. Формула (p-1)! \equiv -1 \pmod{p} означает, что число (p-1)!+1 делится на p_{}, а следовательно, и на q_{}. Однако это невозможно, так как число (p-1)! делится на любое число 1,\, 2,\, \dots,\, p-1, в том числе и на q_{}, и, значит, сумма (p-1)!+1 делиться на q_{} не может. Противоречие доказывает ошибочность предположения о непростоте p_{}.

Итак, теорема Вильсона дает конструктивный критерий проверки числа p_{} на простоту. К сожалению, с вычислительной точки зрения он слишком громоздок, хотя вычисление (p-1)! \pmod{p} и можно организовать по схеме, аналогичной алгоритму вычисления A^B \pmod{p}, т.е. результат каждого умножения «усекать» до остатка от деления на p_{}.

П

Пример. Для p=13:

\begin{array}{|c|c|c|c|c|c|c|c|c|c|c|c|c|} \hline k & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 \\ \hline k! \pmod{p} & 1 & 2 & 6 & 24 & 55 & 18 & 35 & 72 & 63 & 110 & 66 & 12 \\ & & & & {\scriptstyle \equiv_{_{13}}11} & {\scriptstyle \equiv_{_{13}}3} & {\scriptstyle \equiv_{_{13}}5} & {\scriptstyle \equiv_{_{13}}9} & {\scriptstyle \equiv_{_{13}}7} & {\scriptstyle \equiv_{_{13}}11} & {\scriptstyle \equiv_{_{13}}6} & {\scriptstyle \equiv_{_{13}}1} & \\ \hline \end{array}

Теорема Ферма-Эйлера о представлении простого числа в виде суммы двух квадратов

Простое число p>2 при делении на 4 дает в остатке либо 1, либо 3.

П

Пример. Рассмотрим простые числа 13,29,61,137,757. Оказывается, что

13=2^2+3^2,\ 29=2^2+5^2,\ 61=5^2+6^2,\ 137=4^2+11^2,\ 757=9^2+26^2 \, .

Обратим внимание, что все рассмотренные простые числа имели вид 4\,k+1 при k \in \mathbb N.

?

Показать, что простое число вида 4k+3 не может быть представлено в виде суммы двух квадратов простых чисел.

Т

Теорема [Ферма,Эйлер]. Для того, чтобы простое число p могло быть представлено в виде суммы двух квадратов натуральных чисел необходимо и достаточно, чтобы p \equiv 1 \pmod{4}.

Доказательство [Лагранж]. Достаточность. Пусть p — простое, такое, что p=4\,n+1 при n\in \mathbb N. На основании теоремы Вильсона число (4\,n)!+1 делится на p. Тогда и [(2n)!]^2+1 делится на p. В самом деле, докажем, что

(4\,n)!+1 \equiv [(2n)!]^2+1 \pmod{p} \, .

Действительно,

(4n)!=(2n)! (2n+1)(2n+2)\times\dots\times (4n)+1=
=(2n)! (p-2n)(p-2n+1)\times\dots\times (p-1)+1=
=(2n)! p (p-2n+1)\times\dots\times (p-1) - (2n)! (2n)(p-2n+1)\times\dots\times (p-1)+1 \equiv_{p}
\equiv_p - (2n)! (2n)(p-2n+1)\times\dots\times (p-1)+1 \equiv_{p}

и далее повторяем тот же самый прием:

\equiv_{p} (2n)! (2n)(2n-1)\times\dots\times (p-1)+1 \equiv_p \dots \equiv_p (-1)^{2n} (2n)! (2n)!+1 \, .

Обозначим \mathfrak N = (2n)!. Мы доказали, что

\mathfrak N^2 \equiv -1 \pmod{p} \, .

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

\{ u+ \mathfrak N v \ \mid \ \{u,v\} \subset \{0,1,\dots, \lfloor \sqrt{p} \rfloor \} \} \, .

В этом наборе содержится (\lfloor \sqrt{p} \rfloor +1)^2>p чисел, поэтому будут существовать по крайней мере две различные пары чисел (u_1,v_1) и (u_2,v_2 ) такие, что остатки от деления u_1+\mathfrak N v_1 и u_2+\mathfrak N v_2 на p будут одинаковыми. Тогда число

(u_1-u_2)+ \mathfrak N (v_1-v_2) = U+ \mathfrak N V

делится на p. Здесь обозначили U=u_1-u_2, V=v_1-v_2; очевидно, что |U|< \lfloor \sqrt{p} \rfloor и |V|< \lfloor \sqrt{p} \rfloor. Но, следовательно, и число

U^2- \mathfrak N^2 V^2 = (U+ \mathfrak N V)(U- \mathfrak N V)

делится на p:

U^2- \mathfrak N^2 V^2 \equiv 0 \pmod{p} \, .

По доказанному \mathfrak N^2 \equiv -1 \pmod{p} и тогда

U^2+V^2 \equiv 0 \pmod{p} \, ,

т.е. U^2+V^2 делится на p: U^2+V^2=qp при некотором q\in \mathbb N. Ввиду неравенств для модулей чисел U и V должно быть выполнено

U^2+V^2 \le 2 \lfloor \sqrt{p} \rfloor^2 < 2p \, ,

и, поэтому q=1. Достаточность доказана.

Необходимость. Если p=a^2+b^2>2 — простое, то числа a и b — разной четности. Пусть a=2\,n+1, b=2\, m. Тогда

a^2+b^2 = (2\,n+1)^2+ (2\, m)^2 = 4(n^2+n+m^2)+1 \equiv 1 \pmod{4} \, .

Можно доказать, что представление простого числа вида 4k+1 в виде суммы квадратов натуральных чисел единственно (с точностью до перестановки слагаемых). Вопрос о практическом нахождении разложения в такую сумму решается следующим алгоритмом .

1. Найдем число A такое, что A^2 \equiv - 1 \pmod {p}. Фактическое его нахождение упростится, если известен первообразный корень \Lambda по модулю p: число

A=\Lambda^{(p-1)/4} \pmod{p}

является решением сравнения, вторым решением очевидно является p- A. Одно из этих чисел меньше p/2, обозначим его r_0.

2. Число r_0 взаимно просто с p, т.е. \operatorname{HOD} (r_0,p)=1. Запустим алгоритм Евклида поиска этого \operatorname{HOD} и остановим его как только получившийся остаток станет меньше \sqrt{p}:

\begin{array}{lcl} p&=&r_0q_1+r_1 \ , \quad \sqrt{p}<r_1<r_0; \\ r_0&=&r_1q_2+r_2 \ , \quad \sqrt{p}<r_2<r_1; \\ \dots && \dots \\ r_{k-3}&=&r_{k-2}q_{k-1}+r_{k-1} \ , \quad \sqrt{p} <r_{k-1}< r_{k-2}; \\ r_{k-2}&=&r_{k-1}q_{k}+r_{k} \ , \quad 0<r_{k}< \sqrt{p} . \end{array}

3. Утверждается, что число b=\sqrt{p-r_k^2} — натуральное, и, тем самым, числа a=r_k и b представляют решение задачи.

Для доказательства обратимся к пункту Линейное представление HOD. Для каждого остатка в алгоритме Евклида нахождения \operatorname{HOD} (r_0,p)=1 можно выписать его линейное представление:

r_j=u_j r_0+v_j p \ ,

где u_j и v_j являются некоторыми полиномами от частных q_1,\dots,q_j из алгоритма. Эти выражения известны под названием континуант. Возведя последнее равенство в квадрат, и учитывая r_0^2 \equiv - 1 \pmod {p}, получим

r_j^2+u_j^2 \equiv 0 \pmod p \, .

Таким образом, получили цепочку равенств

r_0^2+1^2 = pQ_0,\ r_1^2+u_1^2 =pQ_1,\dots, r_j^2+u_j^2 =pQ_j, \dots

Докажем, что числа этой последовательности убывают.

П

Пример. Для p= 757 имеем \Lambda=2 первообразным корнем поскольку 756=2^2\cdot 3^3 \cdot 7 и

2^{756/2} \not\equiv 1,\ 2^{756/3} \not\equiv 1, 2^{756/7} \not\equiv 1 \pmod{757}\, .

Имеем

2^{756/4} \equiv 87 \pmod{757}, \ u \ r_0=87 \, .

По алгоритму Евклида нахождения \operatorname{HOD} (r_0,p) получаем

r_1= p \pmod{r_0} = 61,\ r_2 = r_0 \pmod{r_1}=26,\ r_3 = r_1 \pmod{r_2}=9 < \sqrt{p} \, .

Число \sqrt{757-9^2}= 26.


2018/02/12 21:37 редактировал au