1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Mohamad Ali Baydoun Jan 11 '15 at 12:20
  • $\begingroup$ Actually i just got this problem from a teacher i cant explain more since i havent solved it too $\endgroup$ – Deddy Jan 11 '15 at 12:24
3
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.