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](https://en.wikipedia.org/wiki/Wilson%27s_theorem#Gauss%27s_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](https://en.wikipedia.org/wiki/Primitive_root_modulo_n#Table_of_primitive_roots). 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](https://math.stackexchange.com/questions/3739515/is-there-a-deeper-reason-for-the-classification-of-moduli-in-which-a-primitive-r) that I asked on math.stackexchange.



Is Gauss's generalization of Wilson's theorem non-superficially related to the classification of moduli for which primitive roots exist?
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.
$$


