# Show that if n has primitive roots then

Let $$P_{n}=\prod_{1\le a\le n ,(a,n)=1}a$$ Show that if n has primitive roots then $P_{n}=-1$(mod n).Otherwise $P_{n}=1$(mod n). How do I approach this one? It seems interesting.

Note that there are two kinds of elements in your product: elements $x$ satisfying $x^2 = 1$ and elements satisfying $xy = 1$ for some $y \ne x$. The elements of the second kind can be paired together, with the product of each pair equal to 1. Therefore, the overall product is equal to the product of all of the elements squaring to $1$.
If $(\mathbb{Z}/n\mathbb{Z})^\times$ is cyclic, there can be only one such element, and it furthermore must be $-1$.
Otherwise, you need to show that the set of such elements forms an elementary abelian 2-subgroup of rank at least 2. It's clear that the product of every element in such a group is the identity, by taking a basis $x_1, \ldots x_n$, and then taking the product of the elements $x_1^{i_1}\dots x_n^{i_n}$ over all choices $(i_j) \in \{0,1\}^n$ yields the answer $x_1^{2^{n-1}}\dots x_n^{2^{n-1}} = 1$.
Off the top of my head, showing that this is the case uses the fact that the groups $(\mathbb{Z}/n\mathbb{Z})^\times$ are not cyclic precisely when $n$ has two distinct odd prime divisors or when $n$ is divisible by both $4$ and an odd prime. Therefore, my approach doesn't help if you're trying to use this fact to classify when $(\mathbb{Z}/n\mathbb{Z})^\times$ is cyclic.
• I just tried to work out a proof of the abelian group version of this theorem, and failed in the case of many order-2 elements. How do you know that the order-2 elements form a free $\Bbb Z/2\Bbb Z$-module? – Mario Carneiro Apr 10 '15 at 22:36
• if $x^2 = y^2 = 1$, then $(xy)^2 = x^2y^2 =1$, so the set is closed under multiplication. The fact that there is an action of the field $\mathbb{F}_2$ follows from the fact that each element squares to 1. Note that for arbitrary abelian groups, you might have only 1 such element even though your group is not cyclic. I'm explicitly using the fact that groups like $\mathbb{Z}/3\mathbb{Z} \times \mathbb{Z}/3\mathbb{Z}$ cannot appear when you consider $(\mathbb{Z}/n\mathbb{Z})^\times$. – Rolf Hoyer Apr 10 '15 at 22:42
• Could you elaborate on "there is an action of the field $\Bbb F_2$ because each element squares to 1"? Although I can believe the statement, I'm not sure what test you are using to verify the module structure without checking the axioms directly. Also I'm not sure what is the problem you are highlighting with $(\Bbb Z/3\Bbb Z)^2$ - there are no order 2 elements in that group, so there is no problem, yes? – Mario Carneiro Apr 11 '15 at 5:03
• it's already an abelian group, and there's only one thing the module struture can be. The element $0\in \mathbb{F}_2$ takes everything to the identity, and the element $1\in \mathbb{F}_2$ acts trivially. The thing that you need to check is then that $(1\cdot a)(1\cdot a) = (1+1)\cdot a = 0\cdot a$, which is equivalent to saying that every element $a$ squares to $1$. As to the example, I guess I mean that $\mathbb{Z}/2\mathbb{Z} \times (\mathbb{Z}/3\mathbb{Z})^2$ instead as an example of a non-cyclic abelian group with only one element squaring to the identity. – Rolf Hoyer Apr 11 '15 at 5:13