4
$\begingroup$

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?

$\endgroup$
5
  • $\begingroup$ @mdave16 Yes of course. $\endgroup$ – Taha Akbari Jul 25 '17 at 17:51
  • $\begingroup$ Can you show that whatever the product is, its square must be $1$? $\endgroup$ – Arthur Jul 25 '17 at 18:08
  • $\begingroup$ Do you have any knowledge of group theory? Where did you find the problem? (so we can surmise what level of math is expected) $\endgroup$ – Bill Dubuque Jul 25 '17 at 22:25
  • $\begingroup$ @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. $\endgroup$ – Taha Akbari Jul 26 '17 at 5:39
  • $\begingroup$ @Taha I added a shorter proof to my answer. $\endgroup$ – Bill Dubuque Jul 29 '17 at 3:38
6
$\begingroup$

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

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

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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