Wilson’s Theorem $\!\bmod pq\!:\, 1\equiv $ product of all residues coprime to $pq$

number theory

I know that $\{a_i\}=R(pq)$, and the title is step $(b)$, here is step $(a)$ (maybe a hint?):

Let $p$ and $q$ be two distinct odd primes.

$(a)$ Show that all the solutions of the congruence $x^2 \equiv 1 \pmod {pq}$ are given by
$x \equiv \{\;1,\;-1,\;p^{q-1}-q^{p-1},\;q^{p-1}-p^{q-1}\}\pmod{pq}$.

I can prove $(a)$, but cannot prove $(b)$ which is a generalization of Wilson's theorem.

Best Answer

As explained here, by pairing up inverses the product reduces to the product of all self-inverse $a_i$ (roots of $\,x^2\equiv 1).\, $ By CRT the roots are your $\,x\equiv (1,1),(-1,-1),\color{#c00}{(-1,1)},\color{#0a0}{(1,-1)}\pmod{p,q}\,$ with product $(1,1),\,$ which maps to $1\!\pmod{\!pq}.\ $ QED

Remark $ $ As explained in the link, the same proof generalizes Wilson's theorem to $\,\Bbb Z_n\,$ for odd $n$ having at at least two distinct prime factors. I explain in that answer how it generalizes even further, e.g. if a finite abelian group has a unique element of order $2$ then it is the product of all the elements; otherwise the product is $1$. There are motley twists on results like this - some well-known - some not. Follow said link to learn more.

Related Question