# small factors of $p^k + 1$

I am a beginner in number theory and interested to know about what is the minimum value of $k$ such that $p^k+1$ has a small factor, by small I mean of $O(poly(log p))$. I don't know how to start about solving this problem. Any hint or references in the form of books or papers or theorems will be highly welcomed.

Thanks.

• I assume you meant $p$ to be prime. If $q$ is a prime, with $p$ a non-square mod $q$, then $q$ divides $p^{(q-1)/2}+1$. The smallest such $q$ is $O((\log p)^4)$ under GRH, so $k \le (q-1)/2$. I don't know if you can do better than that. I also assumed you are not interested in the fact that $p+1$ is divisible by $2$ if $p$ is odd. Commented Aug 22, 2016 at 7:25
• Yes of course I mean $p$ to be an odd prime and I am excluding $2$ from the set of small factor(small as defined above). Can something be said without assuming GRH ? Commented Aug 22, 2016 at 8:22
• @FelipeVoloch the bound is $O(\log ^2 p)$ by N C Ankeny
– xyz
Commented Aug 22, 2016 at 9:20