Product of Totatives-I

The natural arithmetic to consider is the multiplicative group of residues modulo $n$ , which we will denote $U(n)=\{a \in \mathbb{Z}_n | gcd(a, n)=1 \}$ . We can then represent $U(n)$ as

$U(n) \approx U(2^a)\times U(p_1^{r_1})\times U(p_2^{r_2})\times \ldots \times U(p_k^{r_k})$ ,

where $n=2^ap_1^{r_1}p_2^{r_2}\cdot \ldots \cdot p_k^{r_k}$ for distinct odd primes $p_i$ , $r_i \geq 1$ , and $a \geq 0$ ( $\approx$ stands for isomorphic). Now we notice that the only elements of $U(p_i^{r_i})$ satisfying $b^2 \equiv 1 \mod n$ are $\pm 1$ . Furthermore, we know $U(2^a) \approx \mathbb{Z}_2 \times \mathbb{Z}_{2^{a-2}}$ for $a \geq 2$ , so it should have $4$ distinct elements satisfying $b^2 \equiv 1 \mod 2^a$ (if $a=0$ or $1$ , then $U(2^a)$ is just the trivial group).

Therefore, there are $4 \cdot 2\cdot 2\cdot \ldots \cdot 2=2^{k+2}$ residues $b$ satisfying $b^2 \equiv 1 \mod n$ for $a \geq 2$ , and $2^k$ for $a=0,1$ . Set $T=\{b \in U(n) | b^2 \equiv 1 \mod n\}$ . Then notice that

$\displaystyle \prod_{b \in U(n)} b= \prod_{b \in T} b$ .

This is because if $b \notin T$ , then $b \ne b^{-1}$ , and so the LHS can be rearranged to make $b$ and $b^{-1}$ cancel. Furthermore, the RHS can be reduced by considering $T=C \cup D$ where $C=\{c \in T | c<n/2 \}$ and $D=\{d \in T | d>n/2 \}$ . Clearly, for each $d\in D$ , $d \equiv -c \mod n$ for some $c\in C$ . Thus,

$\displaystyle \prod_{b \in T} b=(-1)^{|C|} \prod_{c \in C} c^2=(-1)^{|C|}=(-1)^{|T|/2}=(-1)^{2^{k\pm 1}}=\boxed{1}$

Note: If $n=1, 2$ then the product trivially yields $1$