12
$\begingroup$

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

$\endgroup$
  • $\begingroup$ If $p$ is a polynomial with integer coefficients and $a,b$ are distinct integers, $(a-b)\mid\left(p(a)-p(b)\right)$. In particular $(a^n-1)\mid (a^{nm}-1)$, which is trivial by polynomial division, too. $\endgroup$ – Jack D'Aurizio Jan 29 '18 at 16:17
29
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ Which proves that if M = 2^p - 1 is a Mersenne prime, then p must be prime too. Example: 127 = 2^7 - 1 is prime, and so is 7. 7 = 2^3 - 1 is prime, and so is 3 = 2^2 - 1, and so is 2. $\endgroup$ – Timmos Jan 30 '18 at 13:51
  • $\begingroup$ Yes, that is correct. $\endgroup$ – Maria Mazur Jan 30 '18 at 13:51
31
$\begingroup$

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}$$

$\endgroup$
  • $\begingroup$ Excellent argument and visualization. Thanks! $\endgroup$ – Eric Duminil Jan 30 '18 at 11:24
  • $\begingroup$ That is some great insight and excellent use of binary. $\endgroup$ – Timmos Jan 30 '18 at 13:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.