Does there always exist an odd number of elements? Given a nonzero integer $k$, does there always exist a positive integer $n$ such that there are exactly an odd number of elements $i\in\{0,1,...,n-1\}$ with $\frac{2^n-1}4 < 2^ik \mod{2^n-1} < \frac{3(2^n-1)}4$? Here $a\mod b\in\{0,1,...,b-1\}$.
 A: Taking $k = 2$ seems to be an exception. For $n \geq 3$ we have the following:


*

*For $0 \leq i < n-3$ we have $2^i k = 2^{i+1} < 2^{n-3} < \frac{1}{4}(2^n - 1)$ and hence $2^i k$ is not in the desired range. 

*For $i = n-3$ we have $2^i k = 2^{n-2} = \frac{1}{4}2^n > \frac{1}{4}(2^n - 1)$ which is just in the desired range.

*For $i = n-2$ we have $2^i k = 2^{n-1} = \frac{1}{2}2^n$ which is also in the desired range.

*For $i = n-1$ we have $2^i k = 2^n \equiv 1$ which is not in the desired range.


So for any $n \geq 3$, the number of elements $i \in \{0, \ldots, n-1\}$ satisfying $$\frac 14 (2^n-1) < \left(2^ik \mod{2^n-1}\right) < \frac 34 (2^n-1)$$ is exactly $2$, which is even. 
For $n = 2$ we have a lower bound of $3/4 < 1$ and upper bound of $9/4 > 2$, in which case both $i = 0$ and $i = 1$ satisfy the equation. So again, the number of elements is even.
Finally, for $n = 1$ we have a lower bound of $1/4$ and upper bound of $3/4$, and no integer is in this range. So again, the number of elements satisfying the requirement is even.
Concluding, $k = 2$ seems to be a counterexample.
