A factoring trick

In Matt Parker’s latest video, he gives two proofs to show that if you

you’ll get a number that is a multiple of your original number minus one. In words, this seems magical; in equation form,

b n1=(b1)(something)

not so much. Certainly you know that

b 21=(b1)(b+1)

because that comes up so often. You may also remember from algebra class that

b 31=(b1)(b 2+b+1)

So it isn’t tremendously surprising to hear that b1 is a factor no matter what n is. But what’s the proof?

Matt’s first proof is to notice that b=1 is a solution to

b n1=0

for any n. Therefore, (b1) has to be one of the factors of b n1. He considers this a rather prosaic proof, and quickly moves on to the fun one, which involves expressing the numbers in different bases. It is a cute proof, and you should watch the video to see it.

But I wanted to go back to

b n1=(b1)(something)

and see if there’s a solution for something that works for every n. Obviously there is, or I wouldn’t have written this post. And you’ve probably already guessed what that solution is, but let’s figure it out systematically.

We’ll set up the polynomial division of b n1 by b1 and run it out for a few steps:

Polynomial division

As you can see, after Step m in the process, the difference (i.e., the expression under the horizontal line) is

b nm1

So after m=n1 steps, the difference will be b1, which means that the last term in the quotient will be +1 and there will be no remainder. Therefore, something is

b n1+b n2++b+1= m=0 n1b m

which is easier to remember than I would have guessed.