Modular arithmetic problem

Question

Here's the problem: start with $2^n$, then take away $\frac{1}{2}a^2+\frac{3}{2}a$ starting with $a=1$, and running up to $a = 2^{n+1}-2$, evaluating modulo $2^n$. Does the resulting sequence contain representatives for all the congruence classes module $2^n$?

Some examples of these sequences: \begin{align*} n=2\quad & 2,3,3,2,0,1\\ n=3\quad & 6,3,7,2,4,5,5,4,2,7,3,6,0,1\\ n=4\quad & 14,11,7,2,12,5,13,4,10,15,3,6,8,9,9,8,6,3,15,10,4,13,5,12,2,7,11,14,0,1 \end{align*}

It seems that the answer is yes but I want to show this holds for all natural numbers $n$. How does one do this?

Answer 1

This is correct. Denote $f(x)=x(x+3)/2 \pmod {2^n}$. Then $f(x)=f(y)$ if and only if $x(x+3)-y(y+3)=(x-y)(x+y+3)$ is divisible by $2^{n+1}$. Since $x-y$ and $x+y+3$ have different parity, this in turn happens if and only if one of them is divisible by $2^{n+1}$. So, if $x=1,2,\ldots,2^{n+1}$, then $f(x)$ takes each value (i.e., each residue modulo $2^n$) exactly twice, as these numbers are distinct modulo $2^{n+1}$ and are partitioned onto pairs with sum $-3$ modulo $2^{n+1}$. Two of these pairs are $(2^{n+1}-2,2^{n+1})$ and $(2^{n+1}-1,2^{n+1}-2)$, thus if you remove a number from each pair (correspondingly, $2^{n+1}$ and $2^{n+1}-1$, so that the numbers $1,\ldots,2^{n+1}-2$ remain), the remaining numbers still cover all possible values of $f$.