1
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ Is $n$ or is $k$ fixed? Is there an assumption on $a$? $\endgroup$
    – Dietrich Burde
    Jul 6, 2017 at 19:58
  • $\begingroup$ $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) $\endgroup$
    – Jason S
    Jul 6, 2017 at 20:15
  • $\begingroup$ I fixed the statement, I had incorrectly given $a^{2^k}$ rather than $a\cdot{2^k}$ $\endgroup$
    – Jason S
    Jul 6, 2017 at 20:17
  • $\begingroup$ 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" :-) $\endgroup$
    – Jyrki Lahtonen
    Jul 7, 2017 at 7:14

1 Answer 1

Reset to default
1
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$
    – Jyrki Lahtonen
    Jul 6, 2017 at 20:39
  • $\begingroup$ Oh that's an interesting insight, I hadn't realized that. $\endgroup$
    – Jason S
    Jul 7, 2017 at 14:03
  • $\begingroup$ Also thanks for the reference to cyclotomic cosets as that clarifies a number of other related questions. (hard to know what to search for if you don't know the name!) $\endgroup$
    – Jason S
    Jul 7, 2017 at 16:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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