Республиканская олимпиада по математике, 2024 год, 11 класс

Дано простое число $p\ge 3$ и натуральное число $d$. Докажите, что существует натуральное число $n$, взаимно простое с $d$, такое, что произведение $P=\prod\limits_{1 \le i < j < p} {({i^{n + j}} - {j^{n + i}})}$ не делится на $p^n.$ ( Сатылханов К. )

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

Пусть $N = C^{2}_{p-1}$. Зафиксируем число $a$. Пусть $a_{i,j} = \frac{i}{j} \pmod{p^a}$ и $b_{i,j} = \frac{j^i}{i^j} \pmod{p^a}$. Будем выбирать такое $a$, что ни одна из скобок не делится на $p^a$. Заметим, что такое условие переписывается в виде $a_{i,j}^n \not\equiv b_{i,j} \pmod{p^a}$. Для удобства, пусть теперь есть элементы $a_1, \ldots, a_N$ и $b_1, \ldots b_N$, и нужно $a_i^n \not\equiv b_i \pmod{p^a}$. Заметим, что $ord_{p^a}(a_i) = k > a$, так как $p^a | i^k - j^k$ и $i,j<p$. Если рассмотреть $n$ от 1 до $a$, то существует не более одного $n$ в этом промежутке, что $a_i^n = b_i \pmod{p^a}$. Тогда в этом промежутке не более $N$ неподходящих $n$, тогда хотя бы $a-N$ подходящих. Можно взять такое $a$, что будет отрезок из $d$ идущих подряд подходящих $n$. Возьмем такое $n_0$ из них, что $n_0 = 1 \pmod{d}$. А далее возьмем $n = kd\varphi(p^a) + n_0$ для достаточно большого $k \in \mathbb{N}$. Для такого $n$, ни одна из скобок по прежнему не делится на $p^a$, $(n,d) = 1$, a также $v_p(\prod\limits_{1 \le i < j < p} {({i^{n + j}} - {j^{n + i}})}) \leq N*(a-1) \leq n$.