Showing that $U(2^n)$ is not cyclic for $n \ge 3$ I'd appreciate a hint on how to solve the following problem:
Prove that $U(2^n) (n \ge 3)$ is not cyclic. ($U(m)$ is the group of positive integers $j \le m$ such that $\gcd(j,m)=1$, under multiplication $\mbox{mod}\,\,m$)
Since elements in $U(2^n)$ are coprime to $2^n$, $U(2^n)=\{1,3,5,...,2^n-3, 2^n-1\}$.  I tried taking an arbitrary odd number, $1 \le 2k+1 \le 2^n$, and showing that $(2k+1)^{2^n} \not\equiv 1 \,\,\mbox{mod} \,\,2^n$, which would show that no element has order $2^n$ and therefore cannot generate $U(2^n)$ so that $U(2^n)$ is not cyclic.
I used the binomial theorem to expand $(2k+1)^{2^n}$ in general terms, and wanted to show that there is some coefficient that is not divisible by $2^n$, so that $(2k+1)^{2^n}\, \mbox{mod} \,\,2^n \not\equiv 1$.  Problem is, the coefficients other than one are divisible by $2^n$, as far as I can see.  I hope I'm not missing something obvious.
Outside of this, I'm afraid I'm out of ideas.  How else can I go about this?
Thanks.
 A: The first issue here is that the order of $U(2^n)$ is not $2^n$ - in fact, it is $\phi(2^n)=2^{n-1}$, where $\phi$ is Euler's totient function.
As a hint:  note that the element $2^n-1$ is of order 2, since
$$
(2^n-1)^2=2^{2n}-2^{n+1}+1\equiv1\pmod{2^n}.
$$
Also,
$$
(2^{n-1}+1)^2=2^{2n-2}+2^n+1\equiv1\pmod{2^n}
$$
as long as $2n-2\geq n$, which holds since $n\geq 3$.
So, you have two (distinct) elements of order 2.  Can that happen if $U(2^n)$ is cyclic?
A: Here is a way of principle of mathematical induction to prove it.
For n=3 it is simple to show that U(8) is not cyclic.
Now assume that for any positive integer k>3, U(2^k) is not cyclic. We have to show that U(2^k+1) is not cyclic.
The proof is by contradiction, we assume that U(2^k+1) is cyclic then it's every subgroup must be cyclic. Since, the integers which are prime to 2^k will also be prime to 2^k+1. Hence, U(2^k) will be a subgroup of U(2^k+1), but is not cyclic which is a contradiction to our assumption that U(2^k+1) is cyclic.
