Resource for finding proof (h'k + 1 + 2 + 3...+m-1) % m for m power of 2 visits every modulus slot

Question

I have tried do this modulus question where we need to prove that for m is power of 2 if we start with some random number % m = h'k and then do (h'k + 1) % m, (h'k + 1 + 2) % m,... (h'k + 1 + 2 + 3...+m-1) % m will visit every number [0...m-1] only one time. Are they any resources, series, how I can prove this? I don't want to use induction as I feel like it is really mathematically sound proof for this problem.

Answer 1

I also don't think induction would be a good way to prove this since there's no easy way which I can see to relate the results from one power of $2$ to the next power of $2$. Instead, let $m = 2^n$ for $n \ge 1$, $r = h'k$ and

$$a_i = r + \sum_{k=0}^{i}k, \; 0 \le i \le m - 1 \tag{1}\label{eq1}$$

Next, consider integers $i,j$ with $0 \le i, j \le m - 1$ and $j \gt i$, with

$$\begin{equation}\begin{aligned} a_j - a_i & = (r + \sum_{k=0}^{j}k) - (r + \sum_{k=0}^{i}k) \\ & = \sum_{k=i+1}^{j}k \\ & = \frac{(j-i)((i+1) + j)}{2} \end{aligned}\end{equation}\tag{2}\label{eq2}$$

In the last step, I used the arithmetic progression sum formula. If $i,j$ are both even or both odd, then $j - i$ is even, but it's less than $m = 2^n$ so it has less than $n$ factors of $2$, and $(i+1) + j = (i+j) + 1$ is odd so it has no factors of $2$, meaning the value in \eqref{eq2} has less than $n$ factors of $2$ and, thus, can't be $\equiv 0 \pmod m$. Next, consider one of $i,j$ to be odd and the other even. Then $j - i$ is odd, with $(i + 1) + j$ being even. However, note that $(i + 1) + j \le ((m - 1) + 1) + (m - 1) = 2m - 1 \lt 2^{n+1}$. This means it has at most $n$ factors of $2$, so when divided by $2$, the result in \eqref{eq2} has at most $n-1$ factors of $2$ and, thus, the value in \eqref{eq2} also can't be $\equiv 0 \pmod m$.

This shows the result in \eqref{eq2} cannot be $\equiv 0 \pmod m$, so each of the $m$ values of $a_i$ for $0 \le i \le m - 1$ must have a unique result $\pmod m$. As there's only $m$ available residues $\pmod m$ of $0$ to $m-1$, inclusive, this means the $a_i$ must take on each of the values in $[0,m-1]$ exactly one time in some order.