13
$\begingroup$

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.

$\endgroup$

2 Answers 2

12
$\begingroup$

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

$\endgroup$
14
  • 2
    $\begingroup$ 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. $\endgroup$
    – Favst
    Commented Jun 20, 2022 at 22:17
  • 1
    $\begingroup$ 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. $\endgroup$
    – KConrad
    Commented Jun 20, 2022 at 23:51
  • $\begingroup$ 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. $\endgroup$
    – Favst
    Commented Jun 21, 2022 at 0:02
  • $\begingroup$ 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$. $\endgroup$
    – KConrad
    Commented Jun 21, 2022 at 0:33
  • 1
    $\begingroup$ 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. $\endgroup$
    – KConrad
    Commented Jun 21, 2022 at 20:54
17
$\begingroup$

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

$\endgroup$
3
  • 2
    $\begingroup$ 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. $\endgroup$
    – KConrad
    Commented Jun 20, 2022 at 5:26
  • $\begingroup$ What if there is more than one element of order 2? Then we just now that the product of all elements is the product of the elements of order 2 (which could be different from $e$). $\endgroup$
    – Thrash
    Commented Apr 7 at 22:10
  • $\begingroup$ Update: If there is more than one such element, we can consider all such elements together with $e$, which form a subgroup that (I think) is isomorphic to a $k$-fold copy of the cyclic group of order $2$ (where $k>1$), and it is not difficult to see that the product of all these elements yields $e$ because in each component, the element of order $2$ occurs an even number of times. $\endgroup$
    – Thrash
    Commented Apr 8 at 10:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.