# Factorization of sum of two square

The difference is $a^2 - b^2 = (a - b).(a + b)$

But what about when I have $a^{25} + 1$ ? According to wolfram alpha, the alternate form is:

1. $(a+1) (a^4 -a^3 + a^2 -a + 1)( a^{20} - a^{15} + a^{10} -a^5 +1)$

However, the square root of 25 is a rational number 5.

But If I had 50, where the square root of 50 is irrational ?

1. $(a^2 + 1) (a^8 -a^6 +a^4 -a^2 +1) (a^{40} -a^{30} +a^{20} -a^{10} +1 )$

In fact, I'm just wondering and trying to find out patterns, I'm very curious about that, since I haven't found anything related, only the alternate forms generated by wolfram. My question is how and what mathematical algorithm they used to find $k$ forms for $a^n + 1$ ?

Such factorizations are special cases of general formulas for factorizations of cylotomic polynomials, e.g. see wikipedia. These formulas follow by Möbius inversion.

Such polynomial factorizations come in handy for integer factorization. For example, Aurifeuille, Le Lasseur and Lucas discovered so-called Aurifeuillian factorizations of cyclotomic polynomials $\rm\;\Phi_n(x) = C_n(x)^2 - n\ x\ D_n(x)^2\;$. These play a role in factoring numbers of the form $\rm\; b^n \pm 1\:$, cf. the Cunningham Project. Below are some simple examples of such factorizations:

$$\begin{array}{rl} x^4 + 2^2 \quad=& (x^2 + 2x + 2)\;(x^2 - 2x + 2) \\\\ \frac{x^6 + 3^2}{x^2 + 3} \quad=& (x^2 + 3x + 3)\;(x^2 - 3x + 3) \\\\ \frac{x^{10} - 5^5}{x^2 - 5} \quad=& (x^4 + 5x^3 + 15x^2 + 25x + 25)\;(x^4 - 5x^3 + 15x^2 - 25x + 25) \\\\ \frac{x^{12} + 6^6}{x^4 + 36} \quad=& (x^4 + 6x^3 + 18x^2 + 36x + 36)\;(x^4 - 6x^3 + 18x^2 - 36x + 36) \\\\ \end{array}$$

If $n$ is odd then the polynomial $p(x)=x^n+1$ has a zero at $x=-1$, $p(-1)=(-1)^n+1=-1+1=0$. By the factor theorem, $x+1$ is therefore a factor of $p(x)$. Using polynomial long division (or synthetic division) you can show that $x^n+1=(x+1)(x^{n-1}-x^{n-2}+x^{n-3}-\cdots-x+1)$.

For example, consider $p(x)=x^5+1$. By the above, since $5$ is odd, $p(x)=(x+1)(x^4-x^3+x^2-x+1)$. Next notice that

\begin{align*}x^{25}+1&=(x^5)^5+1=p(x^5)\\ &=(x^5+1)((x^5)^4-(x^5)^3+(x^5)^2-x^5+1)\\ &=(x+1)(x^4-x^3+x^2-x+1)(x^{20}-x^{15}+x^{10}-x^5+1).\end{align*}

Finally, notice that $x^{50}+1=(x^2)^{25}+1=p((x^2)^5)$, so you can just substitute $x^2$ for $x$ in the factorization of $x^{25}+1$.

There is a Wikipedia article about algorithms for factoring polynomials. For the special case of polynomials of the form $a^n + 1$ the factors will be cyclotomic polynomials: more precisely,

$$a^n + 1 = \prod_{d | 2n, d \nmid n} \Phi_d(a).$$

For $n = 25$ the corresponding values of $d$ are $d = 2, 10, 50$, and for $n = 50$ the corresponding values of $d$ are $d = 4, 20, 100$.

Let $z=\mathrm{e}^{\mathrm{i}\pi/n}$, hence $z^n=-1$ and $z^{2k}$ from $k=1$ to $k=n$ are the $n$th roots of $1$. Then $a^n+1=a^n-z^n$ is the product of $a-z^{2k+1}$ from $k=1$ to $k=n$. One recovers a factorization on the real numbers by multiplying the $k$ term with the $n-k-1$ term for every $k\ne(n-1)/2$, since $(a-z^{2k+1})(a-z^{2n-2k-1})=a^2-2\cos((2k+1)\pi/n)a+1$.