Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
1  
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
3  
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
1  
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
add comment

5 Answers

up vote 3 down vote accepted
  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}$.

share|improve this answer
add comment

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.

share|improve this answer
1  
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
add comment

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

share|improve this answer
add comment

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

share|improve this answer
add comment

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

share|improve this answer
add comment

Your Answer

 
discard

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.