Product of invertibles in $\Bbb Z_n$ [Wilson's Theorem generalization]

Solution 1:

Most proofs use group theory. Since you don't know that, I will sketch a more elementary proof that attempts to expose some of the group-theoretic essence of the matter more simply.

As you noted, $ $ by pairing inverses the product reduces to the product of all roots of $\,x^2\!-\!1\,$ in $\,\Bbb Z_n.\,$ If there is only one root $\,x = 1\,$ then the product $= 1.\,$ Else there is a root $\,g\neq 1\,$ and using it we can partition the $k$ roots into pairs $(a,ga)$ since the map $\,a\mapsto ga$ is self inverse by $\,g^{-1}=g\,$ and $\,ga\neq a\,$ by $\,g\neq 1.\,$ Each pair $(a,ga)$ has product $a^2 g = g\,$ so the entire product $= g^{k/2}\! = g$ or $1,\,$ by $\,g^2 = 1.\,$ If there are exactly two roots $\,1,g\,$ then the product $= g.\,$ Else there is a third root $h$ and the same argument shows the entire product $= 1$ or $h,\,$ thus it must be $1,\,$ by $\,1,g,h\,$ distinct.

Using the above, we reduce to checking if the set of invertibles in $\,\Bbb Z_n\,$ has at least two nontrivial roots $\,g,h\not\equiv 1$ of $\,x^2\equiv 1.\,$ For $n>2$ one nontrivial root is $\,h\equiv -1.\,$ The proof separates into a few cases, using nothing deeper than CRT = Chinese Remainder Theorem. Let's do a typical case.

If $n$ is odd with at least two prime factors $\,p\neq q\,$ then $\,n = ab\,$ for coprime $a,b>2,\,$ so by CRT the solution of $\,g \equiv 1\pmod{\!a},\ g\equiv -1\pmod{\!b}\,$ satisfies $\,g^2\equiv 1,\,\ g\not\equiv -1,1\pmod{\!n}.\,$ Hence, by above, there are at least two nontrivial roots $\,g\,$ and $\, h\equiv -1\,$ so the product is $\,\equiv 1.\,$

The few remaining cases can be dispatched in similarly simple ways, e.g. see Theorem $2.2$ in Wilson's Theorem: an algebraic approach by Pete L. Clark.

Remark $ $ Here is another elementary way to compute the root product. If there are at least two nontrivial roots $\,g,h\not\equiv 1.\,$ We show that the product of all roots is $\equiv 1$ by placing them into quads (vs pairs) with product $1$. Define $\,a\sim b$ if $a$ can be obtained from $b$ by a sequence of "reflections" of the form $\,x\mapsto gx\,$ or $\,x\mapsto hx\,$ or, equivalently, if $\, a = g^i h^j b\,$ for some integers $i,j$.

It is easy to check that this is an equivalence relation, so it partitions the roots into disjoint classes of equivalent elements. Further, since $\,g^2\equiv 1\equiv h^2$ it is easy to show that each equivalence class has exactly $4$ elements of form $\, \{a, ga, ha, gha\}\,$ with product $\,(a^2 gh)^2 \equiv 1.\,$ Thus the product of all roots partitions into a product of quads with product $1$, so the entire product is also $\,\equiv 1.$

If you learn group theory it is enlightening to revisit the above proof to see how it is used implicitly above. The pairs are the cosets $aG$ of the subgroup $G = \left<g\right> = \{1,g\}$ and the quads are the cosets $aG$ of the subgroup $\,G = \left<g,h\right> = \{1,g,h,gh\}$ or, equivalently, the orbits of $a$ under $G$, so we are essentially repeating a (special-case) proof of Lagrange's theorem

You can find links to other classical approaches in the above linked paper. Exploiting innate reflection (involution) symmetry (as in the pairing and quading above) is a widely applicable method that often leads to elegant proofs.

The ideas above generalize Wilson's theorem even further to: if a finite abelian group has a unique element of order $2$ then it equals the product of all the elements; otherwise the product is $1$. You can find another classical proof of this in Pete L. Clark's notes listed above

Solution 2:

Gauss's generalization of Wilson's theorem. The product is $-1$ mod $n$ if $n$ is $4$, a power of an odd prime, or twice a power of an odd prime; for all other $n>1$ it is $1$. See also OEIS sequence A001783.