Multiplicative group modulo $2^n$

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.

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.