different prime factor

Question

Let $k$ be an positive integer and $m$ is the odd positive integer. Prove that there exist a natural number $n$ such that $ m^n + n^m $ have at least $k$ different prime factor

Answer 1

Let $p$ be a prime not dividing $m$. Then $m^n\equiv 1\pmod p$ whenever $n\equiv 0\pmod{p-1}$. If additionally $n\equiv -1\pmod p$ then (here we use that $m$ is odd) $$ m^n+n^m\equiv 1+(-1)^m\equiv 1-1\equiv 0\pmod p.$$ As said, this holds whenever $n\equiv 0\pmod{p-1}$ and $n\equiv -1\pmod p$. To solve the problem at hand, pick $k$ distinct primes $p_1,\ldots,p_k$ such that these congruences can be fulfilled concurrently. It suffices to ensure that $p_i>m$ (so definitely $p_i\nmid m$) and $p_i\nmid p_j-1$ for all $i,j$. This can be done recursively: Given suitable primes $\max(m,3)<p_1< \ldots< p_{k-1}$ pick $p_k>p_{k-1}$ such that $p_k\equiv 2\pmod {p_1\cdots p_{k-1}}$, which is possible by Dirichlet.