!!§!! Вспомогательные результаты к разделу ((:modular МОДУЛЯРНАЯ АРИФМЕТИКА)). ---- ~~TOC~~ ==Критерий Вильсона== !!Т!! **Теорема [Вильсон]**. //Для того чтобы число// $ p>2 $ //было простым, необходимо и достаточно, чтобы выполнялось сравнение// $$ (p-1)! \equiv -1 \pmod{p} \ . $$ **Доказательство.** Необходимость. Если $ p_{} $ --- простое, то для любого $ A\in \{1,\dots, p-1 \} $ существует единственное решение сравнения $ Ax\equiv 1 \pmod{p} $ (см. результат ☞ ((:modular#алгоритм_решения ЗДЕСЬ))). Обозначим его $ \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} \ \mbox{ или } \ 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)! \pmod{p} $ и можно организовать по схеме, аналогичной ((:modular#вычисление_остатков_степенных_выражений алгоритму вычисления)) $ 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 $ в виде суммы квадратов натуральных чисел единственно (с точностью до перестановки слагаемых). Вопрос о практическом нахождении разложения в такую сумму решается следующим алгоритмом ((https://ru.wikipedia.org/wiki/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%9A%D0%BE%D1%80%D0%BD%D0%B0%D1%87%D1%87%D0%B8 .)) 1. Найдем число $ A $ такое, что $ A^2 \equiv - 1 \pmod {p} $. Фактическое его нахождение упростится, если известен ((:modular:index#первообразный_корень первообразный корень)) $ \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 $. Запустим ((:numtheory#алгоритм_евклида алгоритм Евклида)) поиска этого $ \operatorname{HOD} $ и остановим его как только получившийся остаток станет меньше $ \sqrt{p} $: $$ \begin{array}{lcl} p&=&r_0q_1+r_1 \ , \quad \sqrt{p} 3. Утверждается, что число $ b=\sqrt{p-r_k^2} $ --- натуральное, и, тем самым, числа $ a=r_k $ и $ b $ представляют решение задачи. Для доказательства обратимся к пункту ((:numtheory#линейное_представление_нод Линейное представление 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 $. ♦