# What's the name of this formula? Proof solution.

I am working through the problems from the Book of Proofs. I am feeling rather dejected since after spending close to 3 hours looking at the problem unable to unlock the last step, the proof involved a formula I had never heard off.

I am wondering what's the name for the factorization method used below so that I can make sure this never happens again.

PS: My method was identical to this except I proved by case instead of in one go. The cases both are even and only one is even where relatively easy to show once I remembered that ($$a^2 - b^2$$) = (a-b)(a+b), but I then stayed there scratching, scrunching paper, pacing, and scratching some more until I realized I was probably wasting time.

• I would call this formula "difference of $n$th powers" or something like that. If you know some modular arithmetic, you can solve this question as follows: given that $n = ab$, we'll reduce $2^n - 1$ modulo $2^a - 1$. Note that we have $2^a \equiv 1$, so $2^n - 1 = (2^a)^b - 1 \equiv 1^b - 1 = 0$ modulo $2^a - 1$. So $2^a - 1$ is a factor of $2^n - 1$. This avoids the yucky formula, although it's easier to come up with if you knew the formula in the first place. Of course both solutions probably should mention that this $2^a - 1$ is a proper and nontrivial factor! Commented Apr 14, 2023 at 19:09
• I see, I am not really familiar with modulo arithmetic outside of the idea of equivalence classes, but this does make a good deal of sense. Thanks a lot for the explanation! Commented Apr 14, 2023 at 21:00

I don't know if there's a name for this method, but here's how I would remember it: for any positive integer $$a$$, the polynomial $$x^a-1$$ certainly has $$x=1$$ as a root, and therefore $$x^a-1$$ is divisible by $$x-1$$. It turns out (and is easy to check) that the quotient of those two polynomials is very nice: $$x^a-1 = (x-1)(x^{a-1} + x^{a-2} + \cdots + x^2 + x + 1).$$ In this solution, we're applying this factorization with $$x=2^b$$.
Indeed one can lift the above identity to one with two variables: $$x^a-y^a = (x-y)(x^{a-1} + x^{a-2}y + \cdots + x^2y^{a-3} + xy^{a-2} + y^{a-1}).$$ This includes the familiar difference of squares $$x^2-y^2=(x-y)(x+y)$$ as the special case $$a=2$$. When $$a$$ is odd, there's also the similar identity $$x^a+y^a = (x+y)(x^{a-1} - x^{a-2}y + \cdots + x^2y^{a-3} - xy^{a-2} + y^{a-1}),$$ where the signs in the second factor alternate. (This identity can be proved just by changing $$y$$ to $$-y$$ in the previous identity.)
The complete factorization of $$x^a-1$$ involves cyclotomic polynomials, so if you're looking for a word to attach to this factorization method, "cyclotomic" might be appropriate (although these particular identities barely scratch the surface of cyclotomic polynomials).