Factor $10^n -1$

Question

There is an identity or quick way to factor problems of the form $c^x -1$ e.g. $10^n-1$, what is it?

I mean that it can be represented in some way as multiple factors,e.g. $(x-a)(y-b)$, there is a way to expand the difference easily.

Answer 1

Okay so I did find something interesting after my rambling in the comments. It comes from here.

Suppose we have a difference of two $(n+1)$-th powers, $(x^{n+1} - y^{n+1})$. Then

$$(x^{n+1} - y^{n+1}) = (x-y)(x^n + x^{n-1}y + x^{n-2}y^2 + ... + xy^{n-1} + y^n)$$

Take $y=1$ as in your case, OP. Then $y^n = 1$ for all $n$ and

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

More compactly,

$$(x^{n+1} - 1) = (x-1)\left( \sum_{k=0}^n x^k \right)$$

We make the assumption that $n$ is a positive integer, by the way, and $x,y$ are real numbers.

The summation won't be factorable in any meaningful way, though, at least as far as I know. For example, consider $n=2$. Then,

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

We can't really factorize the quadratic on the right meaningfully without also solving for its roots, which I feel kinda defeats the purpose of this. Especially since, for I think it's fifth degree polynomials onwards, we can't solve for the roots easily, unlike the cubic/quadratic formulas.

That's not to say that the quadratic won't be factorizable for specific $x$. For example, I made WolframAlpha calculate the value of the quadratic for $x = 1, 2, 3, ..., 100$ and we see some composite numbers there. So there might be more to be said when it comes to factorizing in specific instances of $(x^3 - 1)$, for example, but not much in general.

Answer 2

Note that $a^n-b^n$ is a multiple of $a⁻b$. And if $n$ is eben, then also $a+b\mid a^n-b^n$ Hence for any $d\mid n$, $10^d-1$ divides $10^n-1$; and if $n/d$ is even, also $10^d+1$ divides $10^n-1$

Answer 3

Since it’s subtraction, you could use the difference of two squares I suppose.

$$a^2-b^2 = (a+b)(a-b) \implies a^c-b^c = \big(a^{\frac{c}{2}}+b^{\frac{c}{2}}\big)\big(a^{\frac{c}{2}}-b^{\frac{c}{2}}\big)$$

In this case, you have $b = 1$, so the factorization is $$\big(c^{\frac{x}{2}}+1\big)\big(c^{\frac{x}{2}}-1\big) \implies (10^5+1)(10^5-1)$$

A more commonly used idea is factoring the difference of $n^{th}$ powers for all $n$ and the sum of $n^{th}$ powers for all odd $n$ (which isn’t relevant but is very similar to the former).

$$a^n-b^n = (a-b)(a^{n-1}+a^{n-2}b+a^{n-3}b^2+…+a^2b^{n-3}+ab^{n-2}+b^{n-1})$$

This works because through expansion because multiplying $a$ to each term is canceled by multiplying $b$ to the term before it, which leaves only the first term for $a$ and the last term for $b$.

$$ = \underbrace{a^n\color{blue}{+a^{n-1}b+a^{n-2}b^2+…+a^3b^{n-3}+a^2b^{n-2}+ab^{n-1}}}_{a(a^{n-1}+a^{n-2}b+…+ab^{n-2}+b^{n-1})}\underbrace{\color{red}{-a^{n-1}b-a^{n-2}b^2-a^{n-3}b^3-…-a^2b^{n-2}-ab^{n-1}}-b^n}_{-b(a^{n-1}+a^{n-2}b+…+ab^{n-2}+b^{n-1})}$$

$$= a^n-b^n$$

So, for instance, you can factor your example as follows:

$$10^n-1 = (10-1)(10^{n-1}+10^{n-2}+10^{n-3}+…+1)$$

which also bears striking resemblance to the geometric series if written as $\frac{10^n-1}{10-1} = 1+10+10^2+…+10^{n-1}$.

As a side note, you can use

$$(a+b)(a^{n-1}-a^{n-2}b+a^{n-3}b^2-a^{n-4}b^3+…+b^{n-1})$$

to factor the sum of $n^{th}$ powers, but this only works for an odd $n$.