# Prove: $2^b-1\mid{}2^a-1 \iff b\mid{}a$ [duplicate]

I figured we'd have to show $$a=qb$$ from $$2^a-1=r(2^b-1)$$ for $$q,r\in\mathbb{Z}$$ for the first implication and vice versa, how should I proceed from here?

Hint $$:$$ $$2^{qb}-1 = (2^b -1) (2^{b(q-1)} + 2^{b(q-2)} + \cdots + 1).$$

The above hint is enough to prove that $$b \mid a \implies 2^b-1 \mid 2^a - 1.$$

To prove that $$2^b - 1 \mid 2^a - 1 \implies b \mid a$$ use division algorithm to write $$a = bq + r,$$ where $$0 \leq r < b.$$ Then we have

\begin{align} 2^a - 1 & = 2^{bq+r} - 1. \\ & = 2^{bq+r} - 2^r + 2^r -1. \\ & = 2^r (2^{bq} -1) + 2^r - 1. \end{align}

Now if $$2^b-1 \mid 2^a-1$$ then since $$2^b - 1\mid 2^r(2^{bq} -1)$$ so we have $$2^b - 1 \mid 2^r - 1,$$ which is absurd if $$0 Therefore we must have $$r=0$$ and hence we have $$a=bq.$$ Or in other words $$b \mid a,$$ as claimed.

QED

Well, if $$m=kn$$, then $$(2^m-1)/(2^n-1) = ((2^n)^k-1)/(2^n-1) = (2^n)^{k-1} +\ldots+2^n+1$$, i.e., $$2^n-1$$ divides $$2^m-1$$.

Conversely, if $$2^n-1$$ divides $$2^m-1$$, then for the Galois fields, $$GF(2^n)$$ is a subfield of $$GF(2^m)$$. Thus $$GF(2^m)$$ is a $$GF(2^n)$$-vector space and hence $$p^m = (p^n)^k$$ for some $$k\geq 1$$. Thus $$n$$ divides $$m$$. Sorry but I don't know of any pure arithmetic proof.

• I have given a pure arithmetic proof of the converse. Please verify whether it is valid or not. – Dbchatto67 Feb 18 '19 at 8:09