Prime divisors of $p^n+1$

Question

Let $p$ be a rational prime and $n$ be a positive integer.

It can be easily deduced from Zsigmondy's theorem that $p^n+1$ has a prime divisor greater than $2n$ except when $(p,n)=(2,3)$ or $(2^k-1,1)$ for some positive integer $k$. Hence we know that there exists an odd prime divisor of $p^n+1$ greater than $n$ if and only if $(p,n)\neq(2,3)$ or $(2^k-1,1)$ for any positive integer $k$.

Question:

(1). For which $(p,n)$ does there exist at least two odd prime divisors of $p^n+1$ coprime to $n$?

(2). For which $(p,n)$ does there exist at least two odd prime divisors of $p^n+1$ greater than $n$?

Answer 1

$x^n+1$ factors over $\mathbb{Z}[x]$ unless $n$ is a power of two.

For $n=15$ the factorization is $ (x + 1) \cdot (x^{2} - x + 1) \cdot (x^{4} - x^{3} + x^{2} - x + 1) \cdot (x^{8} + x^{7} - x^{5} - x^{4} - x^{3} + x + 1)$.

The factors $(p^{2} - p + 1)$ and $(p^{4} - p^{3} + p^{2} - p + 1)$ are odd and with congruence reasons you can get at least two prime factors larger than $15$.

Answer 2

I assume $p$ odd.

1) Setting $s=p+1$, it is easy to show that $p+1$ is coprime to $\frac{p^n+1}{p+1} = \frac{(s-1)^n+1}{s}$ (use binome formula).

2) There is a generalization of a theorem known to Fermat, by which he canceled primes in some expressions :

Theorem : Assume that $a$ and $b$ are two integers and $n$ is a prime number. Then every prime divisor of $a^n-b^n$ that does not divide $a-b$ is congruent to $1$ modulo $n$ (check it).

Applying this with $a=p$ and $b=-1$, and taking (1) into account, you get that every prime that divide $\frac{p^n+1}{p+1}$ is congruent to $1$ modulo $n$ for every prime $n$. In particular, they must be of the form $1+kn > n$. So the answer to your two questions, when $n$ is prime, is that this occurs each time $\frac{p^n+1}{p+1}$ does not reduce to a single prime.