Олимпиадная задача о многочлене с целыми коэффициентами и делимости

Приведём несколько примеров таких многочленов.

1. Пусть $f(x)=(x-2)(x-4)^2(x+1)^5$, $m=6$, $n=32$. Тогда $f(6)=4 \cdot 2^2 \cdot 7^5=16 \cdot 7^5$ не делится на 32. Проверим, что $f(p^k)$ делится на 32 для любого простого числа $p$ и любого натурального $k$. Если $p^k=2$ или $p^k=4$, то значение многочлена равно 0. Для $p^k=2^k$, где $k \geqslant 3$, имеем $$f(2^k)=(2^k-2)(2^k-4)^2(2^k+1)^5=32(2^{k-1}-1)(2^{k-2}-1)^2(2^k+1)^5.$$ Наконец, если простое число $p$ нечётно (а значит, и $p^k$ нечётно), то $f(p^k)$ делится на 32, так как при любом нечётном $s=2l-1$ значение $f(s)$ делится на $(s+1)^5=(2l)^5$, а значит, и на 32.

2. Пусть $f(x)=x^{18}(3 x-x^2)+x^2-3 x$, $m=6$, $n=27$. Сначала проверим, что $f(p^k)$ делится на 27 при всех простых $p$ и натуральных $k$. Начнём со случая $p=3$. Заметим, что первое слагаемое делится на $3^{18}$, а значит, и на 27. Остаётся проверить, что $x(x-3)$ делится на 27 для чисел вида $3^k$, где $k \geqslant 1$. При $k=1$ и $k=2$ это проверяется непосредственно; при $k \geqslant 3$ число $3^k(3^k-3)$ также делится на $27$. Теперь проверим утверждение для простых чисел $p \neq 3$. В этом случае $p^k$ взаимно просто с $n$, а значит, достаточно доказать утверждение «$f(s)$ кратно $n$ при любом $s$, взаимно простом с $n$». Для этого заметим, что при всех таких $s$ по теореме Эйлера выполняется соотношение $s^{18}=s^{\varphi(27)} \equiv 1\pmod{27}$, а тогда $$x^{18} (3 x-x^2)+x^2-3 x \equiv (3 x-x^2)+x^2-3 x \equiv 0\pmod{27}.$$

Остаётся проверить, что $f(6)$ не делится на 27. Для этого снова заметим, что число $6^{18}$ делится на 27, а число $6^2-3 \cdot 6=18$ не делится на 27. 3) Пусть $q>2$ – простое число, $m=2q$, $n=q^3,$ и пусть $r_1, r_2,\ldots, r_t$ – все не кратные $q$ натуральные числа, меньшие $q^3.$ Положим $f(x)=x(x-q)\cdot (x-r_1)(x-r_2)\ldots(x-r_t)$. Этот многочлен подходит. Действительно, $$f(m)=q^2\cdot 2\cdot(2q-r_1)(2q-r_2)\ldots(2q-r_t)$$ не кратно $q^3.$ При $p\neq q$ число $p^k$ имеет остаток от деления на $q^3$, не кратный $q,$ поэтому один из множителей в определении $f(x)$ будет кратен $q^3$ при $x=p^k.$ При $p=q$ и $k\geqslant 2$ уже число $p^k(p^k-q)$ будет кратно $q^3.$ Наконец, при $p=q$, $k=1$ значение $f(p^1)=0$ делится на $q^3.$