Задача про p=8k+3=a^2+bc

[rightways]

Пусть простое $p>3$ и $8|p-3$. Докажите, что $p=a^2+bc$ для некоторых натуральных $a,b,c<\sqrt{p}$.

[maxal]

Возьмите нечётное $a\in\left\{[\sqrt p], [\sqrt p]-1\right\}$ и $b=4$.

[nnosipov]

maxal в сообщении #1441477 писал(а):

Возьмите нечётное $a\in\left\{[\sqrt p], [\sqrt p]-1\right\}$ и $b=4$.

Неужели получается? Честно говоря, я поленился это проверить. Мне этот путь почему-то показался безнадежным, после неуспеха с $b=2$.

При $b=c$ тоже забавно получается. Вообще, какая-то вирусная задача.

Upd. При $c=2b$, конечно.

[maxal]

Почему-то вместо минуса увидел плюс (т.е. $p\equiv 5\pmod 8$).
Для $p\equiv 3\pmod 8$, та же идея работает если $[\sqrt p]$ нечётно, когда можно взять $a=[\sqrt p]$ и $b=2$.

-- Tue Feb 25, 2020 10:01:48 --

А вообще можно положить $c=2b$ и представить $p=a^2+2b^2$. Такое представление у $p\equiv 3\pmod{8}$ есть.

[nnosipov]

maxal в сообщении #1441489 писал(а):

и представить $p=a^2+2b^2$. Такое представление у $p\equiv 3\pmod{8}$ есть.

А если, например, $a=3$ и $b$ --- нечётное простое? Тогда все плохо, ибо $2b>\sqrt{p}$. Я это и имел в виду, когда писал, что ситуация забавная.

[Руст]

Для таких p выполняется

$$(\frac{-2}{p})=1 \to p=x^2+2y^2=(x+y)^2+y(y-2x)=(2y-x)^2+2y(2x-y).$$

Если $y<\sqrt p /2$, то

$$a=x, b=2y,c=y.$$

Если $\sqrt p /2 <y<2x$, то

$$a=2y-x, b=y, c=2(2x-y).$$

Если $y>2x$, то

$$a=x+y, b=y, c=y-2x.$$

Ясно, что $p=11\mod 24$ или $p=19\mod 24$.
В последнем случае можно использовать метод maxal. Пусть $k=[\sqrt p]$.
Возьмем в качестве $a$ , одно из чисел $k-2,k-1,k$.
Если $k$ не делится на 3, то $p=k^2+3c, c=\frac{p-k^2}{3}<\sqrt p$.
Иначе берем нечетное из $k-2,k-1$ и $b=6$.

[nnosipov]

Руст в сообщении #1464261 писал(а):

Если $\sqrt p /2 <y<2x$, то

$$a=2y-x, b=y, c=2(2x-y).$$

Если $y \approx 0.5\sqrt{p}$, то $x \approx 0.7\sqrt{p}$ и $c \approx 1.8\sqrt{p}$ --- перебор. Короче говоря, под вопросом значения $y$, для которых $\sqrt{p}/2<y<2\sqrt{p}/3$.

[Руст]

Да, я это упустил. Мне кажется проще доказать, что любое натуральное число $n$ за конечным числом исключений
представляется в виде $n=a^2+bc, \ a,b,c\in N, \ a,b,c<\sqrt n$.
Пусть $k=[\sqrt{n-1}]$. Случай $a=k$ решает задачу, если $q=n-k^2$ не простое число большее $k$.
Случаи $q=k+1, 2k+1$ исключаются при $n>16$ за счет выбора $a=k-1$. Таким образом при $n>16$ остается рассмотреть $n=k^2+q, k+1<q<2k, q\in P$.
Если $n%4=0,1$ за счет выбора $a=k,k-1$ при $n>16$ добиваемся того, что $n=a^2+4c, c<\sqrt n$.
Среди $n\le 100$ не представимыми так являются только числа $n=1,3,4,7,9,14,16,23,47,62.$.
Пусть $n=a^2+bc$ решение и $p|bc$ нечетное простое число. Тогда $(\frac{n}{p})=1$. Пусть $l=\sqrt n \mod p, l<p/2$.
Число $n-a^2$ делится на $p$. Соответственно, $a=ps+\pm l$. За счет большего значения $a<\sqrt n$ можем улучшить решение уменьшая остаток $bc$.
Когда число $n$ достаточно большое можно найти $b=\prod p_i<\sqrt n, \ (\frac{n}{p_i})=1, i=1,...,l$, так что из $2^l$ квадратных корней от $n$ по модулю $b$
в интервале $k-b+1\le a\le k$ найдется такой, что $\frac{n-a^2}{b}=c<\sqrt n$.

[nnosipov]

Руст в сообщении #1464384 писал(а):

Мне кажется проще доказать, что любое натуральное число $n$ за конечным числом исключений
представляется в виде $n=a^2+bc, \ a,b,c\in N, \ a,b,c<\sqrt n$.

Да, это интересно. К сожалению, сейчас нет времени внимательно прочитать Ваш текст.

Вообще, сама постановка задачи кажется мне выморочной: стоит увеличить границу всего лишь в 2 раза (и то лишь для одного $c$) --- и все становится очевидным. Тут нужен хороший стимул, чтобы так надрываться.

[Руст]

Достаточно доказать, что при достаточно большом n существует простое число $p: (\frac{n}{p})=1, \ 2p<\sqrt n$.

[Руст]

Для чисел $n$ представимых в виде $n=x^2+2y^2$ нашел еще одно представление $n=(3y-x)^2+y(6x-7y)$.
Отсюда получается справедливость при $y<\frac{6}{11}\sqrt n$. Остается интервал $\frac{6}{11}\sqrt n<y<\frac{2}{3}\sqrt n$.
Здесь иногда можно делитель второго множителя можно передать к $y$, а от $y$ перебросить несколько меньший множитель ко второму.
Но это не всегда удается.

[waxtep]

Пара наблюдений:
1. Простота $p$ видимо существенна (или может быть лишь отсутствие делимости на $3$ ?); для составных чисел минимальное вида $8k+3$ и непредставимое в требуемом виде - это $75$;
2. Для некоторых $p$ максимальное $a$ лежит довольно далеко от $a_0=\left\lfloor\sqrt p\right\rfloor$, например $947=25^2+14\cdot23$;
3. Я пытался порешать задачу в лоб, рассматривая $p=a_0^2+d$, все хорошо (существует такое $a$, что $b\leqslant4,c\leqslant a_0$), кроме случаев, когда $d$ дает $7$ или $11$ по модулю $12$, что с ними делать непонятно

[Руст]

Простота существенно не помогает. Я воспринял это как намек на квадратичное представление.
Из расширенной гипотезы Римана получено, что минимальный квадратичный не вычет по модулю $p$ не превосходит $2\ln^2p$.
Аналогично можно доказать, что минимальное простое $p$, такое что $(\frac np)=1$ не превосходит $C\ln^2 n$. Для достаточно большого $n$
$C\ln^2 n<\sqrt n /2$. Так можно доказать, что за конечным исключением это свойство выполняется для любого $n$.
Думаю, что ограничение сверху для исключительных порядка 1000000 (думаю можно строго доказать, что больше миллиона нет исключительных $n$.

[waxtep]

Руст в сообщении #1464473 писал(а):

Я воспринял это как намек на квадратичное представление

Но все таки, представимости $p$ в виде $x^2+2y^2$ самой по себе ведь недостаточно, вот то же $75=5^2+2\cdot5^2$ не может быть представлено в требуемом виде

[Руст]

Да. Но когда n простое, числа x,y взаимно простые и одно из них делится на 3.

Всего получилось 17 исключений:
1, 3, 4, 7, 9, 14, 16, 23, 47, 62, 75, 138, 167, 215, 318, 398, 482. Для всех остальных чисел $n=a^2+bc, \ a,b,c\in N, \ a,b,c<\sqrt n$.

Когда $n\le 150 000 000$ максимальное отклонение максимального значения $a$ от
$[\sqrt n]$ равно 24, достигается при n=2566038, a=1577.
При $150 000 000<n<2^{32}$ считал по более быстрой программе и нашел максимальное значение
минимального $p: \ (\frac{n}{p})=1$.
При $n= 3 205 013 118, p=139$. Так что оценка для такого p типа $p<2\ln^2 n$ даже несколько завышена.