Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

Thanks in advance.

share|improve this question

4 Answers 4

up vote 7 down vote accepted

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}$$

share|improve this answer

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$.

share|improve this answer

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$.

share|improve this answer

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$.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.