3
$\begingroup$

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?

$\endgroup$
6
$\begingroup$

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<r < b.$ Therefore we must have $r=0$ and hence we have $a=bq.$ Or in other words $b \mid a,$ as claimed.

QED

| cite | improve this answer | |
$\endgroup$
2
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ I have given a pure arithmetic proof of the converse. Please verify whether it is valid or not. $\endgroup$ – Dbchatto67 Feb 18 '19 at 8:09

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