# Prove that the order of $U(n)$ is even when $n>2$.

I'm trying to provide a solution to the following claim:

"The order of $U(n)$ is even when $n>2$."
Note: here, $U(n)$ is the set of all positive elements that are less than and relatively prime to $n$.

I think I've correctly proven the claim, but I couldn't find anything similar online. So, I would appreciate any criticism/corrections regarding my proof (me being fairly new to abstract algebra, help is very welcome!).

proof: Assume $|U(n)|=m$, for $n>2$. Firstly, suppose that some $\mu \in U(n)$ has an even order. By Lagrange's Theorem, we know that $|\mu|$ divides $m$. Thus, $m$ is even (since for $k\in \mathbb{N}$, $\not \exists l \in \mathbb{N} : 2k|(2l+1)$). If $\mu$ is odd, then $m$ is either even or odd. However, we know (I forgot the theorem's name) that the number of elements of order $2$ is divisible by $\phi(2)=1$. So, there is at least one element of order $2$ in $U(n)$. Thus, if $m$ is odd then $\exists h \in U(n)$ such that $|h|$$\not |$$m$, which is impossible. Therefore, $m=|U(n)|$ must always be even. $\blacksquare$ (?)

I like your idea that if $U(n)$ has an element of even order, then the order of $U(n)$ is even by Lagrange's Theorem. On the other hand, for $n>2$, the order of $n-1$ in $U(n)$ is 2.

Another approach to this problem is to work with properties of the Euler phi function since $o(U(n))=\varphi(n)$.

• Right! I like that: $(n-1)^2=n^2-2n+1=n(n-2)+1 \equiv 1 (\bmod{n})$. I was skeptical of the line "However, we know (I forgot the theorem's name) that the number of elements of order 2 is divisible by ϕ(2)=1." I could replace it with "Since $(n-1)^2 \equiv 1 (\bmod{n})$, then there is at least one element of order $2$ in $|U(n)|$." What do you think about the proof with that change?
– P.V.
Commented Jul 25, 2014 at 4:24

Notice that $\phi(n)=|U(n)|$ where $\phi$ is Eurler's totient function.

So, if $n > 2$, $\phi(n)$ is even.

Here is the proof:

There are two cases; $n$ has an odd prime in its prime factorization, and $n=2^k,\ k\in\mathbb{Z}$. <\br>

Suppose $n$ has an odd prime in it's factorization, say $p$, then $\phi(n)=\phi(pn')=\phi(p)\phi(n')=(p-1)\phi(n')$. Notice that $p$ is odd, so $(p-1)$ is even. Thus, $\phi(n)$ is even.

Suppose $n=2^k,\ k\in\mathbb{Z},\ k > 1$. Then $\phi(n)=\phi(2^k)=2^k(1-\frac{1}{2})=2^{k-1}$. So $\phi(n)$ is even.

Therefore, $\phi(n)=|U(n)|$ is always even.