9
$\begingroup$

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

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

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$.

$\endgroup$

Your Answer

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