# Showing that $U(2^n)$ is not cyclic for $n \ge 3$ [duplicate]

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.

Thanks.

• This is exercise 56 in chapter 4 of Gallian's Contemporary Abstract Algebra. Nov 24, 2015 at 1:48

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?

• Got it, thanks. Did you have an idea ahead of time that those two numbers would have order 2? Is there a better way to find them than just playing with the numbers? Jul 14, 2013 at 21:02
• Well, you would expect $2^n-1$ to have order 2, since $2^n-1\equiv -1\pmod{2^n}$. As for the other... I recalled having proved it this way previously, so I knew to look for an element of order 2, and I figured that $2^{n-1}+1$ requires very little nudging to get everything other than $1$ to mod out. Jul 14, 2013 at 21:29
• Got it. Thanks for the help. Jul 14, 2013 at 21:59
• Thank you, this answer really helped me! Nov 25, 2015 at 2:13
• @J.W.Tanner Sure is Dec 11, 2020 at 19:52

By the way, it suffices to consider just $$2^3$$, since if its multiplicative group is non-cyclic, then necessarily the multiplicative groups mod $$2^n$$ for $$n>3$$ are non-cyclic, since they surject to the multiplicative group of $$2^3$$...

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.

Suppose G=$$U(2ⁿ)$$ is cyclic. Then G must have atleast one element of order |U(2ⁿ)|=$$\phi(2ⁿ)$$=2

Now the number of elements of order d in a group is a multiple of $$\phi(d)$$

Hence the number of elements of order $$2^{n-1}$$ =k.$$\phi$$($$2^{n-1}$$)=k.$$2^{n-2}$$ Clearly $$k.2^{n-2}$$ $$\leq$$ $$2^{n-1}$$ (order of the group) Thus the possible values of k are 0,1&2.

• If $$k=2$$ then no. of such elements is $$2.2^{n-2}=2^{n-1}$$ (what do you think about this?) Each element of $$U(2^n)$$ has order $$2^{n-1}.$$ But identity 1 has order 1 !!. Hence $$k≠2$$
• If $$k=1$$ then no. of such elements is $$2^{n-2}.$$ i.e, exactly half the elements have order $$2^{n-1}$$ which is not possible.

$$Hence \ k \ must \ be \ 0.$$

That is, no element in $$U(2^n)$$ has order $$2^{n-1}.$$ Hence $$U(2^n)$$ is not cyclic.

A cyclic group of even order has exactly one element of order $$2$$. For $$n\geq 3$$, both $$-1=2^n-1 \bmod 2^n$$ and $$1+2^{n-1}\bmod 2^n$$ have multiplicative order $$2$$, and they are distinct modulo $$2^n$$ since $$1+2^{n-1}<2^n-1$$ because $$n\geq 3$$ (they are equal when $$n=2$$).
In fact, for $$n\geq 3$$ there are always exactly three elements mod $$2^n$$ of order $$2$$: $$-1, 2^{n-1}+1, 2^{n-1}-1 \bmod 2^n$$. But this is not necessary in the argument above.