<s>[INST] 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:


*

*$(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 ?


*

*$(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$ ?
Thanks in advance.
 [/INST] 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}$$
</s>