# 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.

• Is $n$ or is $k$ fixed? Is there an assumption on $a$? Jul 6, 2017 at 19:58
• $n$ is fixed (I added that to the problem statement). No restrictions on $a$. (other than $n$ is a positive integer and $k, a$ are nonnegative integers) Jul 6, 2017 at 20:15
• I fixed the statement, I had incorrectly given $a^{2^k}$ rather than $a\cdot{2^k}$ Jul 6, 2017 at 20:17
• It seems to me that your argument is correct. My answer is just another way. Yours actually needs less lines, mine may be "visually clearer" :-) Jul 7, 2017 at 7:14

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.

• Doing this for the example you found when $n=6$ and $a=2^6-2=111110_2$. The other elements in that cycle are $2^6-3=111101_2$, $2^6-5=111011_2$, $2^6-9=110111_2$, $2^6-17=101111_2$ and $2^6-33=011111_2$. You see how that single zero moves forward one position each time we increase the exponent by one. Jul 6, 2017 at 20:39