# If $n > 2$, prove that the order of the multiplicative group of units modulo n, $U_n$, is even.

I'm struggling with this. I know it is going to use Lagrange's Theorem. This is what I have so far.

Suppose $$|U_n| = k.$$ This implies $$a^k = 1$$ for all $$a$$ in $$U_n$$ and $$|a|$$ divides $$k$$.

Now, what can be said about the order of an element $$a$$? I haven't been able to conclude that it's even with what I have, therefore I continued so: $$|\langle a\rangle|$$ divides $$k$$ where $$\langle a\rangle$$ is the cyclic subgroup generated by $$a.$$

However, I haven't been able to conclude that $$|\langle a\rangle|$$ is even.

So I tried using this: an element $$a$$ is in $$U_n$$ iff gcd$$(a, n) = 1$$.

Any hints?

Hint: Use a pairing argument. If $x$ is a unit, then so is $-x$. And if $n\gt 2$ they are distinct.
• Where is the $-x$ in the group, $U_4 = \{1, 3\}$? I'm trying to understand this in a small example first. – Dude Apr 16 '14 at 12:39
• Sorry, typo. edited to $U_4$. – Dude Apr 16 '14 at 12:42
• I think you mean $U_4$. If $x=1$, then $-x=3$, if $x=3$, then $-x=1$. The objects $1$ and $3$ are a couple. In today's business-oriented language, we can call them partners. – André Nicolas Apr 16 '14 at 12:42
• The example you chose to ask about is perhaps too small to see what happens in general. Look at $U_{10}$ or $U_{11}$. – André Nicolas Apr 16 '14 at 12:45
• Perhaps it's easier if written $x \mapsto n-x$. – lhf Apr 16 '14 at 13:01
Yet another hint: Show that $\{+1,-1\}$ is a subgroup of $U_n$ of order $2$. Now apply Lagrange.
Different hint: $|U_n|=\varphi(n)$, the Euler totient function. So you have to prove that for $n \gt 2$ this number is even.