Prove that $n^k+1$ has a prime divisor $>2k$

Let $$n\ge3$$ & $$k\ge2$$. Show that $$n^k +1$$ has a prime divisor $$>2k$$.

• Where did you find this problem? It's quite interesting. – Carl Schildkraut Oct 20 '18 at 17:12

By Zsigmondy's Theorem (see here), $$n^{2k} - 1$$ has a prime divisor $$p$$ such that $$p$$ is not a divisor of $$n^j-1$$, for any $$j < 2k$$. In particular, $$p$$ does not divide $$n^k-1$$, but it does divide $$n^{2k} - 1 = (n^k - 1)(n^k + 1)$$, so $$p$$ divides $$n^k + 1$$. We also have $$n^{j} \neq 1 \pmod{p}$$ for $$j < 2k$$, so $$\varphi(p) = p-1 \ge 2k$$.