Factor of a Mersenne number [duplicate]

Why is it true that if 7 divides 91 then $(2^7-1) $ divides $(2^{91}-1)$?

1) $2^{91}-1$

$7|91 \implies (2^7-1)|(2^{91}-1)$

$\implies 2^7-1$ is factor

2) $2^{1001}-1$

$7|1001 \implies (2^7-1)|(2^{1001}-1)$

$\implies 2^7-1$ is factor

Solution 1:

It may be illustrative to write the numbers out in binary. I'll use $2^{21} - 1 = (2^7)^3 - 1$ instead of $2^{91} - 1$, since it's shorter:

$$\begin{aligned} 2^{21} - 1 &= \underbrace{111111111111111111111}_{21\text{ digits}}\,\vphantom1_2 \\ &= \underbrace{1111111}_{7\text{ digits}}\,\underbrace{1111111}_{7\text{ digits}}\,\underbrace{1111111}_{7\text{ digits}}\,\vphantom1_2 \\ &= 1111111_2 \times 100000010000001_2 \\ &= (2^7 - 1) \times (2^{14} + 2^7 + 1). \end{aligned}$$

Solution 2:

We have $$2^{91}-1 = (2^7)^{13}-1 = (2^7-1)((2^7)^{12}+...+2^7+1)$$

More generally:

$$2^{ab}-1 = (2^a)^{b}-1 = (2^a-1)((2^a)^{b-1}+...+2^a+1)$$

so $2^a-1\mid 2^{ab}-1$

And we can replace $2$ with any other number.