Западно-Китайская математическая олимпиада, 2017 год

Пусть $p$ простое и $n$ натуральное такое, что $p^2$ делит $\prod\limits_{k = 1}^n {\left( {{k^2} + 1} \right)}$. Докажите, что $p < 2n$.

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

Докажем по индукции

Шаг 1. При $n=3$ имеем наибольше возможное $p=5$ . Условие выполняется

Шаг 2. Пусть при $n=l$ наибольше возможное $p=P$ , при котором произведение разделится на $P^2$. Пусть выполняется условие $P<2l$

Шаг 3. Перейдём к $n=l+1$. Рассмотрим несколько случаев

Случай 1. $(l^2+1)^2$ не делит произведение. Тогда понятно, что наибольшим простым числом , удовлетворяющим условию, останется $P$. А для него $P<2l<2(l+1)$

Случай 2. Пусть $(l^2+1)^2$ делит произведение и $l^2+1$- простое. Тогда наиболее возможным простым $p$ , удовлетворяющим условию ,будет $l^2+1$

Докажем, что $p<l+1$:

$$l^2+1<2(l+1)$$ ;$(l-1)^2<2$; $$l<1+\sqrt 2$$ Учитывая, что $l$ натуральное и больше 1, то получили неравенство для всех $l$ верное

Случай, когда $l^2+1$ составное, при этом квадрат простого делителя,входящего в $l^2+1$ делит произведение, доказывается аналогично