# If $a$ divides $b$, then $(2^a-1)$ divides $(2^b-1)$ [duplicate]

This question already has an answer here:

Prove that if $a \mid b$, then $(2^a-1) \mid(2^b-1)$.

So, I've said the following:

1. Let $a \mid b$.
2. $\implies b=am$
3. Assume $(2^a-1) \mid (2^b-1)$
4. $\implies (2^b-1)=(2^a-1)x$

But I can't figure out what to do with any of this from here forward.

## marked as duplicate by user147263, Jyrki LahtonenDec 3 '15 at 11:00

• Why are you assuming that $(2^a - 1)|(2^b-1)$? – The Chaz 2.0 Nov 10 '13 at 2:02
• Do you know the usual factorization of $x^n-y^n$ ? – chubakueno Nov 10 '13 at 2:03
• "proofs" is a pretty vast subject to be looking for a single "rule of thumb" – Jack M Nov 10 '13 at 11:35

HINT: Sometimes choosing the ‘right’ representation makes things easier to see. Note that the binary (base two) representation of $2^n-1$ is

$$\underbrace{111\ldots 111}_{n\text{ ones}}\;.$$

Suppose that $b=ka$; then

\begin{align*} \underbrace{111\ldots111}_{b\text{ ones}}&=\underbrace{\underbrace{111\ldots 111}_{a\text{ ones}}\underbrace{111\ldots 111}_{a\text{ ones}}\ldots\underbrace{111\ldots 111}_{a\text{ ones}}}_{k\text{ blocks}}\\\\ &=\left(\underbrace{111\ldots 111}_{a\text{ ones}}\right)\left(\underbrace{1\underbrace{000\ldots000}_{a-1\text{ zeroes}}1\underbrace{000\ldots000}_{a-1\text{ zeroes}}1\ldots1\underbrace{000\ldots000}_{a-1\text{ zeroes}}1}_{k\text{ ones}}\right)\;. \end{align*}

For example, with $a=3$ and $b=12$, we have

$$111111111111=111\cdot1001001001\;.$$

These ideas can be translated into statements about sums of powers of $2$.

When you have a statement you are trying to prove, such as "if $p$, then $q$", you can assume $p$ is true, and then show that $q$ must also be true. This is called a direct proof.

Alternatively, you can assume $q$ is not true, and show that this means $p$ cannot be true. This is called a proof by contradiction.

You are assuming both $p$ and $q$ are true. You should pick one of the two strategies I mentioned above. I would suggest a proof by contradiction in this particular case.

• I would rather go for a direct proof in this case (it lends itself) – chubakueno Nov 10 '13 at 2:13

Suppose $a\mid b$ and so $b=am$ for some $m\geq 1$. Then, $$2^b-1=2^{am}-1=(2^a)^m-1^m\\=(2^a-1)\left((2^a)^{m-1}+(2^a)^{m-2}+\cdots+(2^{a})^2+(2^a)+1\right).$$ We see that $(2^a)^{m-1}+(2^a)^{m-2}+\cdots+(2^{a})^2+(2^a)+1\geq 1$ and so $2^b-1=(2^a-1)k$ for some $k\geq 1$. Hence $2^a-1\mid 2^b-1$.

Remember, it's very easy to begin circular reasoning if you're not careful when you assume a result that you're trying to prove. It's much more conventional (especially when first learning proofs) to reach that result by deducing it from the hypotheses in the statement - in this case $a\mid b$.

• I wouldn't say you can't in the general case. You can connect the result by $\iff$'s to a true statement, and you have a proof. – chubakueno Nov 10 '13 at 2:15
• @chubakueno but then that's not assuming the result, that's setting up a chain of equivalences. I think, especially when you're first learning about logical implication, and proofs in general, it's best to move away from the habit of using chains of equivalences until you fully understand how to prove something in one direction, and more importantly what it means for one statement to imply another. – Dan Rust Nov 10 '13 at 2:24
• Yes, I know it may cause problems for starters. But working backwards may help to get better, easier or shorter proofs, and it should never be forbidden :) – chubakueno Nov 10 '13 at 2:30
• @chubakueno True, I've changed the advice to reflect this :). – Dan Rust Nov 10 '13 at 2:35
• Often there is not a chain of equivalences connecting $A$ and $B$. So the sooner high school habits are dropped the better. – André Nicolas Nov 10 '13 at 2:52