How many elements in U(Z/nZ) have even order?

Question

Let $n$ be an odd natural number. How many elements have even order in $U(\mathbb{Z}/n\mathbb{Z})$?

I thought to use CRT to simplify the problem, but I'm not able to...

Answer 1

Instead of counting the elements with even order, we'll count the elements with odd order and subtract that from the total number of elements.

Suppose that $$ n = \prod_{i = 1}^{k} p_i^{e_i}. $$

Suppose that $x$ has order $m$ modulo $n$, where $m$ is odd. Then $x^m \equiv 1 \pmod n$, and so we have that $x^m \equiv 1 \pmod {p_i^{e_i}}$ for each $i$. It follows that, for each $i$, the order of $x$ modulo $p_i^{e_i}$ divides $m$, and hence is odd.

Conversely, suppose that $x$ has order $m_i$ modulo $p_i^{e_i}$ for each $i$. Then the order of $x$ modulo $n$ is $\operatorname{lcm}(m_1, m_2, \dots, m_k)$. In particular, if each of the $m_i$'s is odd, then the order of $x$ modulo $n$ is also odd.

It follows (using the Chinese Remainder Theorem) that the number of elements that have odd order modulo $n$ is the product of the number of elements that have odd order modulo each of the $p_i^{e_i}$s.

We now count how many elements have odd order modulo $p_i^{e_i}$. Let $f(m)$ denote the greatest odd divisor of $m$, and note that $f$ is completely multiplicative.

Since $p_i^{e_i}$ is is a power of an odd prime, there is a primitive root $g$ modulo $p_i^{e_i}$. (i.e. An element $g$ with order $\varphi(p_i^{e_i})$.)

Every element modulo $p_i^{e_i}$ is congruent to $g^s$ for some unique $s$. The order of $g^s$ is $$ \frac{\varphi(p_i^{e_i})}{\gcd(\varphi(p_i^{e_i}), s)}, $$ and so the order of $g^s$ is odd if and only if $s$ is divisible by the largest power of $2$ that divides $\varphi(p_i^{e_i})$. Let $2^t$ be the largest power of $2$ that divides $\varphi(p_i^{e_i})$ so that $\varphi(p_i^{e_i}) = 2^t f(\varphi(p_i^{e_i}))$. Then the number of natural numbers $s$ such that $0 \leq s < \varphi(p_i^{e_i})$ such that $2^t$ divides $s$ is $$ \left\lfloor \frac{\varphi(p_i^{e_i})}{2^t} \right\rfloor = f(\varphi(p_i^{e_i})). $$

It follows that the number of elements with odd order modulo $p_i^{e_i}$ is equal to $f(\varphi(p_i^{e_i})$, and so the number of elements with odd order modulo $n$ is equal to $$ \prod_{i=1}^{k} f(\varphi(p_i^{e_i})) = f\left( \prod_{i=1}^{k} \varphi(p_i^{e_i})) \right) = f(\varphi(n)). $$

Finally, we see that the number of elements modulo $n$ with even order is equal to $$ \varphi(n) - f(\varphi(n)). $$