When I saw factorials, I immediately thought about Wilson's theorem. However, I didn't succeed at all. I also thought about cyclic groups, but with such amount of information I haven't find the use of them. How can I prove it, where to start at least?
Source of the problem: practice for exam made by my teacher in the university. Motivation is simple - I want to see more abstract algebra ideas since I don't even know how to start correctly.
On
Let $p > 5$ be a prime.
Let $m = p - 1$. Let $n = p(k-1) + 1$ where $k > p$ is a prime divisor of $(p-1)! + 1$. Then $(m, n)$ is a solution.
First, we prove that for $p > 5$ there is a prime divisor $k > p$ of $(p-1)! + 1 $. By contradiction, suppose there is no such divisor. This divisor $l$ cannot be less than $p$, because we would have $l | (p-1)!$, which means $l$ does not divide $(p-1)! + 1$. So we must have $(p-1)! + 1 = p^e$ for some exponent $e$. But this means $(p-1)! = (p-1)(1 + \dots + p^{e-1}) \implies (p-2)! = 1 + \dots + p^{e-1}$. Taking mod $p-1$ on both sides the LHS has $\dfrac{p-1}{2}$ as a factor, so we have $0 = 1 + \dots + 1 = e$. This means that $p-1 | e \implies e \geq p -1$. So $p^e > (p-1)! + 1$. Therefore, there must be some other prime divisor greater than $p$.
Now, $m+n = p - 1 + p(k-1) + 1 = pk$
Taking mod p, we have $(m!)^n + (n!)^m+1 = ((p-1)!)^n + (n!)^{p-1} + 1$. But $n > p$ and $n$ is odd so we have that this is the same as $(-1)^n + 0 + 1 \equiv (-1) + 1 = 0$ in mod $p$.
Taking mod $k$, we have $(m!)^n + (n!)^m + 1 \equiv ((p-1)!)^{ p (k-1) + 1} + ((p(k-1)+ 1)!)^{p-1} + 1 \equiv (((p-1)!)^p)^{k-1} \cdot (p-1)! + 0 + 1 \equiv (p-1)! + 1 \equiv 0$.
Since both of them are prime, we have $pk | (m!)^n + (n!)^m + 1$ which means $m+n | (m!)^n + (n!)^m + 1 \blacksquare$.
When you are confronted to open problems like that, try on simple examples.
First example : $n = 0$. If $n = 0$, $m!^n + n!^m + 1 = 3$ thus $n + m = m$ divides $m!^n + n!^m = 1$ if and only if $m = 3$.
Second example : $n = 1$. If $n = 1$, $m!^n + n!^m + 1 = m! + 2$. If $n + m = m + 1$ is not prime, then $m! + 2 = 2$ modulo $m + 1$. If $m + 1$ is prime, then by Wilson theorem, $m! + 2 = 1$ modulo $m + 1$ thus there are no solution when $n = 1$.
Third example : $n = 2$. If $n = 2$, $m!^2 + n!^m + 1 = m!^2 + 2^m + 1$. Let $k = n + m = m + 2$. If $k$ is not prime and large enough (we don't care about small solutions), then $m!^2 + 2^m + 1 = (k - 2)! + 2^{k - 2} + 1 = 2^{k - 2} + 1$ modulo $k$. If $k \geqslant 3$ and $k$ is even, then $2^{k - 2} + 1$ is odd, so it can't be divided by $k$. I don't thnik we can say anything if $k$ is odd (we can't use Fermat here, we assumed $k$ is not prime).
If $k$ is prime, then by Wilson, $(k - 2)! + 2^{k - 2} + 1 = (k - 1)^{-1} + 2^{k - 2} + 1 = 2^{k - 2}$ modulo $k$. By Fermat, $2^{k - 2} = 2$ modulo $k$. It still doesn't work but it shows that computations are easier when we assume $k = n + m$ to be prime.
Fourth example : $n \geqslant 3$ and $k = n + m$ is prime. Notice that $n < k$ thus each number $1 \leqslant i \leqslant n$ is coprime with $k$. It implies that $n!$ is coprime with $k$, which enable us to use Fermat theorem. We have, in the field $\mathbb{Z}/k\mathbb{Z}$, \begin{align*} m!^n + n!^m + 1 & = (k - n)!^n + n!^{k - n} + 1\\ & = (k - 1)!^n(k - 1)^{-n} \cdots (k - n + 1)^{-n} + n!^{k - 1}n!^{1 - n} + 1\\ & = (-1)^n((-1) \cdots (-n + 1))^{-n} + n!^{1 - n} + 1 \textrm{ by Wilson and Fermat},\\ & = -(n - 1)!^{-n} + n!^{1 - n} + 1\\ & = n!^{-n}\left(-(n - 1)!^{-n}n!^n + n!^{1 - n}n!^n + n!^n\right)\\ & = n!^{-n}\left(-n^n + n! + n!^n\right). \end{align*} Notice that $A = -n^n + n! + n!^n > 0$ for $n$ large enough thus it doesn't vanish and for $m$ large enough with respect to $n$, $0 < A < m < k$, which proves that this quantity is not $0$ in $\mathbb{Z}/k\mathbb{Z}$. We just proved that for any $n$, there is a finite number of $m$ such that $n + m$ is prime and $(n,m)$ is solution to the problem. Therefore, it seems hard to search for a $n_0$ such that there are infinitely many $m$ such that $(n_0,m)$ is solution to the problem, because we would have to look to the case where $n + m$ is not prime.
Let us try an other path : find infinitely many $n$ such that there exists at least one $m$ (a priori larger that $n$) such that $(n,m)$ is solution. We look for $m$ such that $k = n + m$ is prime for simplicity. Let $n \geqslant 3$ and $m$ such that $k = n + m$ is prime. We just computed that $(n,m)$ is solution if and only if $k$ divides $A = -n^n + n! + n!^n$.
Assume now that $n$ is prime. Then, for all $1 \leqslant i \leqslant n - 1$, $i|(n! + n!^n)$ and $i$ is coprime with $-n^n$, thus $i$ doesn't divide $A$. And in $\mathbb{Z}/n\mathbb{Z}$, by Wilson, $$ \frac{A}{n} = -n^{n - 1} + (n - 1)! + (n - 1)!n!^{n - 1} = -1. $$ It proves that $n$ only divides $A$ once. For $n$ large enough, clearly, $A > n$ so $\frac{A}{n} > 1$ is divisible by no $i$ between $2$ and $n$. It implies that $A$ has a prime factor $k > n$. Set $m = k - n > 0$. Then, $k = n + m$ is prime and it divides $A$. $(n,m)$ is a solution to the problem.
It proves the wanted result. Actually, it proves that for any $n$ prime large enough, there exists at least one $m \geqslant 1$ such that $(n,m)$ is solution (and $n + m$ is prime).
For example, with $n = 3$, $-n^n + n! + n!^n = 195$ has for prime factors $3$, $5$ and $13$. One of them, of course, is $n$ and if you take the two others, it gives you that $m = 5 - 3 = 2$ and $m = 13 - 3 = 10$ fit. $(3,2)$ and $(3,10)$ are solutions. Indeed, $$ 3!^2 + 2!^3 + 1 = 45 = 9 \cdot 5 \in (3 + 2)\mathbb{Z}, $$ $$ 3!^{10} + 10!^3 + 1 = 47784725839932466177 = 3675748141533266629 \cdot 13 \in (3 + 10)\mathbb{Z}. $$