2014 dxdy logo

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

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




Начать новую тему Ответить на тему На страницу 1, 2  След.
 
 Задача про p=8k+3=a^2+bc
Сообщение19.02.2020, 11:56 


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

 Профиль  
                  
 
 Re: Задача про p=8k+3=a^2+bc
Сообщение25.02.2020, 17:20 
Модератор
Аватара пользователя


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

 Профиль  
                  
 
 Re: Задача про p=8k+3=a^2+bc
Сообщение25.02.2020, 17:30 
Заслуженный участник


20/12/10
8858
maxal в сообщении #1441477 писал(а):
Возьмите нечётное $a\in\left\{[\sqrt p], [\sqrt p]-1\right\}$ и $b=4$.
Неужели получается? Честно говоря, я поленился это проверить. Мне этот путь почему-то показался безнадежным, после неуспеха с $b=2$.

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

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

 Профиль  
                  
 
 Re: Задача про p=8k+3=a^2+bc
Сообщение25.02.2020, 17:51 
Модератор
Аватара пользователя


11/01/06
5660
Почему-то вместо минуса увидел плюс (т.е. $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}$ есть.

 Профиль  
                  
 
 Re: Задача про p=8k+3=a^2+bc
Сообщение25.02.2020, 20:18 
Заслуженный участник


20/12/10
8858
maxal в сообщении #1441489 писал(а):
и представить $p=a^2+2b^2$. Такое представление у $p\equiv 3\pmod{8}$ есть.
А если, например, $a=3$ и $b$ --- нечётное простое? Тогда все плохо, ибо $2b>\sqrt{p}$. Я это и имел в виду, когда писал, что ситуация забавная.

 Профиль  
                  
 
 Re: Задача про p=8k+3=a^2+bc
Сообщение21.05.2020, 01:05 
Заслуженный участник


09/02/06
4382
Москва
Для таких 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$.

 Профиль  
                  
 
 Re: Задача про p=8k+3=a^2+bc
Сообщение21.05.2020, 10:34 
Заслуженный участник


20/12/10
8858
Руст в сообщении #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$.

 Профиль  
                  
 
 Re: Задача про p=8k+3=a^2+bc
Сообщение21.05.2020, 16:02 
Заслуженный участник


09/02/06
4382
Москва
Да, я это упустил. Мне кажется проще доказать, что любое натуральное число $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$.

 Профиль  
                  
 
 Re: Задача про p=8k+3=a^2+bc
Сообщение21.05.2020, 16:21 
Заслуженный участник


20/12/10
8858
Руст в сообщении #1464384 писал(а):
Мне кажется проще доказать, что любое натуральное число $n$ за конечным числом исключений
представляется в виде $n=a^2+bc, \ a,b,c\in N, \  a,b,c<\sqrt n$.

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

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

 Профиль  
                  
 
 Re: Задача про p=8k+3=a^2+bc
Сообщение21.05.2020, 17:17 
Заслуженный участник


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

 Профиль  
                  
 
 Re: Задача про p=8k+3=a^2+bc
Сообщение21.05.2020, 21:00 
Заслуженный участник


09/02/06
4382
Москва
Для чисел $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$ перебросить несколько меньший множитель ко второму.
Но это не всегда удается.

 Профиль  
                  
 
 Re: Задача про p=8k+3=a^2+bc
Сообщение21.05.2020, 22:36 
Аватара пользователя


07/01/16
1426
Аязьма
Пара наблюдений:
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$, что с ними делать непонятно

 Профиль  
                  
 
 Re: Задача про p=8k+3=a^2+bc
Сообщение22.05.2020, 00:19 
Заслуженный участник


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

 Профиль  
                  
 
 Re: Задача про p=8k+3=a^2+bc
Сообщение22.05.2020, 20:21 
Аватара пользователя


07/01/16
1426
Аязьма
Руст в сообщении #1464473 писал(а):
Я воспринял это как намек на квадратичное представление
Но все таки, представимости $p$ в виде $x^2+2y^2$ самой по себе ведь недостаточно, вот то же $75=5^2+2\cdot5^2$ не может быть представлено в требуемом виде

 Профиль  
                  
 
 Re: Задача про p=8k+3=a^2+bc
Сообщение24.05.2020, 02:03 
Заслуженный участник


09/02/06
4382
Москва
Да. Но когда 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$ даже несколько завышена.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 16 ]  На страницу 1, 2  След.

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group