Order of a general element in the units group mod $2^k$

Question

Is there any formula for the order of a general element in the units group modulo $2^k$ with $k\geq 3$?

Thanks

Answer 1

There is a good rule, and it’s simply that if $m\equiv1\pmod{2^{k-d}}$ but $\not\equiv1\pmod{2^{k-d+1}}$ for $1\le d\le k-2$, i.e. $2\le k-d<k$, then the order of $m$ in the multiplicative group of units modulo $2^k$ is $2^d$. For odd numbers that are $\equiv3\pmod4$, look at $-m$ instead.

The rule above is better expressed in the language of the $2$-order $v_2$: if $w=2^ty$ with $y$ odd, we say that $v_2(w)=t$. Now the rule is that the order of $m$ in $(\Bbb Z/(2^k))^\times$ is $2^{k-v_2(m-1)}$. Let’s try it for $k=5$: the order of $25$ is $2^{5-v_2(24)}=2^{5-3}=4$, just right. You still need to worry about the case $m\equiv3\pmod4$, though.

And now that I’ve told you the way things fit together, you should go home and prove that what I say is true.