49-я Международная Математическая OлимпиадаИспания, Мадрид, 2008 год

Докажите, что существует бесконечно много натуральных чисел $n$ таких, что число ${{n}^{2}}+1$ имеет простой делитель, больший числа $2n+\sqrt{2n}$.

Комментарий/решение

Лемма:

Пусть $p-$ простое число вида $8k+1$. Тогда существует натуральное число $n$ для которого $p|n^2+1$

Док-во:

В качестве $n$ можно выбрать число $n=x^{\frac{p-1}{4}}$, где $x^{p-1}\equiv 1\pmod p$, $x-$ примитивный корень $p$.

Теперь допустим, что таких $n$ со свойством, указанной в задаче, не бесконечно. Возьмем наибольший такой $n$ т.е. $q|n^2+1$ и $q>2n+\sqrt{2n}$. Проверкой можно убедиться, что $n>10$. Теперь выберем простое число $p$ вида $8k+1$, такое, что $p>n^2+1$ (такое $p$ существует по теореме Дирихле). Для этого $p$ по лемме, существует натуральное $m$ такое, что $p|m^2+1$.

Пусть $m\equiv r \pmod p$. Тогда $m^2\equiv r^2\equiv (p-r)^2\equiv -1 \pmod p$.

Один из двух натуральных чисел $r$ или $p-r$ не будет больше чем $p/2$ иначе их сумма будет больше $p$. Пусть этим числом будет $N$. Тогда $N<p/2$ или $p>2N$ и $p|N^2+1$. Пусть $p=2N+k$ тогда $-4\equiv 4N^2\equiv (p-k)^2\equiv k^2 \pmod p$ , то есть $k^2+4$ делиться на $p$. Так как $p\equiv 1\pmod 8$ тогда следует что $k^2+4\ge 2p$ откуда $k\ge \sqrt{2p-4}>\sqrt{4N-4}>\sqrt{2N}$. Следовательно, $p>2N+\sqrt{2N}$ и $p|N^2+1-$ противоречие, так как $N\ge \sqrt{p-1}>n$ и выходит что $n$ не является наибольшим числом как мы допустили.