Теория чисел. Квадратичные невычеты

[Darts501]

Помогите решить задачу. Определим функцию z(x) как количество простых чисел не превосходящих x, и таких что число 17 является квадратичным невычетом по модулю каждого их этих простых чисел. Требуется найти асимптотику этой функции при x стремящемся к бесконечности. По этой задаче у меня вот какие соображения. Асимптотика функции $\pi(x)$ (количество простых чисел, меньших x ) известна (асимптотически ведет себя как $\frac{x}{\ln(x)}$) и есть предположение что z(x) примерно в два раза меньше чем $\pi(x)$, после этого понятно какая асимптотика у $z(x)$. Но во-первых, не понятно как это доказать строго, во-вторых, возможно это вообще не правда!

-- 29.06.2015, 13:43 --

я неправильно сформулировал условие. 17 должно быть наименьшим квадратичным невычетом по модулю этих простых чисел.

[ex-math]

Как мне кажется, появится множитель $1/128$. Ваши числа лежат в определенных арифметических прогрессиях. Асимптотика для простых в прогрессиях известна. Нужна лишь разность этих прогрессий и их общее количество. Скажем, $2$ будет квадратичным вычетом. Это известно для каких простых так -- там две прогрессии по модулю $8$. Вычетами будут еще $3$, $5$, $7$, $11$, $13$, а $17$ -- невычетом. Прогрессии соответствующие можно найти, пользуясь законом взаимности.

[DiMath]

Darts501
Из теоремы Дирихле о простых в арифметических прогрессиях следует, что $\pi(x;q,a)\approx \frac{\pi(x)}{\varphi(q)}$, где $\pi(x;q,a)$ - количество простых чисел, не превосходящих $x$ и равных $a$ по модулю $q$. Если Вам нужна сильная оценка, то самое лучшее, что есть на сегодня -- теорема Бомбьери - Виноградова (частный случай гипотезы Эллиота - Халберстама).

[ex-math]

DiMath
Теорема Бомбьери-Виноградова немного о другом. Там остаток оценивается в среднем по $a $ и $q $. У нас-то эти параметры фиксированы.

А ТС вроде затрудняется понять, как именно свести свою задачу к прогрессиям.

-- 30.06.2015, 14:43 --

Может надо поконкретнее подсказать? Если $(\frac{17}p)=-1$, то мы знаем (в зависимости от остатка, который дает $p $ по модулю $4$) каким будет $(\frac p {17}) $, то есть в каких прогрессиях по модулю $17$ лежат такие $p $.

[Darts501]

ex-math
я не понял, как из того, какое значение принимает $(\frac{p}{17})$ мы поймем в каких прогрессиях лежат эти простые числа. И еще ведь надо учитывать то, что для этих простых чисел число 17 является наименьшим квадратичным невычетом.

[Cash]

Darts501 в сообщении #1032515 писал(а):

я не понял, как из того, какое значение принимает $(\frac{p}{17})$ мы поймем в каких прогрессиях лежат эти простые числа.

Можно просто честно выписать $(\frac{p}{17})$ по всем возможным случаям. Хотя, на мой взгляд, это не нужно. Нам ведь надо знать лишь общее количество...

Darts501 в сообщении #1032515 писал(а):

И еще ведь надо учитывать то, что для этих простых чисел число 17 является наименьшим квадратичным невычетом

$17$ - невычет, $13$ - вычет, разницы особой нет.

[Sonic86]

Darts501 в сообщении #1032515 писал(а):

И еще ведь надо учитывать то, что для этих простых чисел число 17 является наименьшим квадратичным невычетом.

Ну пофиг.
Фраза "17 - наименьший квадратичный невычет" означает, что $\left(\frac{2}{p}\right)=\left(\frac{3}{p}\right)=...=\left(\frac{13}{p}\right)=1$, а $\left(\frac{17}{p}\right)=-1$. В любом случае имеем конечное число случаев, однозначно разбивающиеся на конечное число прогрессий, т.е. достаточно выполнить конечный перебор, оттуда найти плотность. Ну и в чем проблема?
Если хочется оптимизировать перебор - ну оптимизируйте: начните, например, с варианта, когда $5$ - наименьший квадратичный вычет по модулю $p$.

[ex-math]

Darts501
$(\frac p {17} ) $ имеет период $17$, так что простые из одной прогрессии с разностью $17$ будут одновременно вычетами или невычетами, смотря по первому члену прогрессии. Вы же можете сказать, будет ли, например, $2$ вычетом или невычетом по модулю $17$? Хотя, как уже заметил Cash, Вам надо лишь убедиться, что из $\varphi (17) $ прогрессий Вам подойдет ровно половина.
Наименьший невычет означает, что эти операции Вам придется проделать для всех простых от $2$ до $17$ (чтобы все, кроме последнего, были вычетами). Таких чисел семь штук, поэтому и $1/128$.

Вам стоит написать попытку решения. Сложно что-либо комментировать, не имея перед глазами выкладок.

-- 30.06.2015, 21:39 --

Насчет наименьшего уже Sonic86 написал.

[Darts501]

ex-math
Да, согласен с тем, что если $p_1$ и $p_2$ лежат в одной арифметической прогрессии с разностью 17 то $(\frac{p_1}{17})=(\frac{p_2}{17})$, но отсюда же не следует равенство $(\frac{17}{p_1})=(\frac{17}{p_2})$! И после того как Вы выделили прогрессии с разностью 17, только для простых чисел из этих прогрессий число 17 является квадратичным невычетом и только для них, что дальше делаете? Не понял как получается множитель $1/128$. Не могли бы это более подробно объяснить.

[Sonic86]

Darts501 в сообщении #1032666 писал(а):

если $p_1$ и $p_2$ лежат в одной арифметической прогрессии с разностью 17 то $(\frac{p_1}{17})=(\frac{p_2}{17})$, но отсюда же не следует равенство $(\frac{17}{p_1})=(\frac{17}{p_2})$!

Я извиняюсь, Вы квадратичный закон взаимности вообще видели?
Кроме того, зачем Вам это рассуждение? Вам же предложена схема решения, какие конкретно проблемы?

[ex-math]

Darts501
Равенство будет следовать. Нам нужно не просто равенство, а равенство конкретно единице (или минус единице). В случае $17$ все и так хорошо, а вот в случае $11$ результат будет зависеть от остатка, который дает $p$ по модулю четыре. В самом деле, посмотрите формулировку закона взаимности.
А дальше проводите эти рассуждения для простых, меньших семнадцати. В каждом случае будут свои прогрессии, есть китайская теорема об остатках, которая позволит понять сколько прогрессий и с какой разностью получится в их пересечении.

Начните уже последовательно и аккуратно оформлять свои рассуждения.