\(n\in\Bbb N^+\), then
\begin{equation}\prod_{(i,n)=1}i\equiv\begin{cases}\,-1\pmod n,\quad n=2,4,p^\alpha,2p^\alpha\\\quad1\pmod n, \quad \text{otherwise}\end{cases}\end{equation}
这里 \(i\) 跑遍 \(n\) 的缩系.
这是 Gauss 在 DA.\(78\) 给出的 Wilson 定理(Wilson’s theorem) 的推广.
\(2,4,p^\alpha,2p^\alpha\) 有原根, 此种情况下, 可以给出简单的证明. 至于完整的证明, 我还没有找出满意的办法, 下面是一种途径:
先指出如下引理:
\(n\geqslant2, n=2^e p_1^{e_1}p_2^{e_2}\cdots p_k^{e_k},\) 其中\(p_i\geqslant3(i=1,2,\dotsc,k)\)为质数, 则同余方程 \( x^2\equiv1\pmod n\) 解的个数是 \(2^{k+\delta}\), 这里
\begin{equation}\delta=\begin{cases}0,\quad e=0,1,\\1,\quad e=2,\\2, \quad e\geqslant3.\end{cases}\end{equation}
引理的证明, 请参考华罗庚的数论导引, 定理3.5.1, 2.8.1 得出全部.
假定 \( x^2\equiv1\pmod n\) 有 \(2l\) 个解. 若 \((i,n)=1\), 且 \(i\) 不是 \( x^2\equiv1\pmod n\) 的解, 此时必有 \(i^\prime\neq i\) 使得 \( ii^\prime\equiv1\pmod n\), 并且不同的 \(i\) 对应于不同的 \(i^\prime\), 于是可将 \( i,i^\prime\) 配对, 所有这样的 \(i\) 的积 \(\prod\limits i\equiv1\pmod n\); 如果 \( i^2\equiv1\pmod n\), 可以将 \( i,-i\) 配对, \( i(-i)=-i^2\equiv-1\pmod n\). \( i,-i\) 这样的配对一共有 \(l\) 对, 因之
\[\prod_{(i,n)=1}i\equiv\prod_{ i^2\equiv1\pmod n} i\equiv(-1)^l\pmod n.\]
当 \(l\) 为奇数, \(k+\delta=1\), 即 \(n=2,4,p^\alpha,2p^\alpha\) 时, \(\prod\limits_{(i,n)=1}i\equiv-1\pmod n\); 余下的 \(n\) 将使得 \(k+\delta\geqslant2\), \(l\) 为偶数, 从而 \(\prod\limits_{(i,n)=1}i\equiv1\pmod n\).
Wilson 定理的组合证明
来自 \(1930\) 年代的一本俄文杂志, 作者是 A. B. (Moscow)
考虑一个圆周上的 \(p\) 等分点. 依次连结这 \(p\) 个点, 得到一个正 \(p\) 边形, 随便旋转多少个 \(\frac{360^\circ}p\) 所得到的图形都和原来重合. 同理, 连结第 \(1, 1+k, 1+2k,\dotsc\) 也得到一个星形的广义正 \(p\) 边形, 它们同样满足类似的旋转对称性质. 由于跳过 \(k\) 个点和跳过 \(p-k-2\) 个点是一回事, 因此这种类型的多边形一共有\(\frac{p-1}2\) 个.
除了这种旋转对称的“广义正 \(p\) 边形”以外, 其它的多边形随便旋转多少都不能和原来重合. 假设有图形最少只需要旋转 \(d\) 个点的位置(\(d>1\)) 之后就与原图形重合, 那么 \(p\) 一定是 \(d\) 的倍数.
另一方面, 连接圆周上的各点所能形成的多边形总数为 \(\frac{p!}2\). 这是因为规定了起始点后，多边形就由剩下的 \(p-1\) 个点的排列确定, 但每个多边形都各算了两次(顺时针,逆时针遍历各一次). 如前所说,广义的正 \(p\) 边形有 \(\frac{p-1}2\) 个. 故而, 非旋转对称的多边形总数
\[\frac{(p-1）!}2 -\frac{p-1}2 =\frac12 ((p-1)! + 1 – p)\]
被 \(\frac{p-1}2\) 整除当且仅当 \((p-1)! + 1\) 能被 \(p\) 整除.