# Factoring $x^n+n$ over $\mathbb{Z}[x]$

I was working on some polynomial irreducibility problems, and eventually got to wondering which positive integers $n$ had the property that $p_n(x)=x^n+n$ is reducible over $\mathbb{Z}[x]$ i.e. can be written as the product of two other polynomials with integer coefficients. I found two classes of integers that work without too much effort

Class 1: $n=4m^4, m\in \mathbb{Z}$. Here,

$$x^n+n=x^{4m^4}+4m^4=\left(x^{m^4}\right)^4+4m^4,$$

which factors according to the Sophie-Germain identity:

$$a^4 + 4b^4 = (a^2 + 2b^2 + 2ab)(a^2 + 2b^2 - 2ab).$$

Class 2: $n=a^{a^b}$, for an odd integer $a>1$, and any positive integer $b>1$. Now,

$$x^{a^{a^b}}+a^{a^b}=\left(x^{a^{a^b-b}}\right)^{a^b}+a^{a^b}.$$

Since $a$ is odd, $a^b$ is odd, so this can be factored using the identity for the sum of two odd powers.

Both of these were very directly motivated by considering identities that factor particular binomials, and then choosing $n$ to force $p_n(x)$ into the desired form. Unfortunately, I don't know of anymore such identities, and the obvious limitation of this technique is its inability to show that other values of $n$ give irreducible $p_n$.

I suspect that characterizing all such $n$ will require much heavier machinery than the simple manipulations I've used so far, and I'd really appreciate any help/further progress.

• By Eisenstein, if there is a prime $p$ such that $p$ divides $n$ but $p^2$ doesn't, we have irreducibility. Works for $x^k+n$. Sep 13, 2015 at 1:06
• Ahh, and this also eliminates all square free $n$. Sep 13, 2015 at 1:13
• Way more than square-free are eliminated. @SamirKhan Sep 13, 2015 at 1:14
• One can push Eisenstein some more in various ways. Sep 13, 2015 at 1:15
• When $n$ is even, if $x^n+n$ is divisible by $p(x)$ then it is divisible by $p(-x)$. This means that it either factors as $p(x^2)q(x^2)$ for some $p,q$, or it factor as $p(x)p(-x)$ for some $p$. Not sure how that helps... In particular, if $n$ is even and not a perfect square, then it can only factor as $p(x^2)q(x^2)$. Sep 13, 2015 at 1:17

It turns out $p_n(x)$ is reducible only when it is "obvious." More precisely, polynomial $p_n(x)$ is reducible over $\mathbb{Z}$ if and only if at least one of the following two conditions hold.

• There exists an odd prime $q$ such that $q\,\vert\,n$ and $n$ is the $q$th power.
• We have $n = 4b^4$ for some $b \in \mathbb{N}$.

Proof. The "if" direction is easy. In the first case, we have$$p_n(x) = x^n + n = \left(x^{n\over{q}} + \sqrt[q]{n}\right)\left(\sum_{k=0}^{q-1} (-1)^k \sqrt[q]{n^k} x^{{(q-1-k)n}\over{q}}\right),$$and in the second one, Sophie Germain's Identity gives us$$p_n(x) = x^{4b^4} + 4b^4 = \left( x^{2b^4} + 2bx^{b^4} + 2b^2\right)\left(x^{2b^4} - 2bx^{b^4} + 2b^2\right).$$Now, assume that $p_n(x)$ is reducible; this is equivalent to$$[\mathbb{Q}(\zeta_{2n}\sqrt[n]{n}) : \mathbb{Q}] < n$$because $\zeta_{2n} \sqrt[n]{n}$ is a root of $p_n(x)$. Let $c \in \mathbb{N}$ be the largest number such that $n$ is the $c$th power, say $n = t^c$. Let$$g = \text{gcd}(n, c),\text{ }a = t^{c\over{g}},$$then $n = a^g$.

We need to study the field $\mathbb{Q}(\sqrt[n]{n})$. Since all the roots of $x^n - n$ have modulus $\sqrt[n]{n}$, the modulus of the constant term of the minimal polynomial of $\sqrt[n]{n}$ over $\mathbb{Q}$ is $$\left(\sqrt[n]{n}\right)^{[\mathbb{Q}(\sqrt[n]{n}) : \mathbb{Q}]} = t^{{[\mathbb{Q}(\sqrt[n]{n}): \mathbb{Q}] \cdot c}\over{n}}.$$This field is real, and so $|x| = \pm x$ for every $x \in \mathbb{Q}$, thus$$t^{{[\mathbb{Q}(\sqrt[n]{n}): \mathbb{Q}] \cdot c}\over{n}} \in \mathbb{Q}.$$Since $t$ is not a perfect power, this implies $${{[\mathbb{Q}(\sqrt[n]{n}): \mathbb{Q}] \cdot c}\over{n}}\in\mathbb{N},$$so $$n\text{ divides }{{[\mathbb{Q}(\sqrt[n]{n}): \mathbb{Q}] \cdot c}},$$so $${n\over{g}}\text{ divides }{{[\mathbb{Q}(\sqrt[n]{n}):\mathbb{Q}]\cdot c}\over{g}}.$$Since$$\gcd\left({n\over{g}},{c\over{g}}\right)=1,$$we get $${n\over{g}}\text{ divides }[\mathbb{Q}(\sqrt[n]{n}):\mathbb{Q}],$$and hence $$[\mathbb{Q}(\sqrt[n]{n}):\mathbb{Q}]\ge {n\over{g}}.$$On the other hand, $\sqrt[n]{n}=\sqrt[n/g]{a}$, so $$[\mathbb{Q}(\sqrt[n]{n}):\mathbb{Q}]=[\mathbb{Q}(\sqrt[n/g]{a}):\mathbb{Q}]\le {n\over{g}},$$hence together, we get $$[\mathbb{Q}(\sqrt[n]{n}):\mathbb{Q}]= {n\over{g}}.$$(Notice that this implies that the polynomial $x^n-n$ is reducible if and only if $g>1$; in other words, if and only if there exists a prime $q$ such that $q\mid n$ and $n$ is the $q$th power). The field$$\mathbb{Q}(\sqrt[n]{n})=\mathbb{Q}(\sqrt[n/g]{a})$$has a subfield $\mathbb{Q}(\sqrt[d]{a})$ for every $d\mid(n/g)$, and similar calculation as above shows$$[\mathbb{Q}(\sqrt[d]{a}): \mathbb{Q}]=d.$$These are in fact the only subfields of $\mathbb{Q}(\sqrt[n/g]{a})$: if $F$ is any subfield of $\mathbb{Q}(\sqrt[n/g]{a})$, then $$d:=[F:\mathbb{Q}] = \frac{[\mathbb{Q}(\sqrt[n/g]{a}) : \mathbb{Q}]}{[\mathbb{Q}(\sqrt[n/g]{a}) : F]} = \frac{n}{g\cdot [\mathbb{Q}(\sqrt[n/g]{a}) : F]}$$ and the modulus of the constant term of minimal polynomial of $\sqrt[n/g]{a}$ over $F$ is$$\sqrt[n/g]{a}^{[\mathbb{Q}(\sqrt[n/g]{a}):F]}=\sqrt[d]{a}.$$This is again a real field, thus $\sqrt[d]{a}\in F$. We have$$\mathbb{Q}(\sqrt[d]{a})\subseteq F \text{ and }[\mathbb{Q}(\sqrt[d]{a}): \mathbb{Q}]=d=[F:\mathbb{Q}],$$hence$$F=\mathbb{Q}(\sqrt[d]{a}).$$

If we consider instead the field $\mathbb{Q}(\zeta_{2n}\sqrt[n]{n})$ and the polynomial$$x^n+n=p_n(x),$$then the first part of the above argument again gives us$$[\mathbb{Q}(\zeta_{2n}\sqrt[n]{n}):\mathbb{Q}]\ge {n\over{g}};$$however, this time there does not have to be an equality. Together, we get $${n\over{g}} \le [\mathbb{Q}(\zeta_{2n}\sqrt[n]{n}):\mathbb{Q}]<n,$$so $g>1$.

If $g$ is divisible by some odd prime, then we are done. Now, assume that $g$ is a power of $2$, say $g=2^\ell$ for $\ell\in\mathbb{N}$. Then $2\mid n$, so $2\mid a$, so$$2^{2^\ell}=2^g\mid n.$$We have$$2^\ell\ge\ell+1,\text{ }\ell\in\mathbb{N},$$hence$$2 \text{ divides } {{n}\over{2^\ell}}={n\over{g}}.$$It follows the field$$\mathbb{Q}(\sqrt[n]{n})=\mathbb{Q}(\sqrt[n/g]{a})$$has a subfield $\mathbb{Q}(\sqrt{a})$. The fields $\mathbb{Q}$ and $\mathbb{Q}(\sqrt{a})$ are the only subfields of $\mathbb{Q}(\sqrt[n/g]{a})$ that are Galois over $\mathbb{Q}$ because $\sqrt[d]{a}$ has non-real conjugates for $d>2$. We have $$\sqrt{2}\in\mathbb{Q}(\zeta_8)\subseteq\mathbb{Q}(\zeta_{2^{2^\ell+1}})\subseteq\mathbb{Q}(\zeta_{2n})$$ and$$\sqrt{p}\in\mathbb{Q}(\zeta_{4p})\subseteq\mathbb{Q}(\zeta_{2n})$$for every odd prime $p$ dividing $a$, hence $\mathbb{Q}(\sqrt{a})\subseteq\mathbb{Q}(\zeta_{2n})$. The extension $\mathbb{Q}(\zeta_{2n})/\mathbb{Q}$ is Galois with abelian Galois group, so $$\operatorname{Gal}(\mathbb{Q}(\zeta_{2n})/\mathbb{Q}(\zeta_{2n})\cap\mathbb{Q}(\sqrt[n]{n}))\unlhd\operatorname{Gal}(\mathbb{Q}(\zeta_{2n})/\mathbb{Q})$$and the extension $\mathbb{Q}(\zeta_{2n})\cap\mathbb{Q}(\sqrt[n]{n})/\mathbb{Q}$ is Galois (and abelian). Together, it implies$$\mathbb{Q}(\zeta_{2n})\cap\mathbb{Q}(\sqrt[n]{n})=\mathbb{Q}(\sqrt{a}).$$Since $\mathbb{Q}(\zeta_{2n})/\mathbb{Q}$ is Galois, the fields $\mathbb{Q}(\zeta_{2n})$ and $\mathbb{Q}(\sqrt[n]{n})$ are linearly disjoint over $\mathbb{Q}(\zeta_{2n})\cap\mathbb{Q}(\sqrt[n]{n})$ and$$[\mathbb{Q}(\zeta_{2n},\sqrt[n]{n}):\mathbb{Q}(\zeta_{2n})\cap\mathbb{Q}(\sqrt[n]{n})]=[\mathbb{Q}(\zeta_{2n}):\mathbb{Q}(\zeta_{2n})\cap\mathbb{Q}(\sqrt[n]{n})]\cdot[\mathbb{Q}(\sqrt[n]{n}):\mathbb{Q}(\zeta_{2n})\cap\mathbb{Q}(\sqrt[n]{n})].$$Using this, we get $$[\mathbb{Q}(\zeta_{2n},\sqrt[n]{n}):\mathbb{Q}]$$$$=[\mathbb{Q}(\zeta_{2n},\sqrt[n]{n}):\mathbb{Q}(\zeta_{2n})\cap\mathbb{Q}(\sqrt[n]{n})]\cdot[\mathbb{Q}(\zeta_{2n})\cap\mathbb{Q}(\sqrt[n]{n}):\mathbb{Q}]$$$$=[\mathbb{Q}(\zeta_{2n}):\mathbb{Q}(\zeta_{2n})\cap\mathbb{Q}(\sqrt[n]{n})]\cdot[\mathbb{Q}(\sqrt[n]{n}):\mathbb{Q}(\zeta_{2n})\cap\mathbb{Q}(\sqrt[n]{n})]\cdot[\mathbb{Q}(\zeta_{2n})\cap\mathbb{Q}(\sqrt[n]{n}):\mathbb{Q}]$$$$={{[\mathbb{Q}(\zeta_{2n}):\mathbb{Q}]\cdot[\mathbb{Q}(\sqrt[n]{n}):\mathbb{Q}]}\over{[\mathbb{Q}(\zeta_{2n})\cap\mathbb{Q}(\sqrt[n]{n}):\mathbb{Q}]}}$$$$={{[\mathbb{Q}(\zeta_{2n}):\mathbb{Q}]\cdot[\mathbb{Q}(\sqrt[n]{n}):\mathbb{Q}]}\over{[\mathbb{Q}(\sqrt{a}):\mathbb{Q}]}}$$$$={{\varphi(2n)\cdot n}\over{2^{\ell+1}}}.$$

But we have$$\mathbb{Q}(\zeta_{2n},\sqrt[n]{n})=\mathbb{Q}(\zeta_{2n},\zeta_{2n}\sqrt[n]{n}),$$and by the same method as above, we can show that$$[\mathbb{Q}(\zeta_{2n},\zeta_{2n}\sqrt[n]{n}):\mathbb{Q}]={{[\mathbb{Q}(\zeta_{2n}):\mathbb{Q}]\cdot[\mathbb{Q}(\zeta_{2n}\sqrt[n]{n}):\mathbb{Q}]}\over{[\mathbb{Q}(\zeta_{2n})\cap\mathbb{Q}(\zeta_{2n}\sqrt[n]{n}):\mathbb{Q}]}}$$$$={{\varphi(2n)\cdot[\mathbb{Q}(\zeta_{2n}\sqrt[n]{n}):\mathbb{Q}]}\over{[\mathbb{Q}(\zeta_{2n})\cap\mathbb{Q}(\zeta_{2n}\sqrt[n]{n}):\mathbb{Q}]}}.$$Comparing these two expressions gives us$$[\mathbb{Q}(\zeta_{2n}\sqrt[n]{n}):\mathbb{Q}]={{[\mathbb{Q}(\zeta_{2n})\cap\mathbb{Q}(\zeta_{2n}\sqrt[n]{n}):\mathbb{Q}]\cdot n}\over{2^{\ell+1}}}.$$Polynomial $p_n(x)$ being reducible is thus equivalent to$$[\mathbb{Q}(\zeta_{2n})\cap\mathbb{Q}(\zeta_{2n}\sqrt[n]{n}):\mathbb{Q}]<2^{\ell+1}.$$Since $$2^\ell+1\ge\ell+2,$$we have$$\mathbb{Q}(\zeta_{2^{\ell+1}})\subset\mathbb{Q}(\zeta_{2^{\ell+2}})\subseteq\mathbb{Q}(\zeta_{2n})$$and also $\mathbb{Q}(\zeta_{2^{\ell+1}})\subseteq\mathbb{Q}(\zeta_{2n}\sqrt[n]{n})$ because $$\zeta_{2^{\ell+1}}={{(\zeta_{2n}\sqrt[n]{n})^{n\over{2^\ell}}}\over{a}}.$$Next, we have $\zeta_{2^{\ell+2}},\sqrt{a}\in\mathbb{Q}(\zeta_{2n})$ as explained above, and therefor $\zeta_{2^{\ell+2}}\sqrt{a}\in\mathbb{Q}(\zeta_{2n})$. Using once again $$2^\ell+1\ge\ell+2,$$it is also$$\zeta_{2^{\ell+2}}\sqrt{a}=(\zeta_{2n}\sqrt[n]{n})^{2n/2^{\ell+2}}\in\mathbb{Q}(\zeta_{2n}\sqrt[n]{n}).$$If we had $\zeta_{2^{\ell+2}}\sqrt{a}\notin\mathbb{Q}(\zeta_{2^{\ell+1}})$, then it would be$$[\mathbb{Q}(\zeta_{2^{\ell+1}},\zeta_{2^{\ell+2}}\sqrt{a}):\mathbb{Q}(\zeta_{2^{\ell+1}})]\ge2,$$and so $$[\mathbb{Q}(\zeta_{2n})\cap\mathbb{Q}(\zeta_{2n}\sqrt[n]{n}):\mathbb{Q}]\ge[\mathbb{Q}(\zeta_{2^{\ell+1}},\zeta_{2^{\ell+2}}\sqrt{a}):\mathbb{Q}]$$$$=[\mathbb{Q}(\zeta_{2^{\ell+1}},\zeta_{2^{\ell+2}}\sqrt{a}):\mathbb{Q}(\zeta_{2^{\ell+1}})]\cdot[\mathbb{Q}(\zeta_{2^{\ell+1}}):\mathbb{Q}]$$$$\ge2\varphi({2^{\ell+1}})$$$$=2^{\ell+1},$$ a contradiction. It follows$$\zeta_{2^{\ell+2}}\sqrt{a}\in\mathbb{Q}(\zeta_{2^{\ell+1}})\subset\mathbb{Q}(\zeta_{2^{\ell+2}}),$$hence $\mathbb{Q}(\sqrt{a})\subseteq\mathbb{Q}(\zeta_{2^{\ell+2}})$. But the only real quadratic subfield of $\mathbb{Q}(\zeta_{2^k})$ for $k\ge3$ is $\mathbb{Q}(\sqrt{2})$ (it also has non-real quadratic subfields $\mathbb{Q}(i)$ and $\mathbb{Q}(\sqrt{-2})$), and therefore, $\mathbb{Q}(\sqrt{a})=\mathbb{Q}(\sqrt{2})$, which by Kummer theory implies $a=2b^2$ for some $b\in\mathbb{N}$. If we had $\ell\ge2$, then it would be $$\sqrt{a}=b\sqrt{2}\in\mathbb{Q}(\zeta_8)\subseteq\mathbb{Q}(\zeta_{2^{\ell+1}}),$$and so$$\zeta_{2^{\ell+2}}={{\zeta_{2^{\ell+2}}\sqrt{a}}\over{\sqrt{a}}} \in\mathbb{Q}(\zeta_{2^{\ell+1}}),$$ which is impossible by degree comparison. Hence, finally $$\ell=1 \implies n=a^{2^\ell}=4b^4.\tag*{\square}$$

A few remarks are in order. In the case when $n=4b^4$ and $g=2$ (that is, $n$ is not a $q$th power for any odd prime $q$ dividing $b$) we have$$[\mathbb{Q}(\zeta_{2n})\cap\mathbb{Q}(\zeta_{2n}\sqrt[n]{n}):\mathbb{Q}]\ge[\mathbb{Q}(i):\mathbb{Q}]=2,$$hence$$[\mathbb{Q}(\zeta_{2n}\sqrt[n]{n}):\mathbb{Q}]={{[\mathbb{Q}(\zeta_{2n})\cap\mathbb{Q}(\zeta_{2n}\sqrt[n]{n}):\mathbb{Q}]\cdot n}\over4} \ge {n\over2}.$$This implies that the factors given by Sophie Germain's Identity are in this case irreducible over $\mathbb{Z}$ (because both factors have roots of the form $\zeta_{2n}\sqrt[n]{n}$ for some choice of primitive $2n$th root of unity $\zeta_{2n}$ since every primive $8$th root of unity is a $b^4$th power of some primitive $2n$th root of unity). However, in general, finding the factorization of $x^n\pm n$ into irreducible factors seems hard.

P.S. Looking forward to seeing you in a few days!