Wilson's theorem (actually proven by Lagrange) from elementary number theory states that: If $n\ge 2$ is an integer, then
$$
(n-1)! \equiv
\begin{cases}
\hfill -1 \pmod {n} &\text{ if } n \text{ is prime}\\
\hfill 2 \pmod {n} &\text{ if } n=4\\
\hfill 0 \pmod {n} &\text{ if } n \text{ is composite, } n\ne 4
\end{cases}.
$$
Gauss's generalization of Wilson's theorem (the proof of which Gauss skips in Disquisitiones Arithemeticae, article 78, for the sake of "brevity") states that: For positive integers $n$,
$$
\prod_{\substack{k\in[n]\\ \gcd(k,n)=1}}{k} \equiv
\begin{cases}
\hfill -1 \pmod {n} &\text{if } n=1,2,4,p^{\alpha},2p^{\alpha}\\
\hfill 1 \pmod {n} &\text{otherwise}
\end{cases},
$$
where $p$ is any odd prime and $\alpha$ is any positive integer.
This classification matches exactly the moduli for which there exists a primitive root. This seems to be too much of a coincidence, given the unusual form of the satisfying moduli. I have read the proof of Gauss's generalization in Øystein Ore's Number Theory and its History (p. 263-267), but it makes no reference to primitive roots, nor did I find any proof anywhere that uses primitive roots.
Question: Is there a link between Gauss's generalization of Wilson's theorem and the classification of moduli for which there exist a primitive root? There is the superficial link of course, that the two conclusions are the same, but I am wondering if it is possible that one of the results may be proven using the other. Other non-superficial observations are welcome.
This is somewhat related to an earlier question that I asked on math.stackexchange.
Best Answer
I will show the two results are non-superficially related by showing one of them implies the other: the classification of moduli $n \geq 2$ for which the unit group $(\mathbf Z/(n))^\times$ is cyclic implies Gauss' generalization of Wilson's theorem.
The proof is presented in three steps. All the basic ideas are present in the case of odd $n$, which doesn't need the third step. Handling even $n$ is mostly a matter of tedious details.
Step 1: For $n \geq 2$, if $(\mathbf Z/(n))^\times$ is cyclic, then $\prod_{u \in (\mathbf Z/(n))^\times} u \equiv -1 \bmod n$.
Proof: The result is obvious for $n = 2$, so we can take $n \geq 3$, which implies $\varphi(n)$ is even. Let $g$ be generator of $(\mathbf Z/(n))^\times$. Then $$ \prod_{u \in (\mathbf Z/(n))^\times} u = \prod_{0 \leq k \leq \varphi(n)-1} g^k = g^{\varphi(n)(\varphi(n)-1)/2} \bmod n. $$ Since $g$ has order $\varphi(n)$, which is even, $g^{\varphi(n)/2}$ has order 2 in $(\mathbf Z/(n))^\times$, so it must be $-1$ (the only element of order $2$ in the cyclic group $(\mathbf Z/(n)^\times$). Thus $$ g^{\varphi(n)(\varphi(n)-1)/2} = \left(g^{\varphi(n)/2}\right)^{\varphi(n)-1} = (-1)^{\varphi(n)-1} = -1 \bmod n $$ since $\varphi(n)-1$ is odd.
Step 1 covers the cases $n = 2$, $4$, $p^\alpha$, and $2p^\alpha$ where $p$ is an odd prime and $\alpha \geq 1$. The next two steps handle the remaining $n$.
Step 2: For odd $n > 1$ that is not a prime power, $\prod_{u \in (\mathbf Z/(n))^\times} u \equiv 1 \bmod n$.
Proof: To prove that product over units in $(\mathbf Z/(n))^\times$ is $1$, it suffices to show for each prime power $p^\alpha\mid\mid n$ that the product is $1 \bmod p^\alpha$ (then use the Chinese remainder theorem).
Write $n = p^\alpha m$, so $\gcd(p^\alpha,m) = 1$. The natural reduction homomorphism $(\mathbf Z/(n))^\times \to (\mathbf Z/(p^\alpha))^\times$ is surjective, so each unit mod $p^\alpha$ is the reduction of $\varphi(n)/\varphi(p^\alpha)$ units mod $n$, and $\varphi(n)/\varphi(p^\alpha) = \varphi(m)$. Thus $$ \prod_{u \in (\mathbf Z/(n))^\times} u \equiv \left(\prod_{v \in (\mathbf Z/(p^\alpha))^\times} v\right)^{\varphi(m)} \bmod p^\alpha. $$ The group $(\mathbf Z/(p^\alpha))^\times$ is cyclic, so by Step 1 the product over $v$ on the right side is $-1 \bmod p^\alpha$ and the exponent $\varphi(m)$ is even because $m \geq 3$ (this is where we use the fact that $n$ is odd and not a prime power), so the right side of the displayed congruence above is $1 \bmod p^\alpha$.
Step 3: For even $n > 1$ that is not $2$, $4$, or $2p^\alpha$ for an odd prime $p$, $\prod_{u \in (\mathbf Z/(n))^\times} u \equiv 1 \bmod n$.
Write $n = 2^\beta n'$ for $\beta \geq 1$ and odd $n' \geq 1$. We describe these $n$ in three ways: (i) $n = 2^\beta$ for $\beta \geq 3$, (ii) $n = 2n'$ where $n' > 1$ is not a prime power, or (iii) $n = 2^\beta n'$ where $\beta \geq 2$ and $n' \geq 3$.
(i): $n = 2^\beta$ for $\beta \geq 3$. Show by induction on $\beta$ that the solutions of $x^2 \equiv 1 \bmod 2^\beta$ are $x \equiv \pm 1, \pm(1+ 2^{\beta-1}) \bmod 2^\beta$, which are all distinct since $\beta \geq 3$. Therefore $$ \prod_{u \in (\mathbf Z/(2^\beta))^\times} u \equiv (-1)(1+2^{\beta-1})(-(1+2^{\beta-1})) \equiv 1 \bmod 2^\beta. $$
(ii): $n = 2n'$ where $n' > 1$ is not a prime power. We will argue as in Step 2. The natural reduction homomorphism $(\mathbf Z/(n))^\times \to (\mathbf Z/(n'))^\times$ is surjective, so each unit mod $n'$ is the reduction of $\varphi(n)/\varphi(n')$ units mod $n$. Since $\varphi(n) = \varphi(2n') = \varphi(2)\varphi(n') = \varphi(n')$, $\varphi(n)/\varphi(n') = 1$, so $$ \prod_{u \in (\mathbf Z/(n))^\times} u \equiv \prod_{v \in (\mathbf Z/(n'))^\times} v\bmod n'. $$ Since $n' > 1$ is odd and not a prime power, the product on the right side of the displayed congruence is $1 \bmod n'$ by Step 2. So the product on the left side of the displayed congruence is $1 \bmod n'$. It is also $1 \bmod 2$ since units mod $n$ are odd. Therefore $\prod_{u \in (\mathbf Z/(n))^\times} u$ is $1 \bmod n'$ and $1 \bmod 2$, which makes it $1 \bmod n$.
(iii) $n = 2^\beta n'$ where $\beta \geq 2$ and $n' \geq 3$. Using the same method as in Step 2, to show $\prod_{u \in (\mathbf Z/(n))^\times} u$ is $1 \bmod n$, it suffices to show the product is $1 \bmod 2^\beta$ and $1 \bmod n'$.
First we show the product is $1 \bmod n'$. The natural reduction homomorphism $(\mathbf Z/(n))^\times \to (\mathbf Z/(n'))^\times$ is surjective, so each unit mod $n'$ is the reduction of $\varphi(n)/\varphi(n')$ units mod $n$, and $\varphi(n)/\varphi(n') = \varphi(2^\beta)$. Thus $$ \prod_{u \in (\mathbf Z/(n))^\times} u \equiv \left(\prod_{v \in (\mathbf Z/(n'))^\times} v\right)^{\varphi(2^\beta)} \bmod n'. $$ On the right side, the product over units modulo $n'$ is $-1 \bmod n'$ if $n'$ is a prime power (Step 1) and it is $1 \bmod n'$ if $n'$ is not a prime power (Step 2). Since $\varphi(2^\beta)$ is even, $$ \left(\prod_{v \in (\mathbf Z/(n'))^\times} v\right)^{\varphi(2^\beta)} \equiv (\pm 1)^{\rm even} \equiv 1 \bmod n'. $$
To show the product is $1 \bmod 2^\beta$, swap the roles of $2^\beta$ and $n'$ in the previous argument to get $$ \prod_{u \in (\mathbf Z/(n))^\times} u \equiv \left(\prod_{v \in (\mathbf Z/(2^\beta))^\times} v\right)^{\varphi(n')} \equiv (\pm 1)^{\rm even} \equiv 1 \bmod 2^\beta. $$