Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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$?

share|cite|improve this question
up vote 8 down vote accepted

If $a$ is prime to $n$, so is $n-a$.

share|cite|improve this answer
Right. Since n-a is inverse of a. How stupid I am. – Shannon Feb 17 '12 at 3:55
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
If n-a is not the inverse in {\bf Z}_n^{\times}, then do I have to prove it when I use it? – Shannon Feb 17 '12 at 5:36
If n-a is not inverse, then what it is? – Shannon Feb 17 '12 at 6:22
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.