When does $x^n-n$ factor?

Question

Suppose that $n=(kj)^k$ for some integers $j\geq 1$ and $k\geq 2$. Then writing $m=k^{k-1}j^k$, we have $$x^n-n=(x^m)^k - (kj)^k$$ and so $x^m-kj$ is a factor of $x^n-n$. I would like to show that this is the only way that $x^n-n$ can factor over the integers, that is, if $x^n-n$ is not irreducible, then $n=(kj)^k$ for some positive integers $j,k$, with $k\geq 2$.

Answer 1

This is a bit too large for a comment, but rules out many cases as irreducible. It gives a necessary but not sufficient condition $n$ must satisfy.

Here is the lemma we prove: if for any $p$ dividing $n$ we have that $\gcd(v_p(n), n)=1$, then the polynomial for $n$ is irreducible. Here, $v_p(n)$ is the p-adic valuation of $n$.

We look at the Newton polygons for every prime $p$ that divides $n$. Specifically, they are all pure of slope $-\frac{v_p(n)}{n}$. If for at least one $p$ dividing $n$ we have that $\gcd(v_p(n), n)=1$ then this implies that it is irreducible because the Newton polygon does not pass through an integer point meaning it can't factor into two polynomials.

This means if it is reducible, we must have that $\gcd(v_p(n), n)>1$ for all $p$ dividing $n$. So we can write $v_p(n)=p*k_p$ for some integer $k_p\ge 1$, and we have,

$$n=\prod_{p |n} p^{pk_p}$$

Unfortunately this isn't enough to prove your factorization must occur, but it does open the door to trying to brute force search for a counterexample to the conjecture.