Let G be the multiplicative group $\mathbb{Z}_n^*$ for $n = 2^k$ and $k \ge 3$.
Can we prove that no element has order bigger than $2^{k-2}$ ?
My solution (not really a solution) :
Since $n=2^k$, I thought that this group is cyclic and the generator is 2. I'm not sure if the group order can't be bigger than $2^{k-2}$?
On
If we simply want to show that the multiplicative group $G = \Bbb{Z}_{2^k}^*$ is not cyclic for $k \ge 3$ (which is all that is needed to conclude the order of any element is strictly less than the order of group $G$), then we can verify it first for the case $k = 3$ as Jared's original comment points out: $\Bbb{Z}_8^*$ is isomorphic to the product of two cyclic groups of order two (and has no element of order 4).
Then for $k \gt 3$ one verifies that the natural ring homomorphism from $\Bbb{Z}_{2^k}$ onto $\Bbb{Z}_8$ (taking the coarser congruence relation) induces a group homomorphism of the respective multiplicative groups (the groups of units of the respective rings). From this we see that $\Bbb{Z}_{2^k}^*$ cannot be cyclic, since the quotient group of a cyclic group is again cyclic.
The specific structure of $\Bbb{Z}_{2^k}^*$ can be worked out from the fact that it has two cyclic factors, $C_2 \times C_{2^{k-2}}$, with a generator for the second factor being 3 in all orders ($k \ge 3$). A write-up in terms of "primitive roots" is given here in Lemma 12, where it is shown by induction that for any odd $a$:
$$ k \ge 3 \implies a^{2^{k-2}} \equiv 1 \mod 2^k $$
On
The lowbrow explanation is that squares of odd numbers are equal to $1$ mod $8$. This is 1/4, not 1/2, of the elements in the multiplicative group, so that squaring (which is doubling, in the group) does twice as much collapsing of the residue classes than if that group were cyclic. This collapsing persists for higher powers of $2$ as one can always reduce any such situation mod $8$.
This is related to the fact that there are complications in "lifting" of solutions to $x^2=a$, from $\mod 2^k$ to $\mod 2^{k+1}$, but not for lifting the exponent in a solution mod $p^u$ for odd $p$.
An element $a\in\mathbb{Z}/n\mathbb{Z}$ is a unit if and only if $(a,n)=1$, that is, if and only if $a$ and $n$ are relatively prime. In your case, since the only prime divisor of $n=2^k$ is $2$, this equivalence reduces to $a$ is a unit if and only if $a$ is odd. Hence, the elements of $(\mathbb{Z}/2^k\mathbb{Z})^*$ are $$1,3,5,7,\ldots,2^k-5,2^k-3,2^k-1$$ of which there are $2^{k-1}$, or just half of $2^k$ because we are only taking odd elements. Now $(\mathbb{Z}/2^k\mathbb{Z})^*$ is not cyclic for $k\ge 3$ (read here, which states that $(\mathbb{Z}/2^k\mathbb{Z})^*\cong\mathbb{Z}/2\mathbb{Z}\times\mathbb{Z}/2^{k-2}\mathbb{Z}$). It follows that any element $a$ must have order less than $2^{k-1}$, but still dividing $2^{k-1}$, and hence must be no larger than $2^{k-2}$.