Primitive roots modulo $2^k$

Question

I'm trying to write a general proof. I know that if $k=3$ then I have to show that there are no primitive roots modulo 8, and this is given because $8$ has residues $1,3,5,7$; and $ord_8(1)=1, ord_8(3)=2, ord_8(5)=2, ord_8(7)=2$, none of which is $\phi(8)=4$.

A proof I in a textbook said that it can be proved by induction that $a^{2^{k-2}}\equiv 1 \pmod {2^k}$ for all odd numbers $a$ .

I have two questions: (1) What happens if $a$ is even? Why the proof wouldn't work if $a$ is even?; (2) Why is the exponent of $a$ $2^{k-2}$? Is it because it has to be a quadratic nonresidue?

The proof continues: $a^{2^{k-2}}\equiv 1 \pmod {2^k}$, then $a^{2^{k-2}}=1+b2^k$, and squaring both sides $a^{2^{k-1}}=1+b2^{k+1}+b^22^{2k+1}$, then $a^{2^{k-1}}\equiv 1 \pmod {2^{k+1}}$.

I understand why is the formula proved, but I don't understand is how this helps to show that there is no $a$ such that $a^k\equiv 1 \pmod {2^k}$ in general.

Answer 1

First question: If $a$ is even, it's not relatively prime to the modulus. The induction argument fails because the basis step $a\equiv 1 \mod{2}$ doesn't hold.

Second question: If the exponent were $n-1$, then the order of $a$ might still be $\phi(2^n) = 2^{n-1}$. If we prove the exponent is smaller, then we know for sure that $a$ can't have order $\phi(2^n)$ and so it can't be a primitive root.