<s>[INST] Multiplicative group modulo $2^n$ I remember learning that the multiplicative group modulo $2^n$, namely the group $\mathbb{Z}_{2^n}^\times$of integers coprime with $2^n$ is isomorphic to $\mathbb{Z}_2\times\mathbb{Z}_{2^{n-2}}$, which is due to Gauss.
It boils down to proving that the multiplicative order of $3$ in the group is $2^{n-2}$. Can you give me a hint here?
 [/INST] We want to show $$3^{2^{n-3}}\ne 1\mod 2^n$$ and $$3^{2^{n-2}}\equiv 1\mod 2^n$$
for $n\ge 3$
For $n=3$ , we have $3^{2^{n-3}}=3\ne 1\mod 8$ and $3^{2^{n-2}}=9\equiv 1\mod 8$
hence the claim is true for $n=3$
For $n=4$; we have $3^{2^{n-3}}=9\ne 1\mod 16$ and $3^{2^{n-2}}=81\equiv 1\mod 16$ , hence the claim is true for $n=4$
Assume the claim is true for $n$ with $n\ge 4$
Then, we have $$3^{2^{n-1}}-1=(3^{2^{n-2}}-1)(3^{2^{n-2}}+1)$$
By induction hypothesis, the first factor on the right side is divisible by $2^n$ and the second factor is even. Hence we have $2^{n+1}|3^{2^{n-1}}-1$ and therefore $$3^{2^{n-1}}\equiv1\mod 2^{n+1}$$
Now, we verify $$3^{2^{n-2}}\not\equiv 1\mod 2^{n+1}$$
We have $3^{2^{n-2}}-1=(3^{2^{n-3}}-1)(3^{2^{n-3}}+1)$
By induction hypothesis , the first factor on the right side is not divisible by $2^n$ and for the second, we have $3^{2^{n-3}}+1\equiv (-1)^{2^{n-3}}+1=2\mod 4$ hence the second factor is not divisble by $4$. 
The exponents in the power of two in the prime factorizations are therefore a number smaller than $n$ in the first factor and $1$ in the second factor, so smaller than $n+1$ in total. Therefore, we have proven $3^{2^{n-2}}\ne 1\mod 2^{n+1}$ thus completing the proof.
</s>