# Factoring $x^n + y^n$ over the integers

Here's what i know (or think i know) about the factoring.

For integer $n> 1$

1) If $n$ is a positive power of $2$ then it is irreducible.

2) If $n$ is an odd prime then $$x^n + y^n = (x + y)(x^{n-1} - x^{n-2}y + \cdots - xy^{n-2} + y^{n-1} )$$

3) If $n$ has an odd prime factor then it is factorable but the factorization is more complicated , for example $x^{14} + y^{14}$ has 2 distinct irreducible factors and $x^{15} + y^{15}$ has $4$ distinct irreducible factors.

Is there a connection between the prime factorization of $n$ and the number of distinct irreducible factors of $x^n + y^n$ ?

Is there a connection between $n$, AND the number of distinct irreducible factors , AND the highest power occurring in each factor? Example:

$$x^{15} + y^{15} = (x + y)(x^2 - \cdots)(x^4 - \cdots)(x^8 + \cdots)$$

In other words , i'm also asking if there is a connection between $n = 15$ , the number of factors $4$ , and the powers $\{1 , 2 , 4 , 8\}$

For this particular example the numbers work out nicely but i'm not sure the pattern is so obvious in general.

Thank you for your consideration in this matter.

-
I think you are looking for factorization over the rationals (or integers). The Wikipedia article on cyclotomic polynomials may be useful. –  André Nicolas Mar 1 at 18:14
Thanx for the wiki link. You are mostly right about the integer part but i have derived some factorizations like $$x^4 + 1 = (x^2 + \sqrt{2}x + 1)(x^2 - \sqrt{2}x + 1)$$ This example is the simplest that comes to mind but there are many others. I get the feeling that root 2 somehow disqualifies this as a legitimate factorization but i'm not sure exactly why. That is why i asked over the reals , to allow these kind of factorings but they may be inappropriate , i don't know. :) –  neofoxmulder Mar 1 at 19:33
Over the reals things are simple, since $x^n+y^n$ factors as a product of polynomials that are of degree at most $2$. All of degree $2$ if $n$ is even, all but one of degree $2$ if $n$ is odd. –  André Nicolas Mar 1 at 19:38

Since we have this factorisation, we need to know in what minimal way we need to combine the $n$th roots of unity so that we have a polynomial over the integers again. Well, if we multiply together all the primitive $d$th roots of unity terms for all $d\mid n$, that's what we want. There are $\phi(d)$ primitive $d$th roots of unity.

Hence you will have $\#\{1\leq d<n:d\mid n\}$ irreducible factors of degrees $\phi(d)$.

In your case, we have $1,3,5,15\mid 15$, and $\phi(1)=1,\phi(3)=2,\phi(5)=4,\phi(15)=8$.

-
Thanx for the answer and the link both are very helpful. I applied your method to $x^{35} + y^{35}$ and was able to make it work so i'm glad i understand it. :) –  neofoxmulder Mar 1 at 19:05
Things work nicely for $n$ odd, since we are essentially dealing with $t^n-1$. There are some complications for even $n$. –  André Nicolas Mar 1 at 19:43
@AndréNicolas , Oh? can you give a numerical example of even n so i could try and work it out to see what happens? –  neofoxmulder Mar 1 at 20:05
Do you just want an even number or do you want a worked example? –  Ian Coley Mar 1 at 20:07
@IanColey , i tried $$x^{14} + y^{14}$$ but your algorithm doesn't seem to work , unless WA is incorrect. wolframalpha.com/input/?i=factor%28x%5E14+%2B+y%5E14%29 Note: I am not trying to factor these by hand , plug and play using CAS. :) –  neofoxmulder Mar 1 at 20:26

Is there a connection between $n=15$, the number of factors $4$, and the powers $\{1,2,4,8\}$

For $n=2^{2^k}-1=\displaystyle\sum_{j=0}^{2^k-1}2^j$ , we have $\dfrac{x^n+y^n}{x+y}=\dfrac{x^{2^{2^k}-1}+y^{2^{2^k}-1}}{x+y}=\displaystyle\prod_{j=1}^{2^k-1}\Big(x^{2^j}\pm\ldots\Big)$. Here, $k=2$, and $n=15$. The cases $k<4$ are less than a few lines in length, while $k=4$ occupies about $40$ screens of resolution $1366\times768$. :-)

-
I had a feeling n = 15 = 16 - 1 was special , thanx. These formulas are beautiful :) –  neofoxmulder Mar 1 at 20:12