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$, что и требовалось доказать.

Докажем, что пара $(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}$ является целым по теореме Уилсона.

Моя цель была достичь множества таких чисел с помощью подставлений с $p-1$ что бы использовать МТФ и Теорему Вильсона, и вот что у меня получилось:

Сделаем подстановку $(qp-p+1,p-1)$ где $(p≠q≠2)\in \mathbf{P}$. $$S=((qp-p+1)!)^{p-1}+((p-1)!)^{qp-p+1}+1$$ должно делиться на $pq$, посмотрим, действительно ли это так?

Если $S$ делится на $p$ и на $q$ то задача решена, сперва проверим делится ли она на $p$?

Заметим что $qp-p+1$ больше чем $p$, соответственно его факториал будет содержать $p$ и делиться на него же.

Теперь внимание на $((p-1)!)^{pq-p+1}+1$, используем теорему Вильсона и поймём что оно делится на $p$.

Теперь пройдемся по $q$, $(qp-p+1>q)((q-1)(p-1)>0)$ по этому его факториал будет делиться на $q$. Докажем что вторая часть $S$ поделится на $q$.

По идее, мы еще не выбрали $q$, давайте сделаем это что бы нам было удобно. Нам бы хотелось бы что бы $((p-1)!)^{pq-p+1}+1$ делилось на $q$, пусть тогда $p-1<q$ (что бы $(p-1)!$ не поделилось на него) и еще используя то что $pq-p+1=p(q-1)+1$ (МТФ) нам останется доказать что $(p-1)!+1$ делится на $q$. Тогда, просто возьмем такое $q$ что это возможно, но останется еще доказать что такое $q$ найдется что бы $(p-1<q)$, а это легко ибо мы знаем что любой делитель $(p-1)!+1$ будет больше чем $p-1$ в связи с взаимнопростостью с любым числом до него. Вдруг, я подумал: «А что если $(p-1)!+1=p^a$», и вспомнил задачу, значит просто возьмем $p>7$ и задача решена!