Help learning and understanding polynomial factorizations

Question

A number theory book I'm reading used this factorization as a main step for a proof:

Given $m > n$, integers, $$\left( a^{2^{m}} - 1 \right) = \left( a^{2^{m-1}} + 1 \right)\left( a^{2^{m-2}} + 1 \right) \left( a^{2^{m-3}} + 1 \right) \cdots \left( a^{2^n} + 1 \right) \left( a^{2^n} - 1 \right)$$

Original from the book (in Portuguese):

---

I'm having a bit of trouble trying to understand how to derive it systematically (in a simple way, without lots of calculations).

If this a known common factorization? Im I missing something? If so (or not) could one suggest source to learn such factorizations?

Sorry for the possibly relatively low effort question. I just tried to find material on such factorizations and could not find.

Thanks in advance.

Answer 1

Let’s start with an example. Let $m=5,n=2$. Now, we will use the formula $$k^2-1=(k+1)(k-1)\tag{1}$$ repeatedly. We notice that $a^{2^m}=a^{2^{m-1}\cdot2}=\left(a^{2^{m-1} }\right)^2$ $$a^{2^m}-1 =\left(a^{2^{m-1} }\right)^2-1=(a^{2^{m-1}}+1) (a^{2^{m-1}}-1)$$ So $$a^{32}-1=(a^{16}+1)(a^{16}-1).$$ Using $(1)$ again, we’ll get $$a^{32}-1=(a^{16}+1)(a^{8}+1)(a^8-1).$$$$= (a^{32}+1)(a^{16}+1)(a^{8}+1)(a^4+1)(a^4-1)$$ etc. Notice that the last two terms can be written as $$(a^{2^2}+1)(a^{2^2}-1)= (a^{2^n}+1)(a^{2^n}-1) $$ for $n=2$.

As an algebraic example, as suggested by user @TomKern, $$ \bbox[5px,border:2px solid red]{(x^{16}-1)=(x^8+1)(x^8-1)=…=(x^8+1)(x^4+1)(x^2+1)(x+1)(x-1)}.$$ Thus, if $m,n\in \mathbb Z_+$, $n<m$, then we can write $$a^{2^m}-1 =\left(a^{2^{m-1} }\right)^2-1=(a^{2^{m-1}}+1) \color{blue}{(a^{2^{m-1}}-1)}$$$$= (a^{2^{m-1}}+1) \color{blue}{(a^{2^{m-2}}+1) (a^{2^{m-2}}-1)}$$$$= (a^{2^{m-1}}+1) (a^{2^{m-2}}+1) \color{red}{(a^{2^{m-3}}+1) (a^{2^{m-3}}-1)}$$ $$=…$$$$= (a^{2^{m-1}}+1) (a^{2^{m-2}}+1) (a^{2^{m-3}}+1)(a^{2^{m-3}}+1)… \color{blue}{(a^{2^{m-k}}-1)(a^{2^{m-k}}+1)} $$ where $k\in${$1,2,3,…,m-1$} so that $m-k=n$ is an integer less than $m$. This train of factors can be stopped anywhere in between, but if continued as long as possible, you’ll finish the sequence with $(a^{2^{m-1}}+1) …(2+1)(2-1)$.

---

---

One can also do this the reverse way. For eg, $$(2^{128}+1)(2^{64}+1)(2^{32}+1)…(2+1)$$$$= (2^{128}+1)…(2+1)\cdot1$$$$= (2^{128}+1)…(2+1)(2-1)$$$$= (2^{128}+1)…(2^2+1)(2^2-1)=…=2^{256}-1.$$

Answer 2

1. $(x^2 -1) = (x+1)(x-1)$

We know that through experience. We can explain it through "you see that $+$ in one term and the $-$ in the other... they cause all the middle terms in an expansion to cancel out". That is $(x+1)(x-1) = x(x-1) + 1(x-1) = x^2 \underbrace{\color{red}{- x + x}}_{\text{cancel out}} -1=x^2 -1$

1. a) so we we replace $x$ we an power, say $x^k$ then it follows that $(x^{2k}-1)= (x^k +1)(x^k-1)$. (Because $x^{2k} =(x^k)^2$ and so $((\color{green}{x^k})^2 -1) = (\color{green}{x^k} +1)(\color{green}{x^k}-1)$

2. $2^k$ is of course and even number (it is a power of two, after all). And if $2^k = 2n$ what is $n$? Well, obviously that means $n =\frac {2^k}2 = 2^{k-1}$. Increasing an exponent by $1$ will double the value and decreasing the exponent by one will have the number. This is no surprise. But what the heck does this have to do with 1. above?

3. Since $2^k$ is always even. $x^{2^k}$ must be a perfect square. And what is $\sqrt{x^{2^k}}$? Well it must be $x^{\frac {2^k}2}$. And what is $\frac {2^k}2 =2^{k-1}$ so $\sqrt{x^{2^k}} = x^{2^{k-1}}$. This might intuitively not look right because the we are so removed in exponents of exponents but it makes sense. $\sqrt{x^{2^k}} = x^{\frac {2^k}2}=x^{2^{k-1}}$. Meanwhile $\sqrt{\sqrt{x^{2^k}}} = \sqrt{x^{2^{k-1}} }= x^{2^{k-2}}$ and so on.

4. So $(x^{2^k} -1) = (x^{2^{k-1}} +1)(x^{2^{k-1}} -1)$ and as $x^{2^{k-1}}$ is also a perfect square we get:

$(x^{2^k} -1) = (x^{2^{k-1}} +1)(x^{2^{k-1}} -1)=$
$(x^{2^{k-1}} +1)(x^{2^{k-2} }+ 1)(x^{2^{k-2}}-1 =$
$(x^{2^{k-1}} +1)(x^{2^{k-2}} + 1)(x^{2^{k-3}} + 1)(x^{2^{k-3} } -1)=$
$...$
$(x^{2^{k-1}} +1)(x^{2^{k-2} }+ 1)(x^{2^{k-3}} + 1)(x^{2^{k-4}}+ 1)......(x^{2^{k-m}}+1)(x^{2^{k-m}} -1)=$
$...$
$(x^{2^{k-1}} +1)(x^{2^{k-2}} + 1)(x^{2^{k-3}} + 1)(x^{2^{k-4}}+ 1)......(x^{2^1}+1)(x^{2^{0}} +1)(x^{2^{0}}-1)=$
$(x^{2^{k-1}} +1)(x^{2^{k-2}} + 1)(x^{2^{k-3}} + 1)(x^{2^{k-4}}+ 1)......(x^{2}+1)(x +1)(x-1) $

Your result of $m>n$ that $a^{2^m} -1$ (you had a typo... you typed $a^{2^{m-1}} - 1$ instead) is just a step on the way:

$a^{2^m}-1 = (a^{2^{m-1}} +1)(a^{2^{m-1}} -1)=$
$a^{2^m}-1 = (a^{2^{m-1}} + 1)(a^{2^{m-2}}+1)(a^{2^{m-2}}-1) =$
$a^{2^m}-1 = (a^{2^{m-1}} + 1)(a^{2^{m-2}}+1)....(a^{2^{n+1}}+1)(a^{2^n} +1)(a^{2^n}-1)$.

Answer 3

These may be more familiar as factorisations of numbers consisting of repetitions of a single digit (a-1) written in base a, by splitting it in half repeatedly. Let's take base 2 (binary) to illustrate.

Let's factorise the number consisting of 16 1's.

$1111111111111111 = 100000001\times 10001 \times 101\times 11$

Starting from the end, each multiplication doubles the number of 1's.

$11\times 101=1111$ is four 1's.

$1111\times 10001=11111111$ is eight 1's.

$11111111\times 100000001=1111111111111111$ is sixteen 1's.

And so on.

In base 10, we get repetitions of the digit 9 instead.

$99\times 101=9999$ is four 9's.

$9999\times 10001=99999999$ is eight 9's.

$99999999\times 100000001=9999999999999999$ is sixteen 9's.

In general, any number consisting of a composite number of repetitions of a single digit can be factorised by splitting it into equal-sized blocks.

Answer 4

The idea is a simple tree. $$x^{2a} - 1$$ splits into (using difference of squares):

$$(x^a + 1)(x^a - 1)$$

And if $a$ is also a power of two (say, $a = 2b$), we can repeat the difference of squares on the 2nd part:

$$(x^{2b} + 1)(x^{2b} - 1)$$

$$(x^{2b} + 1)(x^{b} + 1)(x^{b} - 1)$$

or, in short:

$$x^{4b}-1 = (x^{2b} + 1)(x^{b} + 1)(x^{b} - 1)$$ We can repeat this as many times as we want for every power or two, if $a=c2^k$, each time splitting the difference of squares of the $x^z - 1$ term into $(x^{z/2}+1)(x^{z/2}-1)$, until we can't divide it further:

$$x^{c2^k}-1 = (x^{c2^{k-1}} + 1)(x^{c2^{k-2}} + 1)...(x^{c2^1}+1)(x^{c2^0}+1)(x^{c2^0} - 1)$$

To formally prove this is true, you'd probably end up doing an induction argument.

We then just have to set $c=2^n$ for some $n$, and $m = n+k$, and the result follows.