# 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.

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.$$

• Beautiful. It's a pleasure to read your detailed response. More so because I believe you are Keith Conrad, whose expository papers on elementary number theory helped me as a high school olympiad student and later as an undergraduate. I actually wondered if you might respond, as this seemed to be your kind of a problem! Would it be alright if I included a version of your proof here in some books that I have written (currently in editing stage)? I would write up my own rendition and give you credit, of course. Jun 20, 2022 at 22:17
• That's fine, but while it's nice to see Gauss' generalization of Wilson's theorem is a consequence of the classification of $n$ for which the units mod $n$ are cyclic (that's what you asked about here, and I didn't known it before), I think it makes Gauss' generalization seem harder than it really is. All you need to know about the units mod $n$ to get Gauss' result is the number of solutions to $x^2 \equiv 1 \bmod n$, which can be done with the Chinese remainder theorem and some simple calculations modulo prime powers, just as in Ore's book. That is much simpler than the method I wrote above. Jun 20, 2022 at 23:51
• Thanks. While there is simplicity in Ore's exposition, I actually prefer your method for a couple of reasons. Firstly, it illuminates a reason for why the two results have similarities. Secondly, although the primitive root theorem is a strong result to be using, I feel that your proof is less ad hoc than Ore's. Also, it provides a nice application of the primitive root theorem in my modular exponentiation chapter. Jun 21, 2022 at 0:02
• What other applications of the primitive root theorem do you have? In many places I've seen people appeal to $(\mathbf Z/(p))^\times$ being cyclic to prove Euler's criterion $a \equiv \Box \bmod p \Longleftrightarrow a^{(p-1)/2} \equiv 1 \bmod p$ when $(a,p) = 1$ for odd primes $p$. I feel like that is overkill, since it can be shown using the fact that a polynomial of degree $d$ over a field (like $\mathbf Z/(p)$) has at most $d$ roots in the field, which is more intuitive and simpler than bringing in a generator of the unit group mod $p$. Jun 21, 2022 at 0:33
• I rewrote Step 3(ii) to avoid mentioning isomorphisms, but they're implicitly there since the reduction map $(\mathbf Z/(n))^\times \to (\mathbf Z/(n'))^\times$ is onto with a trivial kernel: each unit mod $n'$ is the reduction of one unit mod $n$. That's why the exponent on the right side of the displayed congruence in Step 3(ii) is $1$ instead of an even number like in all other similar-looking steps. Jun 21, 2022 at 20:54

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$$.

• For prime $p$, $-1 \bmod p^\alpha$ has order $2$ unless $p^\alpha = 2$. So by the Chinese rem. thm, there is more than one unit mod $n$ of order $2$ if $n$ has more than one odd prime factor or if $n$ has one odd prime factor and is divisible by $4$. There are three elements of order $2$ in the units mod $2^\alpha$ if $\alpha \geq 3$. The only moduli $n > 1$ left for which there could be a unique unit of order $2$ are $2$, $4$, $p^\alpha$, and $2p^\alpha$ for odd primes $p$. For these moduli except $2$, only one unit has order $2$. We don’t need to know the moduli whose units are cyclic. Jun 20, 2022 at 5:26