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?
 A: 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.
A: Write
$$3^m = (4-1)^m = 1 + \sum_{i=1}^m 4^i(-1)^{m-i} {m \choose i}.$$
Now setting $m = 2^{n-2}$ we see with some work (how many factors $2$ are there in the binomial coefficient), the sum vanishes, i.e. 
$$3^{2^{n-2}} \equiv 1 \mod{2^n}.$$
Thus, we know that the order of $3$ must divide $2^{n-2}$, hence it must be a power of two. Look at the binomial coefficients again to see that no smaller power than $2^{n-2}$ will make the sum vanish.
A: By induction, consider the following claims, $A(n): 3^{2^{n-3}} \not\equiv 1 (\mod 2^n)$ and $B(n): 3^{2^{n-2}} \equiv 1 (\mod 2^n)$. Assume $A(n-1), A(n), B(n-1), B(n)$, let's prove $A(n+1)$ and $B(n+1)$.
$B(n+1)$ is obvious since by $B(n)$, $3^{2^{n-1}} = (3^{2^{n-2}})^2 = (2^n x + 1)^2 = 1 (\mod 2^{n+1})$.
To prove $A(n+1)$ we need to use the assumption at $n-1$. The rest is left as an exercise.
