The Euler totient function $\varphi(n) = |\mathbb{Z}^{\times}_{n}|$ is even on $\mathbb{N}_{>2}$, so it is feasible that the group $\mathbb{Z}_{n}^{\times}$ can support an element of order $2$. If $n$ is $4, p^{r}$ or $2 p^{r}$ for odd prime $p$ and $r \geq 1$, then $\mathbb{Z}_{n}^{\times}$ is cyclic and such an element of order 2 necessarily exists if $\mathbb{Z}_{n}^{\times}$ is isomorphic to the rotation group of an even $n$-gon. What can be said about such order 2 elements in $\mathbb{Z}_{n}^{\times}$ for general $n > 1$? Do they always exist? If so, is there a way to count them as a function of $n$?
Here is what I understand. By the Chinese Remainder Theorem, if $n = p_{1}^{r_{1}} \cdots p_{s}^{r_{s}}$, then $\mathbb{Z}^{\times}_{n} \simeq \mathbb{Z}^{\times}_{p_{1}^{r_{1}}} \times \cdots \times \mathbb{Z}^{\times}_{p_{s}^{r_s}}$. So in order to have $\mathbb{Z}^{\times}_{2}$ as a subgroup, $n$ would need to be of the form $2m$ for odd $m$.
Update 1 Yes, if $n > 2$ and $n$ even, order 2 elements always exist by Cauchy's Theorem (duh).
Update 2 It seems that this is a non-trivial problem. There is no simple function of $n$ which counts the sequence $\{1, 1, 1, 1, 1, 3, 1, 1, 1, 3, 1, 1, 3, 3, 1, 1, 1, 3, 3, 1, 1, 7, \dots\}$ (A155828), which is the number of non-identity order 2 elements in $\mathbb{Z}^{\times}_{n}$ as a function of $n \geq 3$.
I used the following Mathematica code to generate this sequence:
${\tt Table[Count[Table[If[GCD[k, n] > 1, 0, Mod[k^2, n]], \{k, 2, n \}],
1], \{n, 3, 100\}]}$
Best Answer
For general $n$, the group $(\mathbb{Z}/n\mathbb{Z})^\times$ is the direct product of $(\mathbb{Z}/p_i^{k_i}\mathbb{Z})^\times$ where $n=\prod p_i^{k_i}$ is the prime factorization of $n$. You already know how many elements of order $2$ there are in each of those factors; now just count in how many ways you can choose an element of order 1 or 2 in each factor, and you'll have the desired number of elements of order 2 in your group.