# On the largest prime factor of $1+n^k$

For every positive integer $n>1$ , let $f(n)$ denote the largest prime factor of $n$. How fast does $f(1+n^k)$ grow with respect to $k$ ? Is it true that $f(1+n^k) > 2k, \forall n >2, \forall k >1$ ?

• This second question is essentially my recent AMM problem 12043. Coincidence? – Max Alekseyev Jun 3 '18 at 13:07
• If one assumes that the distribution of values of a polynomial behave similarly to the distribution of all integers, then one can expect $f(n^k + 1)$ to be $\gg_\epsilon n^{k - \epsilon}$ often, but may be very small compared to $n$ infinitely often (i.e., smooth values of polynomials). I don't think one can say too much about a lower bound that always works. – Stanley Yao Xiao Jun 3 '18 at 14:05
• Related question mathoverflow.net/q/199599 , especially the work of Cam Stewart. Gerhard "I Knew It Looked Familiar" Paseman, 2018.06.03. – Gerhard Paseman Jun 3 '18 at 16:12

I do not attempt to answer the first question. The last question is closely related to Zsygmondy's Theorem: Given your hypotheses, and Zygmondy's theorem, there will be a prime $p$ which divides $n^{2k}-1,$ but does not divide $n^{j}-1$ for any $j < 2k.$ Note then that $p$ must be a prime divisor of $n^{k}+1.$ But also , the element $n+p\mathbb{Z}$ has multiplicative order $2k$ in the group of units of $\mathbb{Z}/p\mathbb{Z}.$ Hence $2k$ divides $p-1,$ so that $p >2k.$