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

How can we compute the product of all invertibles in $\Bbb Z_n$?

In the special case $n=p$ where $p$ is a prime it is Wilson's theorem. By pairing inverses it reduces to computing the product of all $a$ such that $a^2\equiv 1\pmod{n}.\,$ How can we do that?

• @mdave16 Yes of course. – Taha Akbari Jul 25 '17 at 17:51
• Can you show that whatever the product is, its square must be $1$? – Arthur Jul 25 '17 at 18:08
• Do you have any knowledge of group theory? Where did you find the problem? (so we can surmise what level of math is expected) – Bill Dubuque Jul 25 '17 at 22:25
• @BillDubuque It was just asked by our teacher after wilson's theorem for research but I am a high school student and I don't have any knowledge of groupe theory. – Taha Akbari Jul 26 '17 at 5:39
• @Taha I added a shorter proof to my answer. – Bill Dubuque Jul 29 '17 at 3:38

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 = \{1,g\}$$ and the quads are the cosets $$aG$$ of the subgroup $$\,G = \left = \{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

• Here is a similar classical proof that $-1$ is a square in a finite field of odd size $\,q\iff q\equiv1\pmod{\!4}$ $\ \ \$ – Bill Dubuque May 21 '20 at 2:37

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.

• Could you give a link to its proof? – Taha Akbari Jul 26 '17 at 5:48
• I mean the part for all other $n>1$?The other parts can be proved easily. – Taha Akbari Jul 26 '17 at 6:14
• @Taha I added a sketch of an elementary proof avoiding group theory. – Bill Dubuque Jul 26 '17 at 14:35