Задача о неуловимом решении

[lel0lel]

GogalNikolay

lel0lel в сообщении #1708995 писал(а):

проверяете делимость нечётного числа $p$ определённого вида на нечётные, ограниченные сверху числом $\sqrt{p}-C \sqrt[4]{p},$ где $C$ -- некоторая константа. Отступ $C\sqrt[4]{p}$ как раз и получен с помощью применения метода Ферма для чисел рассматриваемого вида.

Значение константы можно рассчитать, оно небольшое.

[GogalNikolay]

lel0lel в сообщении #1730259 писал(а):

Значение константы можно рассчитать, оно небольшое

То есть пользы как с козла молока даже для очень больших чисел, а что рассчитывать разве готового нет

[GogalNikolay]

lel0lel в сообщении #1708995 писал(а):

нужно просто проверить все простые до почти $\sqrt{p}$

Ну, может, скажем, совсем не все, а половину. О простых делителях a^2 - 2: только половина простых

Для того чтобы простое p > 2 делило a^2 - 2 при некотором a, необходимо, чтобы 2 было квадратичным вычетом по модулю p, то есть чтобы существовало решение a^2 \equiv 2 \pmod{p}.

По закону квадратичной взаимности:

\left(\frac{2}{p}\right) = (-1)^{(p^2-1)/8}

Отсюда 2 — квадратичный вычет по модулю p тогда и только тогда, когда p \equiv \pm 1 \pmod{8}, то есть p \equiv 1 или 7 \pmod{8}.

Из четырёх нечётных классов вычетов по модулю 8 — 1, 3, 5, 7 — подходят только два. Следовательно, ровно половина всех нечётных простых может быть делителем чисел вида a^2 - 2.

Следствие для решета. При просеивании последовательности a^2 - 2 на простоту «убийцами» выступают только простые p \equiv \pm 1 \pmod{8}. Простые p \equiv \pm 3 \pmod{8} никогда не делят a^2 - 2, и их можно полностью исключить из решета.

Это означает, что плотность решета вдвое ниже: вместо произведения по всем простым \prod (1 - 1/p) в нём участвует лишь

\prod_{\substack{p \leq z \\ p \equiv \pm 1 \pmod{8}}} \left(1 - \frac{1}{p}\right)

что асимптотически даёт \sim C \cdot \frac{1}{\sqrt{\ln z}} — существенно более медленную сходимость, чем у полного произведения \sim 1/\ln z.

[lel0lel]

GogalNikolay в сообщении #1733935 писал(а):

только половина простых

Для того чтобы простое p > 2 делило a^2 - 2 при некотором a, необходимо, чтобы 2 было квадратичным вычетом по модулю p, то есть чтобы существовало решение a^2 \equiv 2 \pmod{p}.

Это всё хорошо и правильно. Но только как упражнение. Для больших чисел такой метод практически неприменим.

[tolstopuz]

Lemma 2.4. Let $p=X^2-k$ be a composite number with least prime factor $q$. If $(X+j)^2-p$ is not a perfect square for some integer $j\geq 1$, then $q<X+j+1-\sqrt{(X+j)^2-p}$.

Вообще-то лемма неверна:
$3\cdot5=4^2-1=5^2-10$, но $3>6-\sqrt{10}$.
Или $7\cdot17=11^2-2=13^2-50$, но $7>14-\sqrt{50}$.

Но она и не нужна.

-- добавлено через 32 минуты --

После нескольких пинков ChatGPT выдал такое:

Теорема. Пусть $a\geqslant1$, $b\in\{0,1\}$, $1\leqslant d\leqslant a$ — целые числа,

$$c=a^2+a+(a+1)b,\qquad n=2a+b+2c-2d,$$

$$p=(n+1)^2-(b+2).$$

Тогда $p$ простое в том и только в том случае, если для всех целых $1\leqslant x<c-d$ выполняется

$$(n-2x)^2\not\equiv b+2\pmod{4x+2}.$$

Доказательство. Обозначим $X=n+1$, $m=2(c-d)+1$. Тогда

$$X=m+2a+b\geqslant2c+1\geqslant5.$$

Число $p$ нечётно, а из $X^2-p=b+2\in\{2,3\}$ следует

$$(X-1)^2<p<X^2,\qquad X=\lceil\sqrt p\rceil.$$

Кроме того, $p=X^2-(b+2)>X>m$.

Для любого целого $x\geqslant1$, положив $q=2x+1$, получаем

$$(n-2x)^2-(b+2)=(X-q)^2-(b+2)\equiv p\pmod q.$$

Левая часть чётна, а $q$ нечётно. Следовательно,

$$(n-2x)^2\equiv b+2\pmod{4x+2}\iff 2x+1\mid p.$$

Если $p$ простое, оно не делится ни на одно из чисел $2x+1$ при $1\leqslant x<c-d$, поскольку все они меньше $p$.

Пусть теперь $p$ составное, а $q$ — его наименьший простой делитель. Положим $r=p/q$. По лемме

$$q+r\geqslant2X+2,$$

откуда

$$p=qr\geqslant q(2X+2-q).$$

С другой стороны, непосредственно из определений $c$, $X$ и $m$ получаем

$$m(2X+2-m)-p=4(a+b-d+1)>0.$$

Поэтому

$$0<4(a+b-d+1)\leqslant m(2X+2-m)-q(2X+2-q)=(m-q)(2X+2-m-q).$$

Поскольку $m<X$ и $q\leqslant\sqrt p<X$, второй множитель положителен. Следовательно, положителен и первый, то есть

$$q<m=2(c-d)+1.$$

Таким образом, $q=2x+1$ для некоторого целого $1\leqslant x<c-d$. Поскольку $q\mid p$, получаем

$$(n-2x)^2\equiv b+2\pmod{4x+2}.$$

Следовательно, составное число $p$ не удовлетворяет условию теоремы.

Теорема доказана.

Таким образом, доказана даже более сильная версия теоремы 1.1: вместо $1\leqslant x<c$ достаточно проверять $1\leqslant x<c-d$.