<s>[INST] Show ${\pm 3^i}, 1\leq i \leq 2^{n-2}$ is reduced residue system mod $2^n$ Show  set ${\pm 3^i}$, $1\leq i \leq 2^{n-2}$ is reduced residue system mod $2^n$.
For this, I believe I need to prove that for any integer $a$ such that $gcd(a,2^n)=1$, there exists an element $b$ in the set  ${\pm 3^i}$, $1\leq i \leq 2^{n-2}$ so that $a \equiv b$ mod $2^n$. As part of a problem related to this question, I've managed to show that the order of $3$ modulo $2^n$ is $2^{n-2}$. By the definition of order, this should fulfill the requirement of distinct elements in the given set.
How can I proceed further?
 [/INST] You're correct regarding what you need to prove, and have made a good start to determining a solution. Note that since there are $2^{n-1}$ odd integers between $1$ and $2^n$, inclusive, i.e., $\varphi(2^n)=2^{n-1}$, and the set $S = \{\pm 3^{i}, 1 \le i \le 2^{n-2}\}$ has $2(2^{n-2}) = 2^{n-1}$ elements, each of which are odd (i.e., coprime to $2^n$), we only need to prove that each element of $S$ is distinct modulo $2^n$.
To do that, first with $n = 2$, we have $\pm 3$ which is a reduced residue system for $2^2 = 4$. Thus, consider only $n \gt 2$. Using the $2$-adic order function, for even integers $m$, we have $3^m \equiv 1 \pmod{8}$, so $3^m + 1 \equiv 2 \pmod{8}$ giving $\nu_2(3^m + 1) = 1$. With $m$ odd, we have $\nu_2(3^m + 1) = 2$, with this determined by using the Lifting-the-exponent lemma (LTE lemma) with $3^m - (-1)^m$, or noting that $3^m + 1 = (3 + 1)(\color{blue}{3^{m-1} - 3^{m-2} + \ldots - 3 + 1})$, with the blue part having $m$ (i.e., an odd number) terms, each of which are odd, so their sum is odd. Altogether, this means $\nu_2(3^m + 1) \le 2$.
In addition, as you've noted, plus this can be shown using the LTE lemma and is also explained in if $3^k \equiv \ 1\pmod{2^n}$ then $2^{n-2} | k$, the multiplicative order of $3$ modulo $2^n$ is $2^{n-2}$.
Consider that $2$ distinct elements of $S$ have the same congruence modulo $2^n$. First, with them having the same sign and $1 \le j \lt k \le 2^{n-2}$, we have
$$\pm 3^{j} \equiv \pm 3^{k} \pmod{2^n} \; \to \; 1 \equiv 3^{k-j} \pmod{2^n} \tag{1}\label{eq1A}$$
However, $0 \lt k - j \lt 2^{n-2}$, but the multiplicative order being $2^{n-2}$ means this is impossible.
For the second case, with them having opposite signs and $1 \le j, k \le 2^{n-2}$, we get
$$\pm 3^{j} \equiv \mp 3^{k} \pmod{2^n} \; \to \; 3^{j} + 3^{k} \equiv 0 \pmod{2^n} \tag{2}\label{eq2A}$$
WLOG, have $j \le k$, so \eqref{eq2A} becomes $3^{j}(1 + 3^{k-j}) \equiv 0 \pmod{2^n} \; \to \; 1 + 3^{k-j} \equiv 0 \pmod{2^n}$. This requires $\nu_2(1 + 3^{k-j}) \ge n$, but $n \gt 2$ and, as shown previously, $\nu_2(1 + 3^{k-j}) \le 2$, so this is not possible.
The results of these $2$ cases show that all of the elements of $S$ have distinct congruences modulo $2^n$ so, as explained originally, $S$ forms a reduced residue system mod $2^n$.
</s>