I have to prove the following,
$$\prod_{\substack{n=1\\ \gcd(n,m)=1}}^{m}n\equiv \begin{cases}-1\pmod{m}\quad\text{if }m\text{ has a primitive root.}\\ +1\pmod{m}\quad\text{otherwise.}\end{cases}$$
I can prove the first part but I'm having trouble with the second part, any hints ? I tried proving the contrapositive, namely that $\Pi \equiv -1\pmod{m}$ implies $m$ has a primtive root but I didn't get far.
The congruence $$x^2\equiv 1\pmod{m}\Rightarrow (x-1)(x+1)\equiv 0\pmod{m}\tag{1}$$ is possible for each modulus $m$. Dispensing with the trivial cases $m=1$ or $2$, we see the $r$ roots must fall into two pairs of size $r/2$, since for any root $\rho$ we must have $-\rho$ a root too. Now by $(1)$, $\gcd(\rho,m)=\gcd(-\rho,m)=1$, and so they are incongruent modulo $m$: $$\rho\not\equiv -\rho\pmod{m}\Rightarrow 2\rho\not\equiv 0\pmod{m}\tag{2}$$ We also have $(-\rho)(\rho)= -\rho^2\equiv-1\pmod{m}$, so it follows the product of all roots $r$ is $+1$ or $-1$ dependent on whether $4\mid r$ or not: $$\prod_{\substack{i=1\\ 4\mid r}}^{r}\rho_i\equiv1\pmod{m}\quad\text{else}\quad\prod_{\substack{i=1\\ 4\nmid r}}^{r}\rho_i\equiv-1\pmod{m}\tag{3}$$
Now consider the number of roots of congruence $(1)$: When $m=1$ or $2$ the number of roots, $r$, is $1$; $$(1-1)(1+1)\equiv0\pmod{m}$$ When $m$ is the power of an odd prime, $p^a$ say, or double such, $2p^a$, or $4$, then the number of roots $r$ is $2$. \begin{align*} (1-1)(1+1)\equiv &((2^2-1)-1)((2^2-1)+1)\equiv0\pmod{2^2}\\ (1-1)(1+1)\equiv &((p^a-1)-1)((p^a-1)+1)\equiv0\pmod{p^a}\\ (1-1)(1+1)\equiv &((2p^a-1)-1)((2p^a-1)+1)\equiv0\pmod{2p^a}\\ \end{align*} We now need to show that otherwise $4\mid r$. This shows $r=2$ in the right-handside of $(3)$. To see this consider $m=2^b$, where $b>2$. Then we wish to find the roots $$x^2-1=(x-1)(x+1)\equiv0\pmod{2^b}$$ Now both $(x-1)$ and $(x+1)$ are even, so we may write $$\frac{x-1}{2}\cdot\frac{x+1}{2}\equiv0\pmod{2^{b-2}}$$ Since the difference of $\frac{x-1}{2}$ and $\frac{x+1}{2}$ is $x$ which is odd, this means one of the factors is even and the other odd. Therefore one has to be divisible by $2^{b-2}$, and we get $$x\equiv1\pmod{2^{b-1}}\quad\text{or}\quad x\equiv-1\pmod{2^{b-1}}$$ Modulo $2^b$ we get the four incongruent roots $1$, $1+2^{b-1}$ and $-1$, $-1-2^{b-1}$. Now for a general $m=2^bp_1^{a_1}\cdots p_j^{a_j}$ we use The Chinese Remainder Theorem to find the number of roots of $x^2-1$ in $\mathbb{Z}/(m)$ by finding the number of roots in each $\mathbb{Z}/(p_i^{a_i})$, of which there will be two for each odd prime power, and the cases for $\mathbb{Z}/(2^{b})$ have been covered: namely $1$ for $\mathbb{Z}/(2^{1})$, $2$ for $\mathbb{Z}/(2^{2})$, and finally $4$ for $\mathbb{Z}/(2^{b})$ where $b>2$. So in all cases we get $4\mid r$.
Now of $\varphi(m)$ numbers $j$, $1\le j\le m-1$, that are relatively prime to $m$, we have the $r$ roots of $(1)$, and any other non-roots, $u$, $v$ say, will pair up as multiplicative inverses as they are relatively prime to $m$: $$uv\equiv1\pmod{m}$$ Note we won't get $u^2\equiv1\pmod{m}$ as then $u$ satisfies $(1)$ and so is a root, this also means $u\not\equiv v\pmod{m}$, and it follows the product of these $\varphi(m)-r$ non-roots is $1$.
Now if we multiply all $\varphi(m)$ amount of numbers together we get the result: $$ \prod_{\substack{n=1\\ \gcd(n,m)=1}}^{m}n\equiv \begin{cases} 0\pmod{m}\quad\text{if $m=1$,}\\ -1\pmod{m}\quad\text{if $m=4$, $p^a$ or $2p^a$,}\\ +1\pmod{m}\quad\text{otherwise.} \end{cases} $$
By a primitive root modulo $m$ we mean a number $g$, such that for every $a$ relatively prime to $m$, there exists some power of $g$ having $a\equiv g^k\pmod{m}$, where we call $k$ the index or discrete logarithm of $a$ to the base $g$ modulo $n$.
The multiplicative group of integers modulo $m$, $(\mathbb{Z} /(m))^{\times}$, is cyclic if and only if $m$ is $1$, $2$, $4$, $p^a$ or $2p^{a}$, where $p$ is an odd prime and $a>0$. Now a group is cyclic if and only if it has a generator. Hence the primitive root $g$ is a generator in such cases, with $g^0$, $g^1$, $g^2,\dotsc,g^{\varphi{(m)}-1}$ giving the full set of possible residues.
This condition is equivalent to that derived before, and so $$ \prod_{\substack{n=1\\ \gcd(n,m)=1}}^{m}n\equiv \begin{cases} 0\pmod{m}\quad\text{if $m=1$,}\\ -1\pmod{m}\quad\text{if $m$ has a primitive root, $m\neq2$,}\\ +1\pmod{m}\quad\text{otherwise.} \end{cases} $$