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


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

  • $\begingroup$ 2^2^4+1 is prime. If $n$ is not power of two, $x^n+1$ factors over Z[x]. $\endgroup$
    – joro
    Dec 25, 2014 at 15:02

2 Answers 2


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


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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.