2
$\begingroup$

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.

Pain

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.

$\endgroup$
2
  • $\begingroup$ 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! $\endgroup$ Commented Apr 14, 2023 at 19:09
  • $\begingroup$ 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! $\endgroup$
    – Solar
    Commented Apr 14, 2023 at 21:00

1 Answer 1

3
$\begingroup$

Don't feel bad—in this particular proof, that particular formula is more than half the solution! This is a hard solution to come up with without having seen it (or something very similar to it) before.

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

$\endgroup$
1
  • $\begingroup$ I see, this actually makes a lot of sense. Thanks a lot for taking the time to write this! :D $\endgroup$
    – Solar
    Commented Apr 14, 2023 at 20:39

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .