# $|\mathbb{Z}_n^{\times}|$ is always even when $n \geq 3$

I've noticed $|\mathbb{Z}_n^{\times}|$ is always even for $n\geq3$.

I've also observed that $|\mathbb{Z}_n^\times|$ is always even no matter whether $n$ is prime or not. When $n$ is prime and greater than 2, $|\mathbb{Z}_n^\times| = n-1$, which is even. If $n$ is not prime, then we have $\mathbb{Z}_n^\times = \{a \in \mathbb{Z}_n^\times | \gcd(a,n)=1\}$, and $|\mathbb{Z}_n^\times| = k|a|$. How can I tell that $2|k$?

-

If $a$ is prime to $n$, so is $n-a$.
Careful - $n-a$ is the additive inverse of $a$, not the inverse in ${\bf Z}_n^{\times}$. But don't be hard on yourself - it's a lot easier to see these things when you've been teaching them for years than when you're learning them for the first time. – Gerry Myerson Feb 17 '12 at 5:12
You're trying to show a certain set has an even number of elements. Often, the easiest way to do that is to show that the elements come in pairs. So I'm showing you how to pair off the elements of your set: if $a$ is in the set, then (I claim) so is $n-a$, and that's a pair. Now, you have to show that my claim is correct, and you have to show that no number gets paired with itself, and you have to show that each element gets paired with exactly one other element, so you still have some work to do. What I've given you is a hint at what is probably the easiest way to do the problem. – Gerry Myerson Feb 17 '12 at 11:45