文章目录

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−1​h2​≡((p−1)!)261​p(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−1​i(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−1​i(p−i)M​​≡pi=1∑p−1​(−i2M​)​≡−pi=1∑p−1​Mj2​≡−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−1​h4​≡0(modp)(由于h=0∑p−1​1=p≡0(modp)​(1),h=0∑p−1​h=2p(p−1)​​≡0(modp)(2),h=0∑p−1​h2=6(p−1)p(2p−1)​≡0(modp)​(3),h=0∑p−1​h3=(2p(p−1)​)2≡0(modp)​(4),结合(1),(2),(3),(4),得0≡h=0∑p−1​((h+1)5−h5)≡5h=0∑p−1​h4(modp)​,则h=0∑p−1​h4≡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−1​k3+ptk2MM1​​≡MM1​(k=1∑p−1​k3+ptk21​+k=1∑p−1​(p−k)3+pt(p−k)21​)MM1​k=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)MM1​M2​k2​≡−k=1∑p−1​k4MM1​M2​​≡−h=1∑p−1​MM1​M2​h4≡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−1​k4+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−1​k43+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=r1​r2​⋯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,使得ri​x≡1(modm),设其中有k(k为偶数)个ri​的x是它自身,即ri2​≡1(modm),其余的ri​的x不是它自身,则(i=1∏k​ri2​​)(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(11矛盾,因此p必为质数。设

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