# different prime factor

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

• Without any constraints on $k$, I don't see how you'd solve this other than saying that clearly, $m^n + n^m$ is either prime or has a bunch of prime factors. – Mohamad Ali Baydoun Jan 11 '15 at 12:20
• Actually i just got this problem from a teacher i cant explain more since i havent solved it too – Deddy Jan 11 '15 at 12:24

## 1 Answer

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.