6
$\begingroup$

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

  • 0
    Right! I found it and then posted the formula just about the same time you posted your answer. What an interesting problem!2011-04-14

5 Answers 5

0

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

6

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.

  • 0
    My questions were supposed to be hints ;)2011-04-14
4
  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}$.

2

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

2

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