14-я Международная Жаутыковская олимпиада, 2018 год


Докажите, что существует бесконечно много пар $(m, n)$ натуральных чисел таких, что число $(m!)^n+(n!)^m+1$ делится на $m+n$. ( Сатылханов К. )
посмотреть в олимпиаде

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

Комментарии от администратора Комментарии от администратора №1.     Будем искать искомую пару так, чтобы число $m+n=p$ было простым и число $n$ четным. Используя теорему Вильсона, получаем, что $$m!=(p-n)!= {(p-1)!\over (p-n+1)\dots(p-2)(p-1)}\equiv {-1\over -(n-1)\dots(-2)(-1)}\equiv {1\over (n-1)!}\equiv {n\over n!}\pmod p. $$
По малой теореме Ферма $(n!)^p\equiv n!\pmod p$, следовательно, $$(m!)^n+(n!)^m+1\equiv\left({n\over n!}\right)^n+(n!)^{p-n}+1\equiv {n^n+n!+(n!)^n\over (n!)^n}\pmod p ;$$ то есть достаточно доказать, что для бесконечного количества четных $n$ число $n^n+n!+(n!)^n$ имеет простой делитель $p > n$.
Докажем, что этому условию удовлетворяют, например, все числа вида $n=2q$, где $q > 2$ -- простое число. Обозначим $A=(2q)^{2q}+(2q)!+((2q)!)^{2q}$. Для простого $p$ и натурального $k$ обозначим через $v_p(k)$ наибольшее целое число $\ell$ такое, что $k$ делится на $p^\ell$. Если $r < 2q$ -- простое число и $r\notin\{2, q\}$, то $A\equiv (2q)^{2q}\not\equiv 0\pmod r$. Простое число $q$ входит в $(2q)!$ в степени 2, а в $(2q)^{2q}$ и $((2q)!)^{2q}$ -- в степенях $2q$ и $4q$ соответственно, поэтому $v_q(A)=2$.
Далее, $v_2((2q)!)=\left[2q\over 2\right]+\left[2q\over 4\right]+ \left[2q\over 8\right]+\dots < {2q\over 2}+{2q\over 4}+{2q\over 8}+\dots=2q$, следовательно, $v_2((2q)!) < v_2((2q)^{2q})$ и, конечно, $v_2((2q)!) < v_2((2q)!^{2q})$, поэтому $v_2(A)\leq 2q-1$. С другой стороны, $A > (2q)^{2q} > 2^{2q-1}q^2$, поэтому у $A$ есть простой делитель $p > 2q$, что и требовалось доказать.

  2
2018-01-15 23:01:57.0 #

Докажем, что пара $(p-1,(p-1)!-p+2)$ подходит для всех достаточно больших простых $p$.

Тогда $m+n=(p-1)!+1=m!+1$

В этом случае $n$ нечетно и поэтому $(m!)^n+1$ делится на $m+n$. остается заметить что и $(n!)^m$ делится на $m+n$, так как для достаточно больших $p$ :

$p<\frac{m+n}{p}<n$ , откуда выходит что даже $n!$ делится на $m+n$.

Число $\frac{m+n}{p}$ является целым по теореме Уилсона.