Делимость. Гроб?

[rightways]

Натуральное число $n$ не кратно $4$. Докажите, что существуют натуральные $a$ и $b$ для которых число $2a^2+3b^2+1$ кратно $n$.

[nnosipov]

Не вижу, почему здесь не должна сработать стандартная техника (случай простого модуля, гензелев подъём, китайская теорема об остатках). Мой любимый пример на эту тему: доказать, что сравнение $x^2-34y^2 \equiv -1 \pmod{m}$ разрешимо при любом $m$.

[rightways]

у меня возник вопрос.
простые числа вида $4k+1$ представимы в виде $a^2+b^2$. А простые числа какого вида представимы в виде $a^2-34b^2$ ?

[Deggial]

rightways в сообщении #1024131 писал(а):

у меня возник вопрос.
простые числа вида $4k+1$ представимы в виде $a^2+b^2$. А простые числа какого вида представимы в виде $a^2-34b^2$ ?

Попыток решения привести не хотите?
Как мы определяем, что простые вида $4k+1$ представимы в виде $a^2+b^2$? Ну и вот.

[rightways]

Ну это же теорема Ферма. ($p=4k+1=a^2+b^2$)
Например, есть еще такое $p=3k+1=a^2+3b^2$.
тогда думаю, скорее всего найдутся такие небольшие натуральные $a,b$ для которых каждое простое число вида $ p=17ak+b$ представимо как $p=a^2-34b^2$.

[Sonic86]

rightways, Вам только сама форма нужна? В общем, я не знаю, что конкретно надо, но если Вам нужна сама форма, то достаточно обойтись сравнениями. И теорема Ферма - это не откровение, чтобы на него просто сослаться и не знать, что с ней потом делать.

rightways в сообщении #1024208 писал(а):

Ну это же теорема Ферма. ($p=4k+1=a^2+b^2$)

$a^2+b^2\equiv 0\pmod p\Rightarrow t^2+1\equiv 0\pmod p \Rightarrow \left(\frac{-1}{p}\right)=1\Rightarrow p=4k+1$.

rightways в сообщении #1024208 писал(а):

Например, есть еще такое $p=3k+1=a^2+3b^2$.

$a^2+3b^2\equiv 0\pmod p\Rightarrow t^2\equiv -3\pmod p \Rightarrow \left(\frac{-3}{p}\right)=1\Leftrightarrow$ $ (-1)^{\frac{p-1}{2}}(-1)^{\frac{3-1}{2}\frac{p-1}{2}}\left(\frac{p}{3}\right)=1\Leftrightarrow p=3k+1$.

rightways в сообщении #1024208 писал(а):

тогда думаю, скорее всего найдутся такие небольшие натуральные $a,b$ для которых каждое простое число вида $ p=17ak+b$ представимо как $p=a^2-34b^2$.

(у Вас индуктор сломался, купите новый)
$a^2-34b^2\equiv 0\pmod p\Rightarrow ...$ продолжите сами

[rightways]

У меня вот такое решение посложнее.
Известно, что простые числа вида $p=24k+11$ представимы в виде $p=2a^2+3b^2$ (доказательство публиковать лень) . И так как $n$ не делится на $4$ то найдется натуральное число $t$ для которого $nt\equiv 2 (mod 4)$ . Дальше так как $(24n,6nt-1)=1$, то по теореме Дирихле найдется простое число $p=24nk+6nt-1$. Заметим, что наше $p\equiv 11(mod 24)$ поэтому $p=2a^2+3b^2=24nk+6nt-1$ откуда и следует требуемое.
Задачу можно окончательно усилить для $n$ не делящихся на $8$ так как у нас получилось, что $2a^2+3b^2+1$ делится на $6n$.

Вот теперь думаю, можно ли таким способом решить задачу nnosipov
про $a^2-34b^2\equiv -1(mod m)$.

Теперь наверное поняли для чего я искал простые вида $a^2-34b^2$.

Deggial: rightways, замечание за искажение ника участника. Поправлено.