Assume \(n=2^k\) for \(k>2\). (For \(n=2\) and \(n=4\), there are primitive roots – check this if you haven't already). In Exercise 10.6.3 we show that \(n=8\) does not have a primitive root. In particular, each element of \(U_8\) has order \(2^{3-2}=2\), so that \(a^2\equiv 1\) (mod \(8\)) for all \(a\in U_8\). Think of this as a base case for induction on \(k\).

Now assume by induction that for \(n=2^k\) it is true that no element has order higher than \(2^{k-2}\). I.e., \begin{equation*}a^{2^{k-2}}\equiv 1\text{ (mod }2^k)\; .\end{equation*} By definition of divisibility, that means for any odd number \(a\), we have that \begin{equation*}a^{2^{k-2}}=1+2^k\cdot m\end{equation*} for some integer \(m\).

Next, let's look at what happens to everything in modulus \(2^{k+1}\). We want that \begin{equation*}a^{2^{(k+1)-2}}=a^{2^{k-1}}\equiv 1\text{ (mod }2^{k+1})\, .\end{equation*} While it's easy to get \(2^{k+1}\) from \(2^k\), the only way to easily get \(a^{2^{k-1}}\) from \(a^{2^{k-2}}\) is by squaring. (Recall Fact 4.5.2 where we found powers quickly by using \((a^{2^e})^2=a^{2^{e+1}}\).)

So we write \(a^{2^{k-1}}\) as a square, substitute the above, and look at the remainders. \begin{equation*}a^{2^{k-1}}=\left(a^{2^{k-2}}\right)^2=(1+2^k m)^2=1+2^{k+1}m+2^{2k}m^2\end{equation*} \begin{equation*}=1+2^{k+1}(m+2^{k-1}m^2)\equiv 1\text{ mod }2^{k+1}\end{equation*}

By induction we are done; because the highest possible order of an element is less than \(\phi\), there are no primitive roots modulo \(2^k\) for \(k>2\).

We won't prove this, but it is easy if you use just a little group theory, and one can demonstrate it for a given example.