Сравнение по простому модулю

[xmaister]

Нужно доказать, что $\prod\limits_{i=1}^{p}(i^2+1)\equiv 4\pmod p$, если $p$- простое вида $4n-1$.

(Оффтоп)

Методом грубой силы $\prod\limits_{k=1}^{p-1}(k^2+1)=\prod\limits_{k=1}^{p-1}(k+i)\prod\limits_{k=1}^{p-1}(k-i)$. Дальше поэксплуатировав свойства делимость на $p$ чисел Стирлинга и теорему Вильсона, получаем что требуется.

Собтвенно, интересно алгебраическое доказательство. Из каких свойств группы $(\mathbb{Z}/p\mathbb{Z})^{\times}$ это может следовать. Я пробовал прикрутить цикличность и то, что мощность множества чисел вида $k^2+1$- половина мощности $(\mathbb{Z}/p\mathbb{Z})^{\times}$. Но описать числа в таком виде не представимые явно не получилось. Можно ли как-то найти число решений сравнения $x^2-y^2-1\equiv 0\pmod p$?

[Sonic86]

xmaister в сообщении #695600 писал(а):

Можно ли как-то найти число решений сравнения $x^2-y^2-1\equiv 0\pmod p$?

Можно. Довольно общий метод на основе характеров смотрите в Айрленде Роузене Классическое введение в современную теорию чисел. Сейчас могу наврать, но здесь число решений будет что-то типа $p\pm 1$.

(Решается примерно так)

если $\left(\frac{a}{p}\right)$ - символ Лежандра, то число решений $N(t^2\equiv a\pmod p)=1+\left(\frac{a}{p}\right)$. Тогда $N(x^2\equiv y^2+1\pmod p)=\sum\limits_{a=b+1}\left(1+\left(\frac{a}{p}\right)\right)\left(1+\left(\frac{a}{p}\right)\right)=\sum\limits_{a=b+1}1+\left(\frac{a}{p}\right)+\left(\frac{a}{p}\right)+\left(\frac{ab}{p}\right)=p+0+0+\sum\limits_{a=b+1}\left(\frac{ab^{-1}}{p}\right)=p+\sum\limits_{b}\left(\frac{1+b^{-1}}{p}\right)=p+0-\left(\frac{1}{p}\right)=p-1$

xmaister в сообщении #695600 писал(а):

Методом грубой силы $\prod\limits_{k=1}^{p-1}(k^2+1)=\prod\limits_{k=1}^{p-1}(k+i)\prod\limits_{k=1}^{p-1}(k-i)$. Дальше поэксплуатировав свойства делимость на $p$ чисел стирлинга и теорему Вильсона, получаем что требуется.

xmaister в сообщении #695600 писал(а):

Собтвенно, интересно алгебраическое доказательство.

Я думаю, что то, что написано в оффтопе, вполне алгебраическое доказательство.

Sonic86 в сообщении #695643 писал(а):

Я пробовал прикрутить цикличность и то, что мощность множества чисел вида $k^2+1$- половина мощности $(\mathbb{Z}/p\mathbb{Z})^{\times}$.

Так?: $\prod\limits_{k=1}^{p-1}(k^2+1)=\prod\limits_{k=1}^{p-1}(g^{2k}+1)=\left|Q:=(\mathbb{Z}_p^{\times})^2\right|=\sum\limits_{k=0}^{p-1}\sigma_k(Q)=1+\sigma_{\frac{p-1}{2}}(Q)+\sigma_{p-1}(Q)=1+((p-1)!)^2+\sigma_{\frac{p-1}{2}}(Q)=2+\sigma_{\frac{p-1}{2}}(Q)$. Дальше идет какая-то жесть с биномиальными коэффициентами (но при желании можно и досчитать).

[nnosipov]

Эту задачу естественно решать в рамках теории многочленов. Имеем $x^{p-1}-1=\prod\limits_{k \in \mathbb{F}_p^*} (x-k)$ (разложение над полем $\mathbb{F}_p$). Подставить сюда $x=\pm i$, где $i$ --- корень неприводимого над $\mathbb{F}_p$ многочлена $x^2+1$, и потом перемножить. Теорема Вильсона, числа Стирлинга не нужны.

[Коровьев]

xmaister в сообщении #695600 писал(а):

Можно ли как-то найти число решений сравнения $x^2-y^2-1\equiv 0\pmod p$?

Проще воспользоваться тождеством

$$\[ 0 = \left( {\frac{{k^2 + 1}}{{2k}}} \right)^2 - \left( {\frac{{k^2 - 1}}{{2k}}} \right)^2 - 1 \equiv \left( {2k} \right)^{2P - 4} \left( {k^2 + 1} \right)^2 - \left( {2k} \right)^{2P - 4} \left( {k^2 - 1} \right)^2 - 1(\bmod P) \]$$

[nnosipov]

Действительно, кривая-то рациональна.

[xmaister]

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

Эту задачу естественно решать в рамках теории многочленов. Имеем $x^{p-1}-1=\prod\limits_{k \in \mathbb{F}_p^*} (x-k)$ (разложение над полем $\mathbb{F}_p$). Подставить сюда $x=\pm i$, где $i$ --- корень неприводимого над $\mathbb{F}_p$ многочлена $x^2+1$, и потом перемножить. Теорема Вильсона, числа Стирлинга не нужны.

Да, действительно. Но я как-то забыл про то что $x^{p-1}-1\equiv (x-1)\ldots (x-(p-1))\pmod p$

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

Действительно, кривая-то рациональна.

И что? В смысле допускает рациональную параметризацию? Ну а что это дает в общем случае для произвольной рациональной кривой?

-- 14.03.2013, 21:50 --

Sonic86 в сообщении #695643 писал(а):

Довольно общий метод на основе характеров смотрите в Айрленде Роузене Классическое введение в современную теорию чисел.

Спасибо!

[nnosipov]

xmaister в сообщении #695718 писал(а):

И что? В смысле допускает рациональную параметризацию? Ну а что это дает в общем случае для произвольной рациональной кривой?

Я имел в виду кривые второго порядка. В общем случае --- не знаю.

Как определить число решений сравнения по модулю, можно посмотреть ещё в небольшой книжке Степанова "Сравнения по модулю" (М., 1975). Автор говорит о "чисто арифметическом подходе".