# Counting Elements of Order 2 in $\mathbb{Z}^{\times}_{n}$

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\}]}$

-
Or you can just take n-1 as having order 2. Don't need $n$ even, just $n>2.$ –  Thomas Andrews Apr 14 '11 at 2:22
Right, but I'd like to count all order 2 elements as a function of $n$. –  user02138 Apr 14 '11 at 2:22
If $\rho(n)$ denotes the number of odd prime factors of $n$, and $\delta(n)=1$ if $8$ divides $n$, $0$ if $8$ doesn't divide $n$ but $4$ does, and $-1$ if $4$ doesn't divide $n$, then your number is $2^{\rho(n)+\delta(n)+1}-1$. –  user641 Apr 14 '11 at 3:17
Actually, the sequence you want is A060594: oeis.org/A060594 which has a formula (pretty much the one Steve D writes above, or I derived below), then subtract 1 to remove the identity. –  Arturo Magidin Apr 14 '11 at 3:23
Right! I found it and then posted the formula just about the same time you posted your answer. What an interesting problem! –  user02138 Apr 14 '11 at 3:24

1. If $n$ is an odd prime power, then the group $\mathbb{Z}_n^{\times}$ is cyclic, so it has exactly one element of order $2$.

2. If $n=2^k$, then the group $(Z_{2^k})^{\times}$ has either:

• No elements of order $2$ if $k=1$.
• One element of order $2$ if $k=2$.
• Three elements of order $2$ if $k\geq 3$: the group of units is isomorphic to $C_2\times C_{2^{a-2}}$. The elements of exponent $2$ are of the form $(x,y)$ with $x$ and $y$ of exponent $2$ (two possibilities each); this gives $4$ elements of exponent $2$, and removing the identity we get three elements of order $2$.
3. If $n= 2^k p_1^{a_1}\cdots p_r^{a_r}$ is a prime factorization of $n$, then $$\mathbb{Z}_n^{\times} \cong \mathbb{Z}_{2^k}^{\times}\times\mathbb{Z}_{p_1^{a_1}}^{\times}\times\cdots\times \mathbb{Z}_{p_r^{a_r}}^{\times}.$$ An element $(a,b_1,\ldots,b_r)$ is of exponent $2$ if and only if each coordinate is of exponent $2$. There are $2$ possibilities for each $b_i$, $1\leq i\leq r$, plus the number of choices depending on $k$. Throwing away the identity, we get:

• $2^r - 1$ elements of order $2$ if $0\leq k\leq 1$.
• $2^{r+1}-1$ elements of order $2$ if $k=2$.
• $2^{r+2}-1$ elements of order $2$ if $k=3$.

See Sequence A060594 in the OEIS. It gives the number of solutions to $x^2\equiv 1 \pmod{n}$, which is one more than the number of element of order $2$ in $\mathbb{Z}_n^{\times}$.

-

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.

-
You can also solve the equation $x^2=1$ in $Z_n^x$, without the Chinese reminder theorem: n divides (x-1)(x+1) and gcd [(x-1),(x+1)] divides 2. Thus any other prime factor of $n$ fully divides either n+1 or n-1. It is exactly the same as your proof just written "more elementary" –  N. S. Apr 14 '11 at 2:25
Awesome. Thanks. Now, how do we count the order 2 elements? –  user02138 Apr 14 '11 at 2:28
If $p \neq 2$ is should be clear from my comment how many elements of order $2$ are in $(\mathbb{Z}/p_i^{k_i}\mathbb{Z})^\times$. If $p=2$ you must have gcd$(x-1,x+1)=2$, so how can $2^m$ divide $(x-1)(x+1)$? Again you know the answer. For the general formula, what is the order of an element in the product of some groups? How can this be two? –  N. S. Apr 14 '11 at 2:33
I thought that was the point of my answer :-) do you understand how to construct elements of order 2 in a direct product? –  Alon Amit Apr 14 '11 at 2:39
My questions were supposed to be hints ;) –  N. S. Apr 14 '11 at 7:01

In general any finite group $G$ of even order has an element of order 2 by Cauchy's Thm.

-

For any $n \geq 3$, the general group $\mathbb{Z}_n^{\times}$ has an element of order 2, namely $-1$.

-

Using Benoit Cloitre's comment from this sequence (A060594) and subtracting $1$ for the identity element, it must be that the sequence is generated by the following three functions $a(n) = 2^{\omega(n)-1} - 1$ if $n \equiv \pm 2 \mod 8$, $a(n) = 2^{\omega(n)} - 1$ if $n \equiv \pm 1, \pm 3, 4 \mod 8$ and $a(n) = 2^{\omega(n) + 1} - 1$ if $n$ is divisible by $8$, where $\omega(n)$ is the number of prime divisors of $n$.

-