2
19
( x 2 1)2 2 x 2 2 x 2 2 1 p p p p p 从而p 1 mod 8 , 故p 1 mod 8 .
20
5
20.反证法, 假设只有有限个,设为p1 , p2 , , pk .
p 1 2
1, p 1(mod 4); 1, p 1(mod 4).
p a1 (mod 4); 解同余式组 p a2 (mod11). 得p 11a1 12a2 (mod 44). 11 从而有 ( ) 1 p 1, 5, 7, 9, 19(mod 44). 18 p
例2 设n是整数 ,
证明 : n2 1的任何奇因数都是 4m 1的形式.
证明 :由于奇数都可表示成奇素数之积, 而且任意多个 形如4m 1的整数之积也具有4m 1的形式.我们只需 证明 : 若素数p是n2 1的因数 , 则p具有4m 1的形式. 若p | n2 1, 则n2 1(mod p ),即 - 1是p的平方剩余,
4
1
a a (3) a a1 (mod p ) ( ) ( 1 ) p p a a1 (mod p )
(4) (
a1a2 an a a a ) ( 1 )( 2 ) ( n ) p p p p
p同时整除a，a1；或者p同时不整除a，a1 .
若a为p的平方剩余，则有 a
(5) ( ab a ) ( ), p b. p p
3
2
p 1 2
p 1 a (1) ( ) a 2 (mod p ) p
0， p a ； a ( ) 1， a是p的平方剩余； p 1， a是p的平方非剩余.
p 1 2
若 p|a , 显然成立；
若a是p的平方剩余，则a 1;
p 1 2
p 1 a a an ( 1 2 ) ( a1a2 an ) 2 证： p
1(mod p ).
a1 (
p 1 2
a2
p 1 2
an
p 1 2
a a1 (mod p ) a1 a pq
a a1 a2 )( ) ( n )(mod p ) p p p
练习：
1解 : 365 5 73, 方程等价于
1.判断x 2 1 mod 365 是否有解 , 若有求出解数 . 2.证明:x 4 1的奇素数p 1 mod 8 , 进而推出有无
x 2 1 mod 5 1 1 ,( ) ( ) 1, 原方程4个解 . 2 73 x 1 mod 73 5 2证明 : 设p是x 4 1的奇素数,即 从而p 1 mod 4 , 另一方面
q1, q2,, qk是互不相同的素数；
因为227 3(mod 8), 所以(
2 ) 1； 227
227 1 51 2 5 227 )( )( 1) 2 2 ( ) 1； 5 227 5 137 ) 1， 原方程无解. 从而 ( 227
(
16
4
例3 证明：形如8k 7（kZ）的素数有无穷多个。 解 用反证法，假设只有有限个素数p1, p2, , pt . 记 N = (p1p2pt)2 2， 显然 2 N . 则 (p1p2pt)2 2 (mod q)， 设q是N的一个奇素因数， 因此，由定理1有q 1或7(mod 8)。 若N的所有奇素因数都具有8k 1的形式， 则N也是8k 1的形式， 但是，由于任何奇数的平方对模8与1同余， 所以应有 N 1 2 1 (mod 8)。 这个矛盾说明，N至少有一个形如8k 7的奇素因数q。
q (3)若有某个qi = 2，用定理1推论判定 ( i ) 之值； p p q (4) 若qi 2，利用定理2将 ( i ) 的计算转化为计算 ( ); qi p qi ( ); (5) 重复以上步骤，直至求出每个 p k qi q (6) 计算 ( ) ( ) . p p i 1
15
p 1 q 1 2 2 p 1 q 1 2 2
3 11 13 解： ( 429 ) ( 3 11 13 ) ( 563 )( 563 )( 563 ) 563 563 ( 1) (
31 563 1 2 2
( 1)12 1.
( 563 )( 1)
所以， a1
p 1 2
(a pq )
p 1 2
a
p 1 2
1(mod p ).
又(
a1a2 an a a a )和( 1 )( 2 ) ( n ) 的取值只有0，±1， p p p p
即 a1也为p的平方剩余.
5
且p>2，故得证。
6
(5) (
ab 2 a ) ( ), p b p p
例1 已知563是素数，方程x2 429 (mod 563)是否有解。
5 2 3 5 3 例如： ( ) ( ) 1; ( ) 1. ( ) ( ) 1. 3 3 5 3 5 ( 1) 11 4 7 11 7 再如： ( ) ( ) 1; ( ) 1. ( ) ( ) 1. 7 7 11 7 11 ( 1)
定理1
下面的结论成立：
2
ab 2 a b2 证明： ( ) ( )( ) p p p
p 1 a ( )(b 2 ) 2 p
p 1 2 1 ， 当p 1(mod 8)， 2 (1) ( 1) 8 ；即 p 1， 当p 3(mod 8). p
3
111 5631 2 2
( 563 )(1)
11
131 5631 2 2
( 563 )
13
2 2 )( )( 4 ) (1)(1) 1 。 3 11 13
( 1)53 1.
13
方程有解。
14
n 一般地，若p是素数，计算 ( ) 可按以下步骤进行： p (1) 求出n0 n (mod p)，1 n0 p；
9 10
取p 11, a 7.
5 nk 7k [ ] [ ] 0 1 1 2 3 7 p k 1 k 1 11 7不是11的平方剩余. l
即y 2 1(mod 7). p-1 7-1 -1 -1 ( ) (-1) 2 , ( ) (-1) 2 1, p 7 故y 2 1(mod 7)无解 , 则原方程也无解 . (2) 5 x 2 7 x 11 5 x 2 30 x 35(mod 23),
故 x2 1
穷多个素数p 1 mod 8 . 3.证明 : 有无穷多个素数p 1 mod 4 . 4.证明 : n4 n2 1的素因数p 1 mod12 .
x
2
2
x 4 1 mod p


2
x4 1 x2 1 2 x2 2 x 2 mod p , p,2 x 1.
由以上推论知, p 4m 1.
(5, 23) 1, 故原方程等价于 x 2 6 x 7 ( x 3)2 16 0(mod 23),
令y x 3, 则原方程化为y 2 16(mod 23). 易知y 2 16(mod 23)有解 , 从而原方程有解 .
p 1 2
若a是p的平方非剩余，则a
p 1 2
1.
1 1 (2) ( ) 1, ( ) ( 1) (1)的特例. p p 注 : (2)式说明1永远是平方剩余;(3)式说明当p 4m 1时,
1是平方剩余,当p 4m 3(或4m 1)时, 1是平方非剩余.
(2) 将n0写成n0 = Q2q1q2qk的形式，其中QZ，
例2 判断方程x2 137 (mod 227)是否有解。
2 3 2 5 ( 1 ) ( 2 ) ( 5 ) 137 90 ) 解： ( )( )( 227 227 227 227 227 227 (
227 1 1 ) ( 1) 2 1; 227
5 nk 5k [ ] [ ] 0 0 1 1 2 4 p k 1 i 1 11 5是11的平方剩余; l
例1 判断下列同余方程是否有解.
(1) x 2 3 x 5 0(mod 7); (2)5 x 2 7 x 11 0(mod 23). 解 : (1) x 2 3 x 5 x 2 10 x 5 ( x 5)2 52 5(mod 7), 令y x 5, 则原方程化为y 2 20(mod 7),
17
例4 求以11为其二次剩余的所有奇素数p.
p 1 11 p ( ) ( ) ( 1) 2 , 解： 11 p 1, p 1, 2, 3,4,5(mod11); p 直接计算得 ( ) 11 1, p 1,2, 3, 4, 5(mod11).
( 1)
7 2 1
8
2
nk [ p ] a p1 (2) 若a为奇数， (a, p) 1, 则 (1)k 1 ，其中l . 2 p
l
由定理1的(1)式立刻得出 推论 当p 8m 1时, 2是平方剩余,当p 8m 3时,2是
平方非剩余.
例如：取p 11, a 5.
所以有 ( 1 ) 1， ( 2 ) 1， ( 3 ) 1， ( 4 ) 1， ( 5 ) 0. 5 5 5 5 5
2
1
二、基本性质
a (1) ( ) a (mod p ); p p 1 1 1 (2) ( ) 1, ( ) ( 1) 2 ; p p a a (3) a a1 (mod p ) ( ) ( 1 ); p p a1a2 an a a1 a2 (4) ( ) ( )( ) ( n ); p p p p