文章目录
Z
p
\,Z_p\,
Zp域例题
简化剩余系：乘除法运算的封闭性例题
End
Z
p
\,Z_p\,
Zp域
设
p
\,p\,
p为质数，则集合
Z
p
=
{
0
,
1
,
⋯
,
p
−
1
}
\,Z_p=\{0,1,\cdots,p-1\}\,
Zp={0,1,⋯,p−1}是模
p
\,p\,
p的非负最小完全剩余系，同时也是模
p
\,p\,
p的非负最小简化剩余系。
在
Z
p
\,Z_p\,
Zp中可以进行加法，减法，乘法，即对于
a
,
b
∈
Z
p
\,a,b \in Z_p\,
a,b∈Zp，
a
±
b
\,a \pm b\,
a±b，
a
b
\,ab\,
ab都仍在
Z
p
\,Z_p\,
Zp中。
在
Z
p
\,Z_p\,
Zp中也能进行除法，即对于
a
,
b
∈
Z
p
\,a,b \in Z_p\,
a,b∈Zp，并且
a
≠
0
\,a \ne 0\,
a=0，一定有唯一的
x
∈
Z
p
\,x \in Z_p\,
x∈Zp，满足
a
x
≡
b
(
m
o
d
p
)
\,ax \equiv b \!\! \pmod{p}\,
ax≡b(modp)
证
：
(
1
)
存
在
性
：
由
a
∈
Z
p
,
且
a
≠
0
得
(
a
,
p
)
=
1
。
利
用
裴
蜀
恒
等
式
一
定
有
u
,
v
∈
Z
,
满
足
a
u
+
p
v
=
1
,
从
而
a
u
b
+
p
v
b
=
b
,
于
是
有
a
u
b
≡
b
(
m
o
d
p
)
,
在
完
全
剩
余
系
Z
p
中
,
有
x
满
足
x
≡
u
b
(
m
o
d
p
)
,
于
是
有
a
x
≡
a
u
b
≡
b
(
m
o
d
p
)
,
存
在
性
成
立
；
(
2
)
唯
一
性
：
另
一
方
面
,
若
x
′
∈
Z
p
,
满
足
a
x
′
≡
b
(
m
o
d
p
)
,
两
式
相
减
得
a
(
x
−
x
′
)
≡
0
(
m
o
d
p
)
,
而
(
a
,
p
)
=
1
,
于
是
x
−
x
′
≡
0
(
m
o
d
p
)
,
从
而
x
=
x
′
,
则
唯
一
性
成
立
。
证：(1)\,存在性：由\,a \in Z_p\,,且\,a \ne 0\,得\,(a\,,p)=1\,。利用裴蜀恒等式一定有\,u,v \in Z\,,满足\,au+pv=1\,,从而\,aub+pvb=b\,,于是有\,aub \equiv b \!\! \pmod{p}\,,在完全剩余系\,Z_p\,中,有\,x\,满足\,x \equiv ub \!\! \pmod{p}\,,于是有\,ax \equiv aub \equiv b \!\! \pmod{p}\,,存在性成立；(2)\,唯一性：另一方面,若\,x' \in Z_p\,,满足\,ax' \equiv b \!\! \pmod{p}\,,两式相减得\,a(x-x') \equiv 0 \!\! \pmod{p}\,,而\,(a\,,p)=1\,,于是\,x-x' \equiv 0 \!\! \pmod{p}\,,从而\,x=x'\,,则唯一性成立。
证：(1)存在性：由a∈Zp,且a=0得(a,p)=1。利用裴蜀恒等式一定有u,v∈Z,满足au+pv=1,从而aub+pvb=b,于是有aub≡b(modp),在完全剩余系Zp中,有x满足x≡ub(modp),于是有ax≡aub≡b(modp),存在性成立；(2)唯一性：另一方面,若x′∈Zp,满足ax′≡b(modp),两式相减得a(x−x′)≡0(modp),而(a,p)=1,于是x−x′≡0(modp),从而x=x′,则唯一性成立。
综上讨论知，
Z
p
\,Z_p\,
Zp是一个域，即
Z
p
\,Z_p\,
Zp域是可以加法、乘法两种运算以及它们的逆运算减法、除法(除法不为
0
\,0\,
0)的集合。有理数集
Q
\,Q\,
Q，实数集
R
\,R\,
R，复数集
C
\,C\,
C，都是域，而
Z
p
\,Z_p\,
Zp域是一个有限域，即元素个数为有限的域。
例题
设质数
p
>
3
\,p \gt 3\,
p>3，证明：
1
1
2
+
1
2
2
+
⋯
+
1
(
p
−
1
)
2
=
a
b
\,\dfrac{1}{1^2}+\dfrac{1}{2^2}+\cdots+\dfrac{1}{(p-1)^2}=\dfrac{a}{b}\,
121+221+⋯+(p−1)21=ba的分子
a
\,a\,
a能被
p
\,p\,
p整除。
证
：
在
式
子
两
边
同
乘
以
(
(
p
−
1
)
!
)
2
,
得
(
(
p
−
1
)
!
)
2
a
b
=
∑
k
=
1
p
−
1
(
(
p
−
1
)
!
k
)
2
,
右
边
每
一
项
都
是
整
数
,
所
以
右
边
和
左
边
都
是
整
数
。
对
于
每
个
k
∈
{
1
,
2
,
⋯
,
p
−
1
}
,
存
在
h
∈
Z
p
,
使
得
k
h
≡
1
(
m
o
d
p
)
,
而
不
同
的
k
有
不
同
的
h
,
于
是
(
(
p
−
1
)
!
)
2
a
b
≡
∑
h
=
1
p
−
1
(
(
p
−
1
)
!
h
)
2
≡
(
(
p
−
1
)
!
)
2
∑
h
=
1
p
−
1
h
2
≡
(
(
p
−
1
)
!
)
2
1
6
p
(
p
−
1
)
(
2
p
−
1
)
≡
0
(
m
o
d
p
)
,
即
p
∣
(
(
p
−
1
)
!
)
2
⋅
a
,
又
p
∤
(
(
p
−
1
)
!
)
2
,
故
p
∣
a
证：在式子两边同乘以((p-1)!)^2\,,得\,((p-1)!)^2\dfrac{a}{b}=\begin{aligned}\sum_{k=1}^{p-1}(\dfrac{(p-1)!}{k})^2\end{aligned}\,,\\右边每一项都是整数,所以右边和左边都是整数。对于每个\,k \in \{1,2,\cdots,p-1\}\,,存在\,h \in Z_p\,,使得\\\,kh \equiv 1 \!\! \pmod{p}\,,而不同的\,k\,有不同的\,h\,,于是\,((p-1)!)^2\dfrac{a}{b} \equiv \begin{aligned}\sum_{h=1}^{p-1}((p-1)!\,h)^2 \equiv ((p-1)!)^2\sum_{h=1}^{p-1}h^2\end{aligned} \\ \equiv ((p-1)!)^2\dfrac{1}{6}p(p-1)(2p-1) \equiv 0 \!\! \pmod{p}\,,即\,p \mid ((p-1)!)^2\cdot a\,,又\,p \nmid ((p-1)!)^2\,,故\,p \mid a\,
证：在式子两边同乘以((p−1)!)2,得((p−1)!)2ba=k=1∑p−1(k(p−1)!)2,右边每一项都是整数,所以右边和左边都是整数。对于每个k∈{1,2,⋯,p−1},存在h∈Zp,使得kh≡1(modp),而不同的k有不同的h,于是((p−1)!)2ba≡h=1∑p−1((p−1)!h)2≡((p−1)!)2h=1∑p−1h2≡((p−1)!)261p(p−1)(2p−1)≡0(modp),即p∣((p−1)!)2⋅a,又p∤((p−1)!)2,故p∣a设
p
\,p\,
p是大于
3
\,3\,
3的质数，
1
+
1
2
+
⋯
+
1
p
=
r
p
s
\,1+\dfrac{1}{2}+\cdots+\dfrac{1}{p}=\dfrac{r}{ps}\,
1+21+⋯+p1=psr，其中
r
,
s
\,r,s\,
r,s是互质的自然数，证明：
p
3
∣
(
r
−
s
)
\,p^3 \mid (r-s)\,
p3∣(r−s)
证
：
令
T
=
1
+
1
2
+
⋯
+
1
p
−
1
=
r
p
s
−
1
p
=
r
−
s
p
s
,
则
2
T
=
(
1
+
1
p
−
1
)
+
(
1
2
+
1
p
−
2
)
+
⋯
+
(
1
p
−
1
+
1
)
=
p
∑
i
=
1
p
−
1
1
i
(
p
−
i
)
,
设
2
2
,
3
2
,
⋯
,
(
p
−
1
)
2
的
最
小
公
倍
数
为
M
,
则
由
M
与
p
互
质
,
得
i
(
p
−
i
)
M
≡
−
i
2
M
(
m
o
d
p
)
,
得
M
i
(
p
−
i
)
≡
−
M
i
2
(
m
o
d
p
)
,
又
对
1
≤
i
≤
p
−
1
,
有
1
≤
j
≤
p
−
1
,
满
足
i
j
≡
1
(
m
o
d
p
)
,
M
i
2
≡
M
j
2
(
m
o
d
p
)
,
则
2
M
T
=
p
∑
i
=
1
p
−
1
M
i
(
p
−
i
)
≡
p
∑
i
=
1
p
−
1
(
−
M
i
2
)
≡
−
p
∑
i
=
1
p
−
1
M
j
2
≡
−
p
M
(
p
−
1
)
p
(
2
p
−
1
)
6
≡
0
(
m
o
d
p
2
)
,
即
2
M
(
r
−
s
)
p
s
≡
0
(
m
o
d
p
2
)
,
r
−
s
≡
0
(
m
o
d
p
3
)
证：令\,T=1+\dfrac{1}{2}+\cdots+\dfrac{1}{p-1}=\dfrac{r}{ps}-\dfrac{1}{p}=\dfrac{r-s}{ps}\,,则\,2T=(1+\dfrac{1}{p-1})+(\dfrac{1}{2}+\dfrac{1}{p-2})+\cdots+(\dfrac{1}{p-1}+1)=p\begin{aligned}\sum_{i=1}^{p-1}\dfrac{1}{i(p-i)}\end{aligned}\,,设\,2^2,3^2,\cdots,(p-1)^2\,的最小公倍数为\,M\,,则由\,M\,与\,p\,互质,得\,i(p-i)M \equiv -i^2M \pmod{p}\,,得\,\dfrac{M}{i(p-i)} \equiv -\dfrac{M}{i^2} \!\! \pmod{p}\,,又对\,1 \le i \le p-1\,,有\,1 \le j \le p-1\,,满足\,ij \equiv 1 \!\! \pmod{p}\,,\,\dfrac{M}{i^2} \equiv Mj^2 \!\! \pmod{p}\,,则\,2MT=p\begin{aligned}\sum_{i=1}^{p-1}\dfrac{M}{i(p-i)}\end{aligned} \equiv p\begin{aligned}\sum_{i=1}^{p-1}(-\dfrac{M}{i^2})\end{aligned} \equiv -p\begin{aligned}\sum_{i=1}^{p-1}Mj^2\end{aligned} \equiv -\dfrac{pM(p-1)p(2p-1)}{6} \equiv 0 \!\! \pmod{p^2}\,,即\,\dfrac{2M(r-s)}{ps} \equiv 0 \!\! \pmod{p^2}\,,r-s \equiv 0 \!\!\pmod{p^3}
证：令T=1+21+⋯+p−11=psr−p1=psr−s,则2T=(1+p−11)+(21+p−21)+⋯+(p−11+1)=pi=1∑p−1i(p−i)1,设22,32,⋯,(p−1)2的最小公倍数为M,则由M与p互质,得i(p−i)M≡−i2M(modp),得i(p−i)M≡−i2M(modp),又对1≤i≤p−1,有1≤j≤p−1,满足ij≡1(modp),i2M≡Mj2(modp),则2MT=pi=1∑p−1i(p−i)M≡pi=1∑p−1(−i2M)≡−pi=1∑p−1Mj2≡−6pM(p−1)p(2p−1)≡0(modp2),即ps2M(r−s)≡0(modp2),r−s≡0(modp3)设
p
\,p\,
p是大于
5
\,5\,
5的质数，
x
,
y
\,x,y\,
x,y是自然数，证明：
T
=
∑
k
=
1
p
−
1
1
(
p
x
+
k
)
2
−
∑
k
=
1
p
−
1
1
(
p
y
+
k
)
2
\,\begin{aligned}T=\sum_{k=1}^{p-1}\dfrac{1}{(px+k)^2}-\sum_{k=1}^{p-1}\dfrac{1}{(py+k)^2}\end{aligned}\,
T=k=1∑p−1(px+k)21−k=1∑p−1(py+k)21写成既约分数后，分子是
p
3
\,p^3\,
p3的倍数。
证
：
T
=
p
⋅
∑
k
=
1
p
−
1
(
y
−
x
)
(
p
(
x
+
y
)
+
2
k
)
(
p
x
+
k
)
2
(
p
y
+
k
)
2
,
则
只
需
证
M
⋅
∑
k
=
1
p
−
1
p
(
y
2
−
x
2
)
+
2
k
(
y
−
x
)
(
p
x
+
k
)
2
(
p
y
+
k
)
2
≡
0
(
m
o
d
p
2
)
,
其
中
M
是
各
分
数
的
分
母
的
最
小
公
倍
数
,
且
p
∤
M
。
[
1
]
因
为
k
≢
0
(
m
o
d
p
)
,
则
存
在
唯
一
的
h
,
1
≤
h
≤
p
−
1
,
使
得
k
h
≡
1
(
m
o
d
p
)
,
当
k
取
遍
{
1
,
2
,
⋯
,
p
−
1
}
,
h
也
取
遍
{
1
,
2
,
⋯
,
p
−
1
}
,
且
M
(
p
x
+
k
)
2
(
p
y
+
k
)
2
h
4
≡
M
(
m
o
d
p
)
,
于
是
M
∑
k
=
1
p
−
1
1
(
p
x
+
k
)
2
(
p
y
+
k
)
2
≡
M
∑
h
=
1
p
−
1
h
4
≡
0
(
m
o
d
p
)
(
由
于
∑
h
=
0
p
−
1
1
=
p
≡
0
(
m
o
d
p
)
(
1
)
,
∑
h
=
0
p
−
1
h
=
p
(
p
−
1
)
2
≡
0
(
m
o
d
p
)
(
2
)
,
∑
h
=
0
p
−
1
h
2
=
(
p
−
1
)
p
(
2
p
−
1
)
6
≡
0
(
m
o
d
p
)
(
3
)
,
∑
h
=
0
p
−
1
h
3
=
(
p
(
p
−
1
)
2
)
2
≡
0
(
m
o
d
p
)
(
4
)
,
结
合
(
1
)
,
(
2
)
,
(
3
)
,
(
4
)
,
得
0
≡
∑
h
=
0
p
−
1
(
(
h
+
1
)
5
−
h
5
)
≡
5
∑
h
=
0
p
−
1
h
4
(
m
o
d
p
)
,
则
∑
h
=
0
p
−
1
h
4
≡
0
(
m
o
d
p
)
)
从
而
M
∑
k
=
0
p
−
1
p
(
y
2
−
x
2
)
(
p
x
+
k
)
2
(
p
y
+
k
)
2
≡
0
(
m
o
d
p
)
(
5
)
[
2
]
令
t
=
2
(
x
+
y
)
,
M
1
为
p
k
2
t
+
k
3
(
k
=
1
,
2
,
⋯
,
p
−
1
)
的
最
小
公
倍
数
。
显
然
p
∤
M
1
,
则
有
M
M
1
(
p
x
+
k
)
2
(
p
y
+
k
)
2
≡
M
M
1
(
k
3
+
p
t
k
2
)
k
(
m
o
d
p
2
)
,
所
以
2
∑
k
=
1
p
−
1
k
M
M
1
(
p
x
+
k
)
2
(
p
y
+
k
)
2
≡
2
∑
k
=
1
p
−
1
M
M
1
k
3
+
p
t
k
2
≡
M
M
1
(
∑
k
=
1
p
−
1
1
k
3
+
p
t
k
2
+
∑
k
=
1
p
−
1
1
(
p
−
k
)
3
+
p
t
(
p
−
k
)
2
)
M
M
1
∑
k
=
1
p
−
1
p
(
3
+
2
t
)
k
2
(
k
3
+
p
t
k
2
)
(
(
p
−
k
)
3
+
p
t
(
p
−
k
)
2
)
(
m
o
d
p
)
(
6
)
令
M
2
为
1
6
,
2
6
,
⋯
,
(
p
−
1
)
6
的
最
小
公
倍
数
。
显
然
p
∤
M
2
,
又
M
2
(
k
3
+
p
t
k
2
)
(
(
p
−
k
)
3
+
p
t
(
p
−
k
)
2
)
≡
−
k
6
M
2
(
m
o
d
p
)
,
于
是
∑
k
=
1
p
−
1
M
M
1
M
2
k
2
(
k
3
+
p
t
k
2
)
(
(
p
−
k
)
3
+
p
t
(
p
−
k
)
2
)
≡
−
∑
k
=
1
p
−
1
M
M
1
M
2
k
4
≡
−
∑
h
=
1
p
−
1
M
M
1
M
2
h
4
≡
0
(
m
o
d
p
)
(
7
)
由
(
6
)
,
(
7
)
式
,
得
M
∑
k
=
1
p
−
1
2
k
(
y
−
x
)
(
p
x
+
k
)
2
(
p
y
+
k
)
2
≡
0
(
m
o
d
p
)
(
8
)
由
(
5
)
,
(
8
)
知
命
题
成
立
。
证：\begin{aligned}T=p\cdot\sum_{k=1}^{p-1}\dfrac{(y-x)(p(x+y)+2k)}{(px+k)^2(py+k)^2}\end{aligned}\,,则只需证\,\begin{aligned}M\cdot \sum_{k=1}^{p-1}\dfrac{p(y^2-x^2)+2k(y-x)}{(px+k)^2(py+k)^2}\end{aligned} \equiv 0 \!\! \pmod{p^2}\,,\\其中\,M\,是各分数的分母的最小公倍数,且\,p \nmid M\,。[1]\,因为\,k \not \equiv 0 \!\! \pmod{p}\,,则存在唯一的\,h\,,\,1 \le h \le p-1\,,使得\,kh \equiv 1 \!\! \pmod{p}\,,当\,k\,取遍\{1,2,\cdots,p-1\}\,,\,h\,也取遍\{1,2,\cdots,p-1\}\,,且\,M(px+k)^2(py+k)^2h^4 \equiv M \!\! \pmod{p}\,,\\于是\,M\begin{aligned}\sum_{k=1}^{p-1}\dfrac{1}{(px+k)^2(py+k)^2}\end{aligned} \equiv M\begin{aligned}\sum_{h=1}^{p-1}h^4\end{aligned} \equiv 0 \!\! \pmod{p}\,(由于\,\begin{aligned}\sum_{h=0}^{p-1}1 = p \equiv 0 \!\!\!\!\! \pmod{p} \end{aligned}\,\,(1)\,,\,\begin{aligned}\sum_{h=0}^{p-1}h=\dfrac{p(p-1)}{2}\end{aligned} \equiv 0 \!\! \pmod{p}\,\,(2)\,,\,\begin{aligned}\sum_{h=0}^{p-1}h^2 = \dfrac{(p-1)p(2p-1)}{6} \equiv 0 \!\!\!\!\! \pmod{p}\end{aligned}\,\,(3)\,,\,\begin{aligned}\sum_{h=0}^{p-1}h^3 = (\dfrac{p(p-1)}{2})^2 \equiv 0 \!\!\!\!\! \pmod{p}\end{aligned}\,\,(4)\,,\\结合\,(1),(2),(3),(4)\,,得\,\begin{aligned}0 \equiv \sum_{h=0}^{p-1}((h+1)^5-h^5) \equiv 5\sum_{h=0}^{p-1}h^4 \!\!\!\!\! \pmod{p}\end{aligned}\,,则\,\begin{aligned}\sum_{h=0}^{p-1}h^4 \equiv 0 \!\!\!\!\! \pmod{p}\end{aligned}\,\,)\\ 从而\,\begin{aligned}M\sum_{k=0}^{p-1}\dfrac{p(y^2-x^2)}{(px+k)^2(py+k)^2} \equiv 0 \!\!\!\!\! \pmod{p}\end{aligned}\,\,\,(5)\\ [2]\,令\,t=2(x+y)\,,\,M_1\,为\,pk^2t+k^3\,(k=1,2,\cdots,p-1)\,的最小公倍数。显然\,p \nmid M_1\,,则有\,M\!M_1(px+k)^2(py+k)^2 \equiv M\!M_1(k^3+ptk^2)k \!\! \pmod{p^2}\,,所以\\ \begin{aligned}&2\sum_{k=1}^{p-1}\dfrac{kM\!M_1}{(px+k)^2(py+k)^2} \equiv 2\sum_{k=1}^{p-1}\dfrac{M\!M_1}{k^3+ptk^2} \equiv M\!M_1(\sum_{k=1}^{p-1}\dfrac{1}{k^3+ptk^2}+\sum_{k=1}^{p-1}\dfrac{1}{(p-k)^3+pt(p-k)^2})\\ & M\!M_1\sum_{k=1}^{p-1}\dfrac{p(3+2t)k^2}{(k^3+ptk^2)((p-k)^3+pt(p-k)^2)} \!\!\!\!\! \pmod{p}\,\,\,(6)\end{aligned}\\ 令\,M_2\,为\,1^6,2^6,\cdots,(p-1)^6\,的最小公倍数。显然\,p \nmid M_2\,,又\,M_2(k^3+ptk^2)((p-k)^3+pt(p-k)^2) \equiv -k^6M_2 \!\! \pmod{p}\,,\\于是\,\begin{aligned}\sum_{k=1}^{p-1}\dfrac{M\!M_1M_2k^2}{(k^3+ptk^2)((p-k)^3+pt(p-k)^2)} \equiv -\sum_{k=1}^{p-1}\dfrac{M\!M_1M_2}{k^4} \equiv -\sum_{h=1}^{p-1}M\!M_1M_2h^4 \equiv 0 \!\!\!\!\! \pmod{p}\,\,\,(7)\end{aligned}\\由\,(6),(7)\,式,得\,\begin{aligned}M\sum_{k=1}^{p-1}\dfrac{2k(y-x)}{(px+k)^2(py+k)^2} \equiv 0 \!\!\!\!\! \pmod{p}\,\,\,(8)\end{aligned}\,\\由\,(5),(8)\,知命题成立。
证：T=p⋅k=1∑p−1(px+k)2(py+k)2(y−x)(p(x+y)+2k),则只需证M⋅k=1∑p−1(px+k)2(py+k)2p(y2−x2)+2k(y−x)≡0(modp2),其中M是各分数的分母的最小公倍数,且p∤M。[1]因为k≡0(modp),则存在唯一的h,1≤h≤p−1,使得kh≡1(modp),当k取遍{1,2,⋯,p−1},h也取遍{1,2,⋯,p−1},且M(px+k)2(py+k)2h4≡M(modp),于是Mk=1∑p−1(px+k)2(py+k)21≡Mh=1∑p−1h4≡0(modp)(由于h=0∑p−11=p≡0(modp)(1),h=0∑p−1h=2p(p−1)≡0(modp)(2),h=0∑p−1h2=6(p−1)p(2p−1)≡0(modp)(3),h=0∑p−1h3=(2p(p−1))2≡0(modp)(4),结合(1),(2),(3),(4),得0≡h=0∑p−1((h+1)5−h5)≡5h=0∑p−1h4(modp),则h=0∑p−1h4≡0(modp))从而Mk=0∑p−1(px+k)2(py+k)2p(y2−x2)≡0(modp)(5)[2]令t=2(x+y),M1为pk2t+k3(k=1,2,⋯,p−1)的最小公倍数。显然p∤M1,则有MM1(px+k)2(py+k)2≡MM1(k3+ptk2)k(modp2),所以2k=1∑p−1(px+k)2(py+k)2kMM1≡2k=1∑p−1k3+ptk2MM1≡MM1(k=1∑p−1k3+ptk21+k=1∑p−1(p−k)3+pt(p−k)21)MM1k=1∑p−1(k3+ptk2)((p−k)3+pt(p−k)2)p(3+2t)k2(modp)(6)令M2为16,26,⋯,(p−1)6的最小公倍数。显然p∤M2,又M2(k3+ptk2)((p−k)3+pt(p−k)2)≡−k6M2(modp),于是k=1∑p−1(k3+ptk2)((p−k)3+pt(p−k)2)MM1M2k2≡−k=1∑p−1k4MM1M2≡−h=1∑p−1MM1M2h4≡0(modp)(7)由(6),(7)式,得Mk=1∑p−1(px+k)2(py+k)22k(y−x)≡0(modp)(8)由(5),(8)知命题成立。
Note : 对于熟练的人，在模
m
\,m\,
m的模运算过程中不但分子中
m
\,m\,
m的倍数可以略去，分母中
m
\,m\,
m的倍数也可略去。
于
是
(
8
)
推
导
过
程
可
写
成
：
∑
k
=
1
p
−
1
2
k
(
p
x
+
k
)
2
(
p
y
+
k
)
2
≡
∑
k
=
1
p
−
1
2
k
k
4
+
2
p
(
x
+
y
)
k
3
=
∑
k
=
1
p
−
1
(
1
k
3
+
p
t
k
2
+
1
(
p
−
k
)
3
+
p
t
(
p
−
k
)
2
)
≡
p
∑
k
=
1
p
−
1
3
k
2
+
2
t
k
2
−
k
6
=
p
∑
k
=
1
p
−
1
3
+
2
t
k
4
≡
p
∑
h
=
1
p
−
1
(
3
+
2
t
)
h
4
≡
0
(
m
o
d
p
2
)
\,\\于是\,(8)\,推导过程可写成：\\\begin{aligned}&\sum_{k=1}^{p-1}\dfrac{2k}{(px+k)^2(py+k)^2} \equiv \sum_{k=1}^{p-1}\dfrac{2k}{k^4+2p(x+y)k^3} = \sum_{k=1}^{p-1}(\dfrac{1}{k^3+ptk^2}+\dfrac{1}{(p-k)^3+pt(p-k)^2}) \\& \equiv p\sum_{k=1}^{p-1}\dfrac{3k^2+2tk^2}{-k^6}=p\sum_{k=1}^{p-1}\dfrac{3+2t}{k^4} \equiv p\sum_{h=1}^{p-1}(3+2t)h^4 \equiv 0 \!\! \pmod{p^2}\end{aligned}\,
于是(8)推导过程可写成：k=1∑p−1(px+k)2(py+k)22k≡k=1∑p−1k4+2p(x+y)k32k=k=1∑p−1(k3+ptk21+(p−k)3+pt(p−k)21)≡pk=1∑p−1−k63k2+2tk2=pk=1∑p−1k43+2t≡ph=1∑p−1(3+2t)h4≡0(modp2)
简化剩余系：乘除法运算的封闭性
若
a
,
b
\,a,b\,
a,b都与
n
\,n\,
n互质，则
a
b
\,ab\,
ab也与
n
\,n\,
n互质，因此在模
n
\,n\,
n的简化剩余系中可以做乘法。
在模
n
\,n\,
n的简化剩余系中也可以做除法，即设
a
,
b
\,a,b\,
a,b为模
n
\,n\,
n的简化剩余系中两个元素，则一定存在唯一的
x
\,x\,
x使得
a
x
≡
b
(
m
o
d
n
)
\,ax \equiv b \!\! \pmod{n}\,
ax≡b(modn)
证
：
(
1
)
存
在
性
：
设
b
1
,
b
2
,
⋯
,
b
φ
(
n
)
为
一
简
化
剩
余
系
,
则
由
于
a
与
n
互
质
,
则
a
b
1
,
a
b
2
,
⋯
,
a
b
φ
(
n
)
互
不
同
余
,
并
且
均
与
n
互
质
,
则
它
们
也
是
模
n
的
简
化
剩
余
系
,
其
中
必
有
一
个
与
b
在
同
一
类
中
,
即
a
x
≡
b
(
m
o
d
n
)
有
解
,
存
在
性
成
立
；
(
2
)
唯
一
性
：
若
在
b
1
,
b
2
,
⋯
,
b
φ
(
n
)
中
有
另
一
个
x
′
使
得
a
x
′
≡
b
(
m
o
d
n
)
,
两
式
相
减
得
a
(
x
−
x
′
)
≡
0
(
m
o
d
n
)
,
由
于
(
a
,
n
)
=
1
,
得
x
=
x
′
,
唯
一
性
成
立
。
证：(1)\,存在性：设\,b_1,b_2,\cdots,b_{\varphi(n)}\,为一简化剩余系,则由于\,a\,与\,n\,互质,则\,ab_1,ab_2,\cdots,ab_{\varphi(n)}\,互不同余,并且均与\,n\,互质,\\则它们也是模\,n\,的简化剩余系,其中必有一个与\,b\,在同一类中,即\,ax \equiv b \!\! \pmod{n}\,有解,存在性成立；\\(2)\,唯一性：若在\,b_1,b_2,\cdots,b_{\varphi(n)}\,中有另一个\,x'\,使得\,ax' \equiv b \!\! \pmod{n}\,,两式相减得\,a(x-x') \equiv 0 \!\! \pmod{n}\,,由于\,(a\,,n)=1\,,得\,x=x'\,,唯一性成立。
证：(1)存在性：设b1,b2,⋯,bφ(n)为一简化剩余系,则由于a与n互质,则ab1,ab2,⋯,abφ(n)互不同余,并且均与n互质,则它们也是模n的简化剩余系,其中必有一个与b在同一类中,即ax≡b(modn)有解,存在性成立；(2)唯一性：若在b1,b2,⋯,bφ(n)中有另一个x′使得ax′≡b(modn),两式相减得a(x−x′)≡0(modn),由于(a,n)=1,得x=x′,唯一性成立。
例题
设
r
1
,
r
2
,
⋯
,
r
φ
(
m
)
\,r_1,r_2,\cdots,r_{\varphi(m)}\,
r1,r2,⋯,rφ(m)是模
m
\,m\,
m的简化剩余系，且
A
=
r
1
r
2
⋯
r
φ
(
m
)
\,A=r_1r_2\cdots r_{\varphi(m)}\,
A=r1r2⋯rφ(m)，试证：
A
2
≡
1
(
m
o
d
m
)
\,A^2 \equiv 1 \!\! \pmod{m}\,
A2≡1(modm)
证
：
对
于
模
m
的
简
化
剩
余
系
的
任
一
整
数
r
i
(
i
=
1
,
2
,
⋯
,
φ
(
m
)
)
,
该
模
m
的
简
化
剩
余
系
中
存
在
唯
一
的
x
,
使
得
r
i
x
≡
1
(
m
o
d
m
)
,
设
其
中
有
k
(
k
为
偶
数
)
个
r
i
的
x
是
它
自
身
,
即
r
i
2
≡
1
(
m
o
d
m
)
,
其
余
的
r
i
的
x
不
是
它
自
身
,
则
(
∏
i
=
1
k
r
i
2
)
(
∏
i
=
k
+
1
φ
(
m
)
r
i
)
≡
1
(
m
o
d
m
)
(
1
)
,
又
(
∏
i
=
k
+
1
φ
(
m
)
r
i
)
≡
1
(
m
o
d
m
)
(
2
)
,
(
1
)
×
(
2
)
即
知
命
题
成
立
。
证：对于模\,m\,的简化剩余系的任一整数\,r_i\,(i=1,2,\cdots,\varphi(m))\,,该模\,m\,的简化剩余系中存在唯一的\,x\,,使得\,r_ix \equiv 1 \!\! \pmod{m}\,,设其中有\,k\,(\,k\,为偶数)个\,r_i\,的\,x\,是它自身,即\,r_i^2 \equiv 1 \!\! \pmod{m}\,,其余的\,r_i\,的\,x\,不是它自身,\\则\,(\begin{aligned}\prod_{i=1}^kr_i^2\end{aligned})(\begin{aligned}\prod_{i=k+1}^{\varphi(m)}\end{aligned}r_i) \equiv 1 \!\! \pmod{m}\, \quad (1)\,,又\,(\begin{aligned}\prod_{i=k+1}^{\varphi(m)}\end{aligned}r_i) \equiv 1 \!\! \pmod{m}\, \quad (2)\,,\,(1)\,\times\,(2)\,即知命题成立。
证：对于模m的简化剩余系的任一整数ri(i=1,2,⋯,φ(m)),该模m的简化剩余系中存在唯一的x,使得rix≡1(modm),设其中有k(k为偶数)个ri的x是它自身,即ri2≡1(modm),其余的ri的x不是它自身,则(i=1∏kri2)(i=k+1∏φ(m)ri)≡1(modm)(1),又(i=k+1∏φ(m)ri)≡1(modm)(2),(1)×(2)即知命题成立。证明：(威尔逊定理)
p
\,p\,
p为质数的充要条件是
(
p
−
1
)
!
≡
−
1
(
m
o
d
p
)
\,(p-1)! \equiv -1 \!\! \pmod{p}\,
(p−1)!≡−1(modp)
证
：
(
1
)
必
要
性
：
当
p
=
2
或
3
时
,
定
理
显
然
成
立
。
若
r
是
下
列
p
−
3
个
数
：
2
,
3
,
⋯
,
p
−
2
的
中
的
一
个
,
则
在
这
些
数
中
必
有
一
个
数
s
≠
r
,
使
得
r
s
≡
1
(
m
o
d
p
)
(
事
实
上
,
r
,
2
r
,
3
r
,
⋯
,
(
p
−
1
)
r
为
模
p
的
一
个
简
化
剩
余
系
,
且
其
中
存
在
唯
一
一
个
数
s
r
,
满
足
s
r
≡
1
(
m
o
d
p
)
,
由
于
2
≤
r
≤
p
−
2
,
故
s
≠
1
,
p
−
1
,
此
外
,
s
≠
r
,
否
则
有
r
2
≡
1
(
m
o
d
p
)
,
即
(
r
+
1
)
(
r
−
1
)
≡
0
(
m
o
d
p
)
,
故
应
有
p
∣
(
r
+
1
)
或
p
∣
(
r
−
1
)
,
但
2
≤
r
≤
p
−
2
,
矛
盾
。
)
又
因
为
r
s
=
s
r
,
即
r
和
s
是
成
对
出
现
的
,
故
2
,
3
,
⋯
,
p
−
2
这
p
−
3
个
数
共
可
分
为
p
−
3
2
对
,
每
一
对
数
的
乘
积
均
模
p
同
余
1
,
因
此
2
⋅
3
⋯
(
p
−
2
)
≡
1
p
−
3
2
≡
1
(
m
o
d
p
)
,
即
(
p
−
2
)
!
≡
1
(
m
o
d
p
)
,
从
而
(
p
−
1
)
!
≡
−
1
(
m
o
d
p
)
;
(
2
)
充
分
性
：
反
证
法
。
假
设
p
为
合
数
,
则
p
有
一
个
真
因
数
d
(
1
<
d
<
p
且
d
∣
p
)
,
由
d
≤
p
−
1
,
知
d
∣
(
p
−
1
)
!
,
又
(
p
−
1
)
!
≡
−
1
(
m
o
d
p
)
,
故
d
∣
1
,
得
d
=
1
,
这
与
d
>
1
矛
盾
,
因
此
p
必
为
质
数
。
证：(1)\,必要性：当\,p=2\,或\,3\,时,定理显然成立。若\,r\,是下列\,p-3\,个数：2,3, \cdots,p-2\,的中的一个,则在这些数中必有一个数\,s \ne r\,,使得\,rs \equiv 1 \!\! \pmod{p}\,(事实上,\,r,2r,3r,\cdots,(p-1)r\,为模\,p\,的一个简化剩余系,且其中存在唯一一个数\,sr\,,满足\,sr \equiv 1\!\! \pmod{p}\,,由于\,2 \le r \le p-2\,,故\,s \ne 1,p-1\,,此外,\,s \ne r\,,否则有\,r^2 \equiv 1 \!\! \pmod{p}\,,即\,(r+1)(r-1) \equiv 0 \!\! \pmod{p}\,,故应有\,p \mid (r+1)\,或\,p \mid (r-1)\,,但\,2 \le r \le p-2\,,矛盾。)又因为\,rs=sr\,,即\,r\,和\,s\,是成对出现的,故\,2,3,\cdots,p-2\,这\,p-3\,个数共可分为\,\dfrac{p-3}{2}\,对,每一对数的乘积均模\,p\,同余\,1\,,因此\,2\cdot3\cdots(p-2) \equiv 1^{\frac{p-3}{2}} \equiv 1 \!\! \pmod{p}\,,即\,(p-2)! \equiv 1 \!\! \pmod{p}\,,从而\,(p-1)! \equiv -1 \!\! \pmod{p}\,;(2)\,充分性：反证法。假设\,p\,为合数,则\,p\,有一个真因数\,d\,(1 \lt d \lt p\,且\,d \mid p\,)\,,由\,d \le p-1\,,知\,d \mid (p-1)!\,,又\,(p-1)! \equiv -1 \!\! \pmod{p}\,,故\,d \mid 1\,,得\,d=1\,,这与\,d \gt 1\,矛盾,因此\,p\,必为质数。
证：(1)必要性：当p=2或3时,定理显然成立。若r是下列p−3个数：2,3,⋯,p−2的中的一个,则在这些数中必有一个数s=r,使得rs≡1(modp)(事实上,r,2r,3r,⋯,(p−1)r为模p的一个简化剩余系,且其中存在唯一一个数sr,满足sr≡1(modp),由于2≤r≤p−2,故s=1,p−1,此外,s=r,否则有r2≡1(modp),即(r+1)(r−1)≡0(modp),故应有p∣(r+1)或p∣(r−1),但2≤r≤p−2,矛盾。)又因为rs=sr,即r和s是成对出现的,故2,3,⋯,p−2这p−3个数共可分为2p−3对,每一对数的乘积均模p同余1,因此2⋅3⋯(p−2)≡12p−3≡1(modp),即(p−2)!≡1(modp),从而(p−1)!≡−1(modp);(2)充分性：反证法。假设p为合数,则p有一个真因数d(1
p
\,p\,
p为奇质数，试证：
1
2
⋅
3
2
⋯
(
p
−
2
)
2
≡
(
−
1
)
p
+
1
2
(
m
o
d
p
)
\,1^2\cdot 3^2 \cdots (p-2)^2 \equiv (-1)^{\frac{p+1}{2}} \!\! \pmod{p}\,
12⋅32⋯(p−2)2≡(−1)2p+1(modp)
证
：
当
p
为
奇
质
数
时
,
(
p
−
1
)
!
=
(
1
⋅
(
p
−
1
)
)
(
3
⋅
(
p
−
3
)
)
⋯
(
(
p
−
2
)
(
p
−
(
p
−
2
)
)
)
≡
(
−
1
)
p
−
1
2
⋅
1
2
⋅
3
2
⋯
(
p
−
2
)
2
(
m
o
d
p
)
,
由
威
尔
逊
定
理
,
知
(
p
−
1
)
!
≡
−
1
(
m
o
d
p
)
,
即
(
−
1
)
p
−
1
2
⋅
1
2
⋅
3
2
⋯
(
p
−
2
)
!
≡
−
1
(
m
o
d
p
)
,
因
此
命
题
成
立
。
证：当\,p\,为奇质数时,\,(p-1)! = (1\cdot (p-1))(3 \cdot (p-3))\cdots((p-2)(p-(p-2))) \equiv (-1)^{\frac{p-1}{2}}\cdot 1^2 \cdot 3^2\cdots(p-2)^2 \!\! \pmod{p}\,,由威尔逊定理,知\,(p-1)! \equiv -1 \!\! \pmod{p}\,,即\,(-1)^{\frac{p-1}{2}}\cdot 1^2\cdot 3^2\cdots(p-2)! \equiv -1 \!\! \pmod{p}\,,因此命题成立。
证：当p为奇质数时,(p−1)!=(1⋅(p−1))(3⋅(p−3))⋯((p−2)(p−(p−2)))≡(−1)2p−1⋅12⋅32⋯(p−2)2(modp),由威尔逊定理,知(p−1)!≡−1(modp),即(−1)2p−1⋅12⋅32⋯(p−2)!≡−1(modp),因此命题成立。设
p
,
n
\,p,n\,
p,n是正整数，且
p
≥
n
>
0
\,p \ge n \gt 0\,
p≥n>0，试证：
p
\,p\,
p为质数的充要条件是
(
n
−
1
)
!
(
p
−
n
)
!
≡
(
−
1
)
n
(
m
o
d
p
)
\,(n-1)!(p-n)! \equiv (-1)^n \!\! \pmod{p}\,
(n−1)!(p−n)!≡(−1)n(modp)
证
：
因
为
k
≡
−
(
p
−
k
)
(
m
o
d
p
)
,
所
以
(
n
−
1
)
!
≡
(
−
1
)
n
−
1
(
p
−
1
)
(
p
−
2
)
⋯
(
p
−
n
+
1
)
(
m
o
d
p
)
,
由
威
尔
逊
定
理
,
得
p
的
充
要
条
件
是
(
n
−
1
)
!
(
p
−
n
)
!
≡
(
−
1
)
n
−
1
(
p
−
1
)
⋯
(
p
−
n
+
1
)
(
p
−
n
)
!
≡
(
−
1
)
n
−
1
(
p
−
1
)
!
≡
(
−
1
)
n
−
1
(
−
1
)
≡
(
−
1
)
n
(
m
o
d
p
)
证：因为\,k \equiv -(p-k) \!\! \pmod{p}\,,所以\,(n-1)! \equiv (-1)^{n-1}(p-1)(p-2)\cdots(p-n+1) \!\! \pmod{p}\,,由威尔逊定理,得\,p\,的充要条件是\,(n-1) !(p-n)! \equiv (-1)^{n-1}(p-1)\cdots(p-n+1)(p-n)! \equiv (-1)^{n-1}(p-1)! \equiv (-1)^{n-1}(-1) \equiv (-1)^n \!\! \pmod{p}\,
证：因为k≡−(p−k)(modp),所以(n−1)!≡(−1)n−1(p−1)(p−2)⋯(p−n+1)(modp),由威尔逊定理,得p的充要条件是(n−1)!(p−n)!≡(−1)n−1(p−1)⋯(p−n+1)(p−n)!≡(−1)n−1(p−1)!≡(−1)n−1(−1)≡(−1)n(modp)
End