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

1$\begingroup$ This second question is essentially my recent AMM problem 12043. Coincidence? $\endgroup$ – Max Alekseyev Jun 3 '18 at 13:07

$\begingroup$ 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. $\endgroup$ – Stanley Yao Xiao Jun 3 '18 at 14:05

$\begingroup$ Related question mathoverflow.net/q/199599 , especially the work of Cam Stewart. Gerhard "I Knew It Looked Familiar" Paseman, 2018.06.03. $\endgroup$ – 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 $p1,$ so that $p >2k.$

1$\begingroup$ Congratulations on solving AMM problem 12043. $\endgroup$ – Max Alekseyev Jun 3 '18 at 13:12

$\begingroup$ @MaxAlekseyev : I did wonder whether this was some contest problem, and wondered whether to write an answer or not, for that reason. It did not occur to me it might be a Monthly Problem (these are harder to see these days, since the Monthly ( of recent years) doesn't seem to be freely available online). $\endgroup$ – Geoff Robinson Jun 3 '18 at 13:41