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


§

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


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

Т

Теорема [Вильсон]. Для того чтобы число $ 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} \ \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)! \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 $.

modular/wilson.txt · Последние изменения: 2020/04/26 01:04 — au