Is Gauss's generalization of Wilson's theorem non-superficially related to the classification of moduli for which primitive roots exist? 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.
 A: Both Gauss' generalization, and the classification of moduli with primitive roots, are 'shadows' of the structural theory of the finite abelian group $G_m:=(\mathbb{Z}/m\mathbb{Z})^{\times}$.
Gauss' generalization computes the product of elements in $G_m$, while the classification tells us whether $G_m$ is cyclic. If you know the structure of $G_m$, that is, if you have an isomorphism $G_m \cong \bigoplus_i \mathbb{Z}/a_i \mathbb{Z}$, it is easy to both compute the product of elements in $G_m$ and to answer whether $G_m$ is cyclic.
The reason for the similarity between the answers is the following group version of Gauss' result: suppose $G$ is a finite abelian group. If $G$ has a unique element of order $2$, call it $a$, then the product of elements in $G$ is $a$. Otherwise, the product is the identity element $e$.
So without any number theory (only group theory) we know that $\prod_{k \in G_m} k$ is not congruent to $1 \bmod m$ if and only if $G_m$ has a unique element of order $2$. Gauss' result implies a classification of $m$ for which $G_m$ has a unique element of order $2$.
What's the relationship between have a unique element of order $2$ and being cyclic? Well, in the case of the groups $G_m$, they always have even order (unless $m=2$); that's a number theory phenomenon. A cyclic group of even order has a unique element of order $2$, so Gauss' generalization sees the moduli that have primitive roots. Why doesn't it see other moduli? In general, a finite abelian group $G$ of even order can have a unique element of order $2$ while not being cyclic. Such groups are given by $\mathbb{Z}/2^m \mathbb{Z} \oplus A$ where $A$ is a non-cyclic group of odd order. The groups $G_m$ cannot look like that, though, and I do not know how to show it without developing at least most of the structural theory of $G_m$.
A: 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.
$$
