proving that the cycle $\{a\cdot{2^k} \bmod 2^n-1\}$ has a minimum element $b <2^{n-1}$ Is it possible to prove that the cycle $\{a\cdot{2^k} \bmod 2^n-1 \} $ (for fixed $n$) always has a minimum element $b \leq B$ where $B=2^{n-1} - 1$? This appears to be the case.
I know $B$ can't be any smaller, since by construction the cycle $\{2^n-2, 2^n-3, 2^n-5, 2^n-9, \ldots 2^n-2^k-1, \ldots 2^{n-1} - 1\}$ has a minimum value of $2^{n-1} - 1$, but I'm not sure if there exists a cycle with a larger minimum bound.

Presumably if there were, and it had a minimum value $b$ with $2^n - 1 > b > 2^{n-1}$,


*

*then $b = (2^n - 1) + b'$ where $-2^{n-1} < b' < 0$

*and $-2^n < 2b' < b'$

*so $c = 2b \bmod (2^n-1) = 2b' + (2^n-1) < b' + (2^n-1) = b$ which yields a smaller value $c$ in the cycle.


But I'm not sure my proof above holds water.
 A: This becomes obvious if you think about in terms of the base-2 expansions of the residues of the numbers $a\cdot 2^k$ modulo $2^n-1$.
Write $a$ in base two. Without loss of generality $a<2^n-1$. We can extend the binary expansion to $n$ bits by padding it with an appropriate number of leading zeros.
The key is the following
Observation. If
$$
a=b_{n-1}b_{n-2}\cdots b_2b_1b_0
$$
is the binary expansion of $a$, then the binary expansion of the remainder of $2a$ (modulo $2^n-1$) is gotten by rotating this one position to the left. In other words
$$
2a\equiv b_{n-2}b_{n-3}\cdots b_1b_0b_{n-1}\pmod{2^n-1}.
$$
The proof is easy. We have $b_{n-1}\equiv 2^n b_{n-1}\pmod{2^n-1}$, so the integer on the right is congruent to $2a$ modulo $2^n-1$. Because $a<2^n-1$ at least one of the bits $b_i$ is equal to zero. Therefore this integer is also $<2^n-1$, so it is the remainder of $2a$ divided by $2^n-1$.

The main claim follows from this as follows. By repeating the observation we see that the remainders of the integers $a\cdot 2^k, k=0,1,2\ldots,n-1$, are exactly the $n$ different cyclic shifts of $a$. Whenever we increase $k$ by one, we apply the observation to get the next remainder.
As one of the bits $b_i$ is zero, all we need to do is to rotate that zero to become the most significant bit. That particular rotation then represents an integer $<2^{n-1}$ as claimed.

Read about cyclotomic cosets to learn more.
