C Простым числом p

[CrabReiter]

Доказать, что для всякого простого $p$ можно найти целые числа $x$, $y$, что $x^2+y^2+1$ делится на $p$.
Условие задачи дано именно такое. Попытался это как-то доказать, но у меня не вышло, хотя вроде ничего сложного тут нет. Может, условие корявое? Заранее спасибо!

[nnosipov]

CrabReiter в сообщении #531607 писал(а):

Может, условие корявое?

Нет, с условием всё в порядке. Это утверждение хорошо известно, оно используется при доказательстве теоремы Лагранжа о четырёх квадратах. Прочитать об этом можно, например, в книжке Спивак А.В. Арифметика-2. М.: Бюро Квантум, 2008.

[Sonic86]

Легко доказать, что $(\exists x) 0\leqslant x < p, p|x^2+1 \vee p|x^2+2$.

[CrabReiter]

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

CrabReiter в сообщении #531607 писал(а):

Может, условие корявое?

Нет, с условием всё в порядке. Это утверждение хорошо известно, оно используется при доказательстве теоремы Лагранжа о четырёх квадратах. Прочитать об этом можно, например, в книжке Спивак А.В. Арифметика-2. М.: Бюро Квантум, 2008.

Нашёл, прочитал, разобрался. Спасибо Большое!

[Dave]

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

Легко доказать, что $(\exists x) 0\leqslant x < p, p|x^2+1 \vee p|x^2+2$.

Не понял. А если $p=7$? Или $x$ подразумевается не обязательно целым?

[MrDindows]

А такие рассуждения верны? :
По простому модулю $p$ мы имеем $\frac{p+1}{2}$ квадратичных вычетов и $\frac{p-1}{2}$ пар остатков $(r_i, \ p-r_i-1)$ а также число $\frac{p-1}{2}$, которое есть парой само себе, и каждая эта пара удовлетворяет условию задачи. А по принципу Дирихле мы имеем, что, как минимум, либо какая-то пара остатков является вычетами, либо число $\frac{p-1}{2}$, что и требовалось доказать)

[nnosipov]

MrDindows в сообщении #531790 писал(а):

А такие рассуждения верны? :
По простому модулю $p$ мы имеем $\frac{p+1}{2}$ квадратичных вычетов и $\frac{p-1}{2}$ пар остатков $(r_i, \ p-r_i-1)$ а также число $\frac{p-1}{2}$, которое есть парой само себе, и каждая эта пара удовлетворяет условию задачи. А по принципу Дирихле мы имеем, что, как минимум, либо какая-то пара остатков является вычетами, либо число $\frac{p-1}{2}$, что и требовалось доказать)

Сформулировано не совсем удачно, но по сути верно. Можно рассуждать от противного: пусть $x^2 \not\equiv -1-y^2 \pmod{p}$ для любых $x$ и $y$. Тогда набор $R$ квадратичных вычетов и его образ при отображении $\varphi:z \mapsto -1-z$ не пересеклись бы, что невозможно, ибо $|R|+|\varphi(R)|=p+1>p$.

[Sonic86]

Dave в сообщении #531768 писал(а):

Sonic86 писал(а):

Легко доказать, что $(\exists x) 0\leqslant x < p, p|x^2+1 \vee p|x^2+2$.

Не понял. А если $p=7$? Или $x$ подразумевается не обязательно целым?

Я глупость написал. Это я хотел решение про $\frac{p+1}{2}$ значений написать и его не додумал

[Sonic86]

Для полноты картины можно также сказать, что число решений $N(x^2+y^2+1\equiv 0 \pmod p)=p+(-1)^{\frac{p+1}{2}}$.