Формула разложения простого P=4n+1 на сумму двух квадратов

[Коровьев]

1.
Методика вывода формулы аналогична методике в теме
Представление простого P=3n+1 формой P=A^2-AB+B^2
Вывод даю схематично.

Пусть простое $$P \equiv 1\left( {\bmod 4} \right), g $ - его первообразный корень. $$\omega = e^{\frac{{2\pi i}}{P}}$

Обозначим

$$ \varsigma _{\left( m \right)} = \sum\limits_{k = 1}^{\frac{{P - 1}}{4}} {\omega ^{g^{4k + m} } } $

$$ \eta _{\left( 0 \right)} = \left( {\varsigma _{\left( 0 \right)} - \varsigma _{\left( 2 \right)} } \right) + \left( {\varsigma _{\left( 1 \right)} - \varsigma _{\left( 3 \right)} } \right)i $
Тогда
$$ \eta _{\left( m \right)} = \left( {\varsigma _{\left( m \right)} - \varsigma _{\left( m+1 \right)} } \right) + \left( {\varsigma _{\left( m+2 \right)} - \varsigma _{\left( m+3 \right)} } \right)i = i^m \eta _{\left( 0 \right)} $

$$ \left\{ \begin{array}{l} P = 8k + 1 \to \bar \varsigma _{\left( m \right)} = \varsigma _{\left( m \right)} \\ P = 8k + 5 \to \bar \varsigma _{\left( m \right)} = \varsigma _{\left( {m + 2} \right)} \\ \end{array} \right. $

$$ \left\{ \begin{array}{l} \bar \eta _{\left( 0 \right)} = \left( {\varsigma _{\left( 0 \right)} - \varsigma _{\left( 2 \right)} } \right) - \left( {\varsigma _{\left( 1 \right)} - \varsigma _{\left( 3 \right)} } \right)i \to P = 8k + 1 \\ \bar \eta _{\left( 0 \right)} = - \left( {\left( {\varsigma _{\left( 0 \right)} - \varsigma _{\left( 2 \right)} } \right) - \left( {\varsigma _{\left( 1 \right)} - \varsigma _{\left( 3 \right)} } \right)i} \right) \to P = 8k + 5 \\ \end{array} \right. $

Из $\[\eta _{\left( m \right)} ^4 = \eta _{\left( 0 \right)} ^4 \] $, следует, что все изоморфизмы $\[\eta _{\left( m \right)} ^4\] $ по $\omega $ равны. Значит
$$ \eta _{\left( 0 \right)} ^4 = c\left( {a + bi} \right) \to \left( {a,b} \right) = 1 $

Далее
$$ \lambda = \left( {\bar \varsigma _{\left( 1 \right)} - \bar \varsigma _{\left( 3 \right)} } \right)\left( {\varsigma _{\left( 0 \right)} - \varsigma _{\left( 2 \right)} } \right) - \left( {\bar \varsigma _{\left( 0 \right)} - \bar \varsigma _{\left( 2 \right)} } \right)\left( {\varsigma _{\left( 1 \right)} - \varsigma _{\left( 3 \right)} } \right) = 0 $

$$ \eta _{\left( 0 \right)} \bar \eta _{\left( 0 \right)} = \left( {\sum\limits_0^3 {\varsigma _{\left( k \right)} \bar \varsigma _{\left( k \right)} } } \right) - \left( {\sum\limits_0^3 {\varsigma _{\left( k \right)} \bar \varsigma _{\left( {k + 2} \right)} } } \right) + \lambda = \left( {\frac{{3P + 1}}{4}} \right) - \left( { - \frac{{P - 1}}{4}} \right) = P $

$$ \left( {\eta _{\left( 0 \right)} \bar \eta _{\left( 0 \right)} } \right)^4 = c^2 \left( {a^2 + b^2 } \right) = P^4 \to c = P $
(Доказательство опускаю.) Значит
$$a^2 + b^2 = P^2 $

Из однозначности разложения для чисел Гаусса следует
$$ a + bi = \left( {m + in} \right)^2 \to m^2 + n^2 = P $

Т.о.
$$ \eta _{\left( 0 \right)} ^4 = P\left( {m + in} \right)^2 \to \eta _{\left( 0 \right)} ^2 = \sqrt P \left( {m + in} \right) $
Возможный знак минус перед выражением можно "спрятать" в полученное Гауссово число.

Окончательно получим
$$ m = \frac{{\eta _{\left( 0 \right)} ^2 + \bar \eta _{\left( 0 \right)} ^2 }}{{2\sqrt P }} = \frac{{\left( {\varsigma _{\left( 0 \right)} - \varsigma _{\left( 2 \right)} } \right)^2 - \left( {\varsigma _{\left( 1 \right)} - \varsigma _{\left( 3 \right)} } \right)^2 }}{{\sqrt P }} $

$$ n = \frac{{\eta _{\left( 0 \right)} ^2 - \bar \eta _{\left( 0 \right)} ^2 }}{{2i\sqrt P }} = 2\frac{{\left( {\varsigma _{\left( 0 \right)} - \varsigma _{\left( 2 \right)} } \right)\left( {\varsigma _{\left( 1 \right)} - \varsigma _{\left( 3 \right)} } \right)}}{{\sqrt P }} $

$$ P = m^2 + n^2 $
Причём $n$ чётное

[Коровьев]

2.
Пример
$\[ P = 13,g = 2 \to \omega = e^{\frac{{2\pi i}}{P}} \] $

$\[ \left\{ \begin{array}{l} \varsigma _{\left( 0 \right)} = \omega ^1 + \omega ^3 + \omega ^9 \\ \varsigma _{\left( 1 \right)} = \omega ^2 + \omega ^6 + \omega ^5 \\ \varsigma _{\left( 2 \right)} = \omega ^4 + \omega ^{12} + \omega ^{10} \\ \varsigma _{\left( 3 \right)} = \omega ^8 + \omega ^{11} + \omega ^7 \\ \end{array} \right. \] $

$\[ \left\{ \begin{array}{l} \eta _{\left( 0 \right)} = \left( {\varsigma _{\left( 0 \right)} - \varsigma _{\left( 2 \right)} } \right) + \left( {\varsigma _{\left( 1 \right)} - \varsigma _{\left( 3 \right)} } \right)i \\ \bar \eta _{\left( 0 \right)} = - \left( {\varsigma _{\left( 0 \right)} - \varsigma _{\left( 2 \right)} } \right) + \left( {\varsigma _{\left( 1 \right)} - \varsigma _{\left( 3 \right)} } \right)i \\ \end{array} \right. \] $

$\[ \left[ {\left( {\varsigma _{\left( 0 \right)} + \varsigma _{\left( 2 \right)} } \right) - \left( {\varsigma _{\left( 1 \right)} - \varsigma _{\left( 3 \right)} } \right)} \right]^2 = 13 \] $

$\[ \left\{ \begin{array}{l} \eta _{\left( 0 \right)} ^2 = \left( {3 - 2i} \right)\left[ {\left( {\varsigma _{\left( 0 \right)} + \varsigma _{\left( 2 \right)} } \right) - \left( {\varsigma _{\left( 1 \right)} - \varsigma _{\left( 3 \right)} } \right)} \right] = \left( {3 - 2i} \right)\sqrt {13} \\ \bar \eta _{\left( 0 \right)} ^2 = \left( {3 + 2i} \right)\left[ {\left( {\varsigma _{\left( 0 \right)} + \varsigma _{\left( 2 \right)} } \right) - \left( {\varsigma _{\left( 1 \right)} - \varsigma _{\left( 3 \right)} } \right)} \right] = \left( {3 + 2i} \right)\sqrt {13} \\ \end{array} \right. \] $

$\[ \left\{ \begin{array}{l} m = \frac{{\eta _{\left( 0 \right)} ^2 + \bar \eta _{\left( 0 \right)} ^2 }}{{2\sqrt {13} }} = 3 \\ n = \frac{{\eta _{\left( 0 \right)} ^2 - \bar \eta _{\left( 0 \right)} ^2 }}{{2i\sqrt {13} }} = - 2 \\ \end{array} \right. \] $

$\[ m^2 + n^2 = 13 \] $

[vicvolf]

А как у Вас получаются остальные решения: $(3,2), (-3,2), (-3,-2)$ и симметричные 4 решения?

[Коровьев]

vicvolf в сообщении #878583 писал(а):

А как у Вас получаются остальные решения: $(3,2), (-3,2), (-3,-2)$ и симметричные 4 решения?

Цифровое воплощение результата не зависит от знака $m,n$ и перестановки слагаемых.
Разные же знаки $m,n$ зависят от выбора первообразного корня для данного простого числа, а какое слагаемое стоит на первом месте зависит от личного предпочтения. Но следует учесть, что получаемое по приведённой формуле $n$ всегда чётно.

3.
Я остановлюсь на кратком анализе полученных формул. Сначала для $m$.
Так как для простых $P=4k+1$

$$ P = \prod\limits_{k = 1}^{\frac{{P - 1}}{2}} {\left( {1 - \omega ^k } \right)^2 } \to \sqrt P = \prod\limits_{k = 1}^{\frac{{P - 1}}{2}} {\left( {1 - \omega ^k } \right)} $

то, разложив правую часть на множители, получим
$$ m\prod\limits_{k = 1}^{\frac{{P - 1}}{2}} {\left( {1 - \omega ^k } \right)} = \left( {\varsigma _{\left( 0 \right)} - \varsigma _{\left( 2 \right)} + \varsigma _{\left( 1 \right)} - \varsigma _{\left( 3 \right)} } \right)\left( {\varsigma _{\left( 0 \right)} - \varsigma _{\left( 2 \right)} - \varsigma _{\left( 1 \right)} + \varsigma _{\left( 3 \right)} } \right) $

$m$ - целое рациональное число. Остальные множители - целые приведённые алгебраические числа кольца $\mathbb{R}$$(\omega)$ с коэффициентами при $\omega = \pm 1$, свободным членом равным нулю и, следовательно, не имеют целых рациональных делителей (теория чисел).

$${\left( {1 - \omega ^k } \right)}$ - простое алгебраическое число. Оно уникально тем, что вне зависимости от однозначности или неоднозначности разложения на простые множители в данном кольце делится либо на первый, либо на второй множитель правый части.
Т.о. получим
$$m = \varphi _1 \left( \omega \right)\varphi _2 \left( \omega \right)$ - т.е. равно произведению двух целых алгебраических чисел данного кольца.
Это справедливо и для $n/2$.
Далее. Все эти рациональные делители можно описать, зная все подполя поля от $\omega $. Или попытаться решить обратную задачу - для каких простых чисел приведённые формулы могут дать определённое значение $m_0$ или $n_0$.

В сообщениях post130408.html#p130408 и post130803.html#p130803 я элементарно показал, что что существует бесконечное множество таких целых рациональных $m_0 $, что последовательность ${m_0}^2+x^2 $ содержит бесконечно много простых чисел.
Поэтому поставленная выше "обратная задача" возможно даст некий подход к проблеме бесконечности простых чисел в последовательности ${m_0}^2+x^2 $

[nnosipov]

Коровьев в сообщении #879155 писал(а):

В сообщениях post130408.html#p130408 и post130803.html#p130803 я элементарно показал, что что существует бесконечное множество таких целых рациональных $m_0 $, что последовательность ${m_0}^2+x^2 $ содержит бесконечно много простых чисел.

Что-то я не понимаю этого доказательства. Почему после вычеркивания бесконечных строк получится матрица с конечным числом столбцов? Ведь длины конечных строк не обязаны быть равномерно ограничены. А если обязаны, то по какой причине?

[Коровьев]

nnosipov в сообщении #879215 писал(а):

Ведь длины конечных строк не обязаны быть равномерно ограничены. А если обязаны, то по какой причине?

А этого и не требуется. В последнем столбце, (а он обязан быть, раз вычеркнуты все бесконечные строки) может быть даже один или несколько элементов и, естественно, величина суммы его членов тоже конечна и меньше $\frac{{\pi ^2 }}{6}$

[nnosipov]

Коровьев в сообщении #879311 писал(а):

В последнем столбце, (а он обязан быть, раз вычеркнуты все бесконечные строки)

С чего вдруг последний столбец обязан быть? Представьте себе бесконечную нижнетреугольную матрицу, где у неё последний столбец?

[Коровьев]

nnosipov в сообщении #879353 писал(а):

С чего вдруг последний столбец обязан быть? Представьте себе бесконечную нижнетреугольную матрицу, где у неё последний столбец?

Всё верно, гнилое доказательство. С бесконечностью аккуратно надо. Ну да бог с ним.

4.
Продолжу.
$P \equiv 1\left( {\bmod 4} \right)$, g - первообразный корень.
Достаточно известно (особенно в криптографии) разложение простого числа на сумму двух квадратов с применением символа Лежандра
$$ P = \left[ {\frac{1}{2}\sum\limits_{x = 0}^{P - 1} {\left( {\frac{{x^3 + mx}}{P}} \right)} } \right]^2 + \left[ {\frac{1}{2}\sum\limits_{x = 0}^{P - 1} {\left( {\frac{{x^3 + nx}}{P}} \right)} } \right]^2 $

где $m$ - квадратичный вычет, а $n$ - квадратичный невычет по модулю $P$
Причём, второй квадрат чётное число.
Сравнивая с выведенными выше формулами и учитывая, что представление простого числа на сумму двух квадратов с точностью до перестановки квадратов единственно, можно записать

$$ \left| {\frac{1}{2}\sum\limits_{x = 0}^{P - 1} {\left( {\frac{{x^3 + mx}}{P}} \right)} } \right| = \left| {\frac{{\left( {\varsigma _{\left( 0 \right)} - \varsigma _{\left( 2 \right)} } \right)^2 - \left( {\varsigma _{\left( 1 \right)} - \varsigma _{\left( 3 \right)} } \right)^2 }}{{\sqrt P }}} \right| $

$$ \left| {\frac{1}{2}\sum\limits_{x = 0}^{P - 1} {\left( {\frac{{x^3 + nx}}{P}} \right)} } \right| = \left| {2\frac{{\left( {\varsigma _{\left( 0 \right)} - \varsigma _{\left( 2 \right)} } \right)\left( {\varsigma _{\left( 1 \right)} - \varsigma _{\left( 3 \right)} } \right)}}{{\sqrt P }}} \right| $
где
$$ \varsigma _{\left( m \right)} = \sum\limits_{k = 1}^{\frac{{P - 1}}{4}} {\left( {e^{\frac{{2\pi i}}{P}} } \right)^{g^{4k + m} } } $

Далее.
Рассмотрим уравнение
$$y^2 \equiv a\left( {\bmod P} \right)$

Используя символ Лежандра число его решений можно записать так

$$N = 1 + \left( {\frac{a}{P}} \right)$

А число решений по модулю $P$ эллиптического уравнения
$$y^2 \equiv x^3 + ax\left( {\bmod P} \right)$
равно
$$ N = P + \sum\limits_{x = 0}^{P - 1} {\left( {\frac{{x^3 + ax}}{P}} \right)} $
Иными словами, получено явное выражение для числа точек на данной эллиптической кривой по простому модулю $P \equiv 1\left( {\bmod 4} \right)$

$$ N = 1 + P - \left| {2\frac{{\left( {\varsigma _{\left( 0 \right)} - \varsigma _{\left( 2 \right)} } \right)^2 - \left( {\varsigma _{\left( 1 \right)} - \varsigma _{\left( 3 \right)} } \right)^2 }}{{\sqrt P }}} \right| $

$$ N = 1 + P - \left| {4\frac{{\left( {\varsigma _{\left( 0 \right)} - \varsigma _{\left( 2 \right)} } \right)\left( {\varsigma _{\left( 1 \right)} - \varsigma _{\left( 3 \right)} } \right)}}{{\sqrt P }}} \right| $

где в зависимости от $a$ вычет/не вычет надо в квадратных скобках выбирать первое или второе выражение.
Единица добавлена как спец.точка (аналог бесконечно удалённой точки)

[nnosipov]

Вот здесь http://www.ega-math.narod.ru/Books/Ireland.djv задача о представлении простого $p \equiv 1 \pmod{4}$ в виде $p=a^2+b^2$ и простого $p \equiv 1 \pmod{3}$ в виде $p=a^2-ab+b^2$ решается с помощью сумм Якоби $J(\chi,\chi)$ для биквадратичного и кубического характера $\chi$ соответственно (см. предложение 8.3.1). Связь между суммами Якоби и Гаусса см. в теореме 1, п. (d), а также в предложении 8.3.3. Например, для $p \equiv 1 \pmod{4}$ имеем

$$ J(\chi,\chi)=a+bi=\frac{g(\chi)^2}{g(\chi^2)}=\frac{g(\chi)^2}{\sqrt{p}}, $$

где $\chi$ --- биквадратичный характер (поскольку $\chi^2$ --- квадратичный характер, т.е. символ Лежандра, так что $g(\chi^2)=\sqrt{p}$).

Коровьев в сообщении #879508 писал(а):

Достаточно известно (особенно в криптографии) разложение простого числа на сумму двух квадратов с применением символа Лежандра
$$P = \left[ {\frac{1}{2}\sum\limits_{x = 0}^{P - 1} {\left( {\frac{{x^3 + mx}}{P}} \right)} } \right]^2 + \left[ {\frac{1}{2}\sum\limits_{x = 0}^{P - 1} {\left( {\frac{{x^3 + nx}}{P}} \right)} } \right]^2$
где $m$ - квадратичный вычет, а $n$ - квадратичный невычет по модулю $P$

Формула Якобшталя, судя по "Высшей арифметике" Дэвенпорта.

[dmd]

На Хабре была статья в тему.