第五章 二次同余式与
平方剩余

本章的目的就是讨论二次同余式.首先把问 题归结到讨论形式如：x2≡a (mod m)的同余 式，从而引入平方剩余与平方非剩余的概
念. 再利用勒让德符号及雅克比符号讨论
m是单质数的情形.
2
§1 一般二次同余式
设 p 是奇质数.设 p | a,二 次 同 余 式 的 一 般 形 式 是 ax 2 bx c 0 (mod p ). 由于p | 4a, 所 以 ( 1 ) 和 同 余 式 4a( ax 2 bx c ) 0 (mod p )的解 相 同 , 上 式 可 写 成 ( 2 ax b) 2 b 2 4ac (mod p ). (2) (1)
( i v ) x 63 (mod 187).
2
14
§3 Legendre符号, Gauss二次互反律
a 定 义 勒 让 德(Legendre) 符 号( ) ( 读 作 a 对 p 的 勒 让 德 符 号) p 是 一 个 对 于 给 定 的 单 质 数 定 义 在 一 切 整 数 a 上 的 函 数, 它 的 值规定如下： 1, 当 a 是 模 p 的 平 方 剩 余 ； a ( ) 1, 当 a 是 模 p 的 平 方 非 剩 余 ； p 0, 当 p a .
推论 3 -1是模 p的平方剩余的充要条件是 p 1 (mod 4);当 p 1 (mod 4) 时 , p 1 2 ( ( ) ! ) 1 ( m o d p ). 2 (13)
10
证 存在性 对任一a , p | a ,式 ( 9 ) 或 ( 1 0 ) 有 且 仅 有 一 式 成 立 . 由 费 马- 欧 拉 定 理 知 a 有(a 及(a
9
定 理 2 (欧 拉 判 别 条 件) 设 质 数 p 2, p | a .那么, a 是模 p 的 平方剩余的充要条件是a
( p 1)/2
1 ( m o d p) ; ( 9 )
a 是模 p的平方非剩余的充要条件是 a
( p 1)/2
1 ( m o d p) .
(10)
由 于 ( - j ) 2 j 2 (mo d p ),所 以 a 是 模 p 的 平 方 剩 余 当 且 仅 当 a 12 , ,( p 1 p 1 2 1) 2或( ) (mod p)(7).当 1 i j ( p 1) / 2 时 , 2 2
2 i2 j ( mod p )( 8). 所 以 式 ( 7 ) 给 出 了 模 p 的 全 部 平 方 剩 余 , 共
Hale Waihona Puke 15定 理 Legendre 符 号 有 以 下 性 质 ： a pa (i) ( ) ( ); p p a ( p 1)/2 (i i) ( ) a (mod p); p ac a c (i i i) ( ) ( )( ); p p p a2 (i v)当 p | ( ) 1; a时 ， p 1 1 (v) ( ) 1, ( ) ( 1) ( p 1)/2 ; p p
有( p 1) / 2个 . 由 于 模 p 的 简 化 剩 余 系 有 p 1个 数 , 所 以 另 外 的 ( p 1) / 2 个 必 为 模 p 的 平 方 非 剩 余 , 这 就 证 明 前 一 半 结 论 . 当 a 是 模 p 的 平 方 剩 余 时 , 由 式 ( 7 ) 及 ( 8 ) 知 , 必 有 惟 一 的 i, 使 x i (mod p)是 ( 5 ) 的 解 , 进 而 就 推 出 在 简 化 剩 余 系 ( 6 ) 中 有 且 仅 有 x i (mo d p )是 ( 5 ) 的 解 , 即 ( 5 ) 的 解 数 为2.
8
例 1 求 p 11,17,19,29的 平 方 剩 余 与 平 方 非 剩 余 . j 1 2 3 4 5 d j 2 (mod 11) 1 4 2 5 3 模11的平方剩余是:1， -2 , 3 , 4 , 5 ; 平 方 非 剩 余 是 : - 1 , 2,-3,-4,-5 j 1 2 3 4 5 6 7 8 d j 2 (mod 17) 1 4 8 1 8 2 2 4 模17的平方剩余是: 1， 2, 4, 8;平方非剩余是: 3, 5 , 6 , 7 .
19
q p 由 Legendre 符 号 知 , ( )和( )分 别 刻 画 了 同 余 p q 方 程 x 2 q (mod p)和 x 2 p (mod q)是 否 有 解 , 即 q 是否是模p的二次剩余和 p 是否是模q的二次剩余， 这 里 正 好 是 模 和 剩 余 互 换 了 位 置 . 定 理3 就 是 刻 画 了这两者之间的关系,所以称为二次互反律. 二次互反律是初等数论中最重要的定理之一. 它 不 仅 可 用 来 计 算 Legendre 符 号 , 而 且 它 有 重 要 理论价值.
11
充分性：设式(9)成立,这时必有p | a .考 虑 一 次 同 余 式 bx a ( m o d p )(12). 由 定 理 及 p | a 知,对于式(6)给出的模p的 简 化 剩 余 系 中 的 每 个 j ,当 b j时 , 必 有 惟 一 的 x x j 属 于 简 化 剩余系(6),使得式(12)成立.若a不是模p的平方剩余,则必有 j x j , 这 样 简 化 剩 余 系 ( 6 ) 中 的 p 1个 数 就 可 按 j , x j 作 为 一 对 , 两 两 分 完 . 因 此 有( p 1)! a a
5
例 如 , 当 p 3时 , a 1 (mod 3)是 模 3 的 平 方 剩 余 ， a 1 (mod 3) 是 模 3 的 平 方 非 剩 余 . 当 p 5 时 , a 1, 1 (mod 5)是 模 5 的 平 方 剩 余 ， a 2, 2 (mod 5) 是 模 5 的 平 方 非 剩 余 . 当 p 7 时 , a 1,2, 3 (mod 7)是 模 7 的 平 方 剩 余 ， a 1, 2,3 (mod 7) 是 模 7 的 平 方 非 剩 余 .
4
§2 平方剩余和平方非剩余
定 义 1 设 质 数 p 2, a 是 整 数 , p | a .如果 同 余 式 x 2 a (mod p) 有 解 , 则 称 a 是 模 p 的 平 方 ( 二 次) 剩 余 ; 若 无 解 , 则 称 a 是 模 p 的 平 方 ( 二 次) 非 剩 余 .
18
定 理3 ( G a u s s 二 次 互 反 律 ) 设 p, q 均 为 单 质 数 , ( p, q ) 1,则 q ( p 1)/2( q 1)/2 p ( ) ( 1) ( ). p q 定 理3 表 明 : 两 个 奇 数 p, q,只 要 有 一 个 数 q p 1 （ m o d 4 ) , 就 必 有( ) ( );当 且 仅 当 它 们 p q q p 都 是 4k 3 形 式 的 数 时 , 才 有( ) ( ). p q
( p 1)/2 ( p 1)/2
( m o d p ) . 由 wi l son 定 理 知
1( m o d p ).但 这 和 ( 9 ) 矛 盾 . 所 以 必 有 某 一 j0 , 使 j0 x j0 ,
由此及(12)证得结论.
12
推 论 4 设 素 数 p 2, p | a1 , p | a2 . 那 么 , ( i ) 若 a1 , a2均 为 模 p 的 平 方 剩 余 , 则 a1a2也 是 模 p的平方剩余; ( i i ) 若 a1 , a2均 为 模 p 的 平 方 非 剩 余 , 则 a1a2是 模 p的平方剩余; ( i i i ) 若 a1是 模 p 的 平 方 非 剩 余 , a2是 模 p 的 平 方 非 剩 余 , 则 a1a2是 模 p 的 平 方 非 剩 余 .
16
这样,确定a 是否是模p的二次剩余就变为去计算 a Legendre 符 号 ( )的 值 . 定 理 的 性 质 可 以 用 来 计 算 p a 1 2 ( ),并 由 算 数 基 本 定 理 知 , 只 要 能 计 算 出 ： ( ), ( ), p p p q a ( ),就 可 以 计 算 出 任 意 的( ). 这 里 q 2是 小 于 p 的 p p 素数.
17
2 ( p 2 1)/8 定 理 2 ( ) ( 1) （7 ） , 若( a, p) 1,2 | a, p 则 a ( )=(-1) k =1 p 推论
p1
[
ak ] p
p 1 （8), 其 中 p1 . 2
1, p 1(mod 8) 2 n ( )=(-1) p 1, p 3(mod 8)
( p 1)/2 ( p 1)
1 ( m o d p) , 因 而
1)(a 1, a
( p 1)/ 2
1) 0 ( m o d p )(11). 由 于 质 数 p 2
( p 1)/2
( p 1)/2
1) 2,所 以 推 出 结 论 .
必 要 性: 若 a 是 模 p 的 平 方 剩 余 ,则 必 有 x0使 得 的 充 要
6
定理 1 在模 p的一个简化剩余系中, 恰 有 ( p 1) / 2个 模 p 的 平 方 剩 余 ; ( p 1) / 2 个模 p的平方非剩余.此外,若a 是模 p的 平 方 剩 余 , 则 同 余 式 x 2 a (mod p)的 解 数 为 2.
7
p 1 p 1 证 只 要 取 模 p 的 绝 对 最 小 简 化 剩 余 系 ,+1, ,-1, 2 2 p 1 p 1 1, , -1, (6) 来 讨 论 . a 是 模 p 的 平 方 剩 余 当 且 仅 当 2 2 a ( p 1 2 p 1 ) ,( 1) 2 , 2 2 ,( 1) 2 ,12 , ,( p 1 p 1 2 1) 2或( ) (mod p) 2 2