# Splitting polynomials

I have a polynomial ${\frac{{{{({z^2})}^p} \pm {p^p}}}{{{z^2} \pm p}}}$ where $p$ is an odd prime number, and I know it splits into two factors $$\sum_{i = 0}^{p - 1} a_i z^i \text{ and } \sum_{i = 0}^{p - 1} ( - 1)^i a_i z^i$$

For example, when $p=5$ $$\begin{eqnarray*} \frac{x^{10}-5^5}{x^2-5} &=& x^8+5x^6+25x^4+125x^2+625\\ &=& (x^4 + 5x^3+15x^2+25x+25)(x^4-5x^3+15x^2-25x+25) \end{eqnarray*}$$ Does anyone know a nice method for determining these two factoring polynomials?

-
Does the choice of sign depend on the residue class of $p$ modulo $4$? – Jyrki Lahtonen May 17 '12 at 11:07
The factorization exists, iff the sign is equal to $(-1)^{(p-1)/2}$. Given that, one factor is $$\prod_{j=1}^{p-1}\left(x-\left(\frac k p \right)\zeta_p^k\sqrt{p*}\right),$$ where $\zeta_p=e^{2\pi i/p}$, $p^*=(-1)^{(p-1)/2}p$ and $(\frac k p )$ is the Legendre symbol. The other factor is gotten by switching the signs of the zeros. But I guess you knew that, and would like to see a closed formula for the coefficients :-) – Jyrki Lahtonen May 17 '12 at 11:39
Do you have any other examples? – lhf May 17 '12 at 11:48
@lhf, Also sprach Mathematica: For $p=7$ we get $$x^{14}+7^7=\left( 7 + {x^2} \right) \, \left( 343 - 343\,x + 147\,{x^2} - 49\,{x^3} + 21\,{x^4} - 7\,{x^5} + {x^6} \right) \, \left( 343 + 343\,x + 147\,{x^2} + 49\,{x^3} + 21\,{x^4} + 7\,{x^5} + {x^6} \right)$$ and for $p=3$ $$x^6+3^3=\left( 3 + {x^2} \right) \, \left( 3 - 3\,x + {x^2} \right) \, \left( 3 + 3\,x + {x^2} \right).$$ – Jyrki Lahtonen May 17 '12 at 11:57
I can't help thinking this is related to the Aurifeullian factorizations. See, e.g., mathworld.wolfram.com/AurifeuilleanFactorization.html, although I think there's more to Aurifeullian factorization than what's to be found at that site. – Gerry Myerson May 17 '12 at 12:43

Here is the solution I found, which to me is unsatisfactory.

This solution uses Table 24 from Riesel’s “Prime Numbers and Computer Methods for Factorization”. Look up the number you are interested in in the n column, and note down the two sets of coefficients given there: they are $U_n(x)$ and $V_n(x)$. Multiply each coefficient in $U_n(x)$ by $p^0$, $p^1$, $p^2$, …, $p^{p-1}$, and those in $V_n(x)$ by $p^1$, $p^2$, … $p^{p-1}$. Then take a coefficient from each list alternately and you have your factor. Do the same for the other factor after multiplying $V_n(x)$ by $-1$.

Example for $p=11$:
$U_n(x)=1, 5, -1, -1, 5, 1$
$V_n(x)=1, 1, -1, 1, 1$
Multiplying by powers of $11$:
$U_n = 1, 55, -121, -1331, 73205, 161051\\ V_n = 11, 121, -1331, 14641, 161051$
Taking the coefficients one at a time from each list one factor is $$x^{10} + 11x^9 +55x^8 +121x^7 -121x^6 -1331x^5 -1331x^4 +14641x^3 +73205x^2 +161051x +161051$$ and the other factor is

$$x^{10} - 11x^9 +55x^8 -121x^7 -121x^6 +1331x^5 -1331x^4 -14641x^3 +73205x^2 -161051x +161051$$

-
Can you prove that this works in general? – lhf May 18 '12 at 10:52
There is clearly a connection with the factorization cyclotomic polynomials over $\mathbb Z$ because if you set $z=\sqrt{p}w$ then your polynomials are $p^{p-1}\dfrac{(w^2)^p\pm1}{w^2\pm1}$. It seems that $\Phi_p(x^2)$ can be further factorized than $\Phi_p(x)$. See mathworld.wolfram.com/CyclotomicPolynomial.html , eq 17 and 37. – lhf May 18 '12 at 11:02
I think I could prove it if I put my mind to it. Howeveer, I'm not too bothered, as this is not the solution I'm looking for. (Maybe what I'm looking for is unobtainable). Your second comment here mirrors what's in Paul Garrett's paper. See my comments to the next solution. – BudgieJane May 18 '12 at 21:50

Here is a follow-up from my comment, but unfortunately it does not work. Since it is too long for a comment, I leave it here as an answer.

Set $z=\lambda x$, where $\lambda= \sqrt{p}$ for convenience. Then your polynomials are $p^{p-1}\dfrac{(x^2)^p\pm1}{x^2\pm1}$.

Now $(x^2)^p-1=x^{2p}-1=\Phi_{2p}(x)\Phi_p(x)\Phi_2(x)\Phi_1(x)=\Phi_p(-x)\Phi_p(x)(x^2-1)$, where $\Phi_n$ is the $n$-th cyclotomic polynomial.

Then $p^{p-1}\dfrac{((x^2)^p-1)}{x^2-1}=\lambda^{2p-2}\Phi_p(-x)\Phi_p(x)=(\lambda^{p-1}\Phi_p(-x))(\lambda^{p-1}\Phi_p(x))=Q(-z)Q(z)$, where $Q(z)=\lambda^{p-1}\Phi_p(x)=\lambda^{p-1}\Phi_p(z/\lambda)$.

This is the correct form from the original observations. Unfortunately, $Q$ does not have integer coefficients. The factorization obtained for the case $p=5$ does not come from this one. And there goes my idea...

Edit: I've now found that all this is discussed on page 6 of these notes by Paul Garrett. I think this is the best answer to the question.

-
+1 While playing, I got the impression that this has to with the factorization of $\Phi_{2p}(x)$ over the unique quadratic intermediate field $\mathbb{Q}(\sqrt{p^*})$. Have you ever seen that? – Jyrki Lahtonen May 18 '12 at 16:28
@lhf: My original question was motivated by Paul Garrett's paper, which is why I'm looking for a different sort of solution. I admit that what I'm looking for may be unobtainable, but I figure there's no harm in looking. – BudgieJane May 18 '12 at 21:58
@Jyrki: Yes, and lhf seems to be suggesting that too. – BudgieJane May 18 '12 at 21:58
@BudgieJane, you might have mentioned Garrett's paper... – lhf May 19 '12 at 0:58