The structure of the group $(\mathbb{Z}/2^n\mathbb{Z})^*$

Question

I really got stuck with this exercise, can you help me?

This is the total exercise.

1. Calculate $(1+4)^{2^{n-3}}\in (\mathbb{Z}/2^n\mathbb{Z})^*$, and show that the element $5$ has order $2^{n-2}$ for $n \geq 2$.
2. Prove that $5$ and $-1$ generate the group $(\mathbb{Z}/2^n\mathbb{Z})^*$.
3. Prove that $ -1 \notin \langle 5\rangle$
4. Prove that $(\mathbb{Z}/2^n\mathbb{Z})^* \cong \mathbb{Z}/2\mathbb{Z} \times \mathbb{Z}/2^{n-2}\mathbb{Z}$. (This is an isomorphism of groups.)

Here is what I tried to do.

1) The first thing I thought about is the binomial theorem: $$(1+4)^{2^{n-3}} \quad = \quad \sum_{i=0}^{2^{n-3}}\left( {\begin{array}{*{20}c} {2^{n-3}} \\ i \\ \end{array}} \right) 4^i \quad = \quad \sum_{i=0}^{2^{n-3}}\frac{2^{n-3}!\cdot 4^i}{i!(2^{n-3}-i)!}$$ And that is pretty much how far I came. For the next part we should show that $5^{2^n-2}-1 = k\cdot 2^n$ for some integer $k$. What I knew is that $5^{2^n-2}$ is odd, so $5^{2^n-2}-1$ must be even. For more insight, I tried induction:

base case. $5^{2^2 -2}-1= 0\cdot 2^n$

Induction step. Assume that $\exists n \in \mathbb{N},\exists k \in \mathbb{Z},5^{2^n-2}-1 = k\cdot 2^n$. Now we want to proof that for some integer $k'$ the identity $5^{2^{n+1}-2}-1 = k'\cdot 2^{n+1}$ holds. So this is what I did. $5^{2^{n+1}-2}=(5^{2^n-1})^2=(5^{2^n-2}\cdot 5)^2=(5^{2^n-2})^2\cdot 25$. From the induction hypotesis we obtain $5^{2^n-2}=2^n k+1 \quad \text{so that}\quad \ (5^{2^n-2})^2\cdot 25 = (2^n k+1)^2\cdot 25-1 = 25(2^n k +1)^2-1$. Let's expand this. $25(2^nk+1)^2-1 = 25\cdot 2^{2n}k^2 +25\cdot 2^{n+1}k+24$. This is another point where I got stuck.

2) Well, let's take an arbitrary element $x \in \mathbb{Z}$. Can we find $a,b \in \mathbb{Z}$ such that $(-1)^a\cdot 5^b = 2^n\cdot k$ for some integer $k$? I calculated $|(\mathbb{Z}/2^n\mathbb{Z})^*|=2^{n-1}$ by using Euler's product formula. By this, using the previous bits of the exercise, it's enough to show that $\langle -\bar{1}\rangle \cap \langle \bar{5}\rangle = \{1\}$ Because in that case $$|\langle -\bar{1},\bar{5}\rangle| =|\langle -\bar{1} \rangle| \cdot |\langle\bar{5}\rangle|=2 \cdot 2^{n-2} = |(\mathbb{Z}/2^n\mathbb{Z})^*|$$ This brings us to the next part.

3) Clearly $ -1 \notin \langle 5\rangle \iff \langle -\bar{1}\rangle \cap \langle \bar{5}\rangle = \{\bar{1}\}$, since $-\bar{1}$ is the only non-trivial element in $\langle \bar{1}\rangle$. I wanted to show the desired claim by contradiction. If $ -1 \in \langle 5\rangle$, then $\langle \bar{5} \rangle = (\mathbb{Z}/2^n\mathbb{Z})^*$ as remarked. Unfortunately, I don't see how this should contradict our premises.

4) When all the previous stuff will be proved, this is not that hard.

We define the mapping $\quad \eta \quad : \quad \mathbb{Z}/2\mathbb{Z} \times \mathbb{Z}/2^{n-2}\mathbb{Z} \rightarrow \quad : \quad (\bar{i},\bar{j}) \mapsto (-1)^i\cdot5^j$. The mapping is well-defined because the order of the elements divides the group's order, surjective because of 2, injective because of 3 and an homomorphism because of the commutativity of $"\cdot"$.

Hopefully this long story is legible, so that some of you will take the effort to find my mistakes, and give me some hints.

Answer 1

We show by induction that $5^{2^{n-3}}\equiv 1+2^{n-1}\pmod{2^n}$ if $n\ge 3$.

For the induction step, suppose we know that $5^{2^{k-3}}\equiv 1+2^{k-1}\pmod{2^k}$.

Incrementing $k$ by $1$, we have $5^{2^{k-2}}=(5^{2^{k-3}})^2=(1+2^{k-1}+q2^k)^2$. Expand. We get $1+2^k +r$, where $r$ is divisible by $2^{k+1}$. The only place we have to be at all careful is at the $(2^{k-1})^2$ term. That gives us a $2^{2k-2}$, which is $\ge k+1$ if $k\ge 3$.

This almost completes the proof that the order of $5$ is $2^{n-2}$. (The above result shows that the order is greater than $2^{n-3}$. )