Question regarding the largest proper divisor of $x^n+1$ Let $x$ and $n$ be positive integers, with $n$ odd, and let $d$ be the largest proper divisor of $x^n+1$.

QUESTION: Is there a way to characterize the $x$ and $n$ satisfying $d > x^{(n+1)/2}$?

Example: $17^3+1=4914$ has largest [proper] divisor $d=2457 > 17^2 = 289$, but $18^3+1=5833$ has largest [proper] divisor $d=307 \not\gt 18^2=324$.

Lemma: Let $x,n$ be positive integers with $n\ge 3$. Let $d$ be the largest proper divisor of $x^n+1$. Then $d<x^{(n+1)/2}$ if and only if one of the following is true

*

*$x^n+1$ is prime.

*$x^n+1=pq$ for primes $x^{(n+1)/2}>q>p>x^{(n-1)/2}$
Proof: Assume that $d<x^{(n+1)/2}$. If $x^n+1$ is prime, we are done. Otherwise, let $p$ be the smallest prime factor of $x^n+1$, then
$$p=\frac{x^n+1}{d}>\frac{x^{n}+1}{x^{(n+1)/2}}=x^{(n-1)/2}+\frac{1}{x^{(n+1)/2}},$$
so $p>x^{(n-1)/2}$, since it's an integer coprime to $x$.
Suppose that $p^2\mid x^n+1$, then $(x^n+1)/p^2\le x<p$, which means this quotient must be $1$ and $p^2=x^n+1$. However, this has no solutions by Mihăilescu's theorem. We conclude that $p^2\nmid x^n+1$.
Let $q>p$ be the second largest prime factor of $x^n+1$, then again we find that $(x^n+1)/pq\le x<p$, whence this quotient must be one and $x^n+1=pq$. This completes the proof of one implication, the other one is easy.

Note that for $n$ odd, we have
$$
\frac{x^n+1}{x+1} = \frac{(-x)^n-1}{-x-1}=\sum_{j=0}^{n-1}(-x)^j\in\mathbb{Z},
$$
so $x^n+1$ cannot be prime for $x>1$ and $n\ge 3$ and the first case of the lemma doesn't occur (unless $x=1$ of course)
If we're in the second case, then $x+1\ge p>x^{(n-1)/2}\ge x$, so we must have that $n=3$ and $p=x+1$. It follows that $q=x^2-x+1$. We conclude that:
Theorem: Let $x>1$ and $n\ge 3$ be integers, $n$ odd. Let $d$ be the largest proper divisor of $x^n+1$. Then $d>x^{(n+1)/2}$ if and only if $n=3$, and $x+1$ and $x^2-x+1$ are both prime
