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

[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}.

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