2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 Сравнение по простому модулю
Сообщение14.03.2013, 17:40 
Аватара пользователя
Нужно доказать, что $\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$?

 
 
 
 Re: Сравнение по простому модулю
Сообщение14.03.2013, 18:45 
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)$. Дальше идет какая-то жесть с биномиальными коэффициентами (но при желании можно и досчитать).

 
 
 
 Re: Сравнение по простому модулю
Сообщение14.03.2013, 19:20 
Эту задачу естественно решать в рамках теории многочленов. Имеем $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$, и потом перемножить. Теорема Вильсона, числа Стирлинга не нужны.

 
 
 
 Re: Сравнение по простому модулю
Сообщение14.03.2013, 20:28 
Аватара пользователя
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)
\]$$

 
 
 
 Re: Сравнение по простому модулю
Сообщение14.03.2013, 20:34 
Действительно, кривая-то рациональна.

 
 
 
 Re: Сравнение по простому модулю
Сообщение14.03.2013, 20:46 
Аватара пользователя
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 писал(а):
Довольно общий метод на основе характеров смотрите в Айрленде Роузене Классическое введение в современную теорию чисел.

Спасибо!

 
 
 
 Re: Сравнение по простому модулю
Сообщение14.03.2013, 21:02 
xmaister в сообщении #695718 писал(а):
И что? В смысле допускает рациональную параметризацию? Ну а что это дает в общем случае для произвольной рациональной кривой?
Я имел в виду кривые второго порядка. В общем случае --- не знаю.

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

 
 
 [ Сообщений: 7 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group