2020/6/13
数论
二 二次同余式的应用
例 5 求满足方程 E : y2 x3 x 2(mod 7)
的所有点. 解：对 x=0,1,2,3,4,5,6,分别求出 y. x=0, y2 =2 (mod 7), y= 3, 4(mod 7). x=1, y2 =4 (mod 7), y=2,5(mod 7)，
p 1
a 2 1(mod p); (2)
(ii) a 是模 p 的平方非剩余的充分 必要条件是
p 1
a 2 1(mod p); (3)
并且当 a 是模 p 的平方剩余时，同 余式(1)恰有二解.
2020/6/13
数论
三 模为奇素数的平方剩余
与平方非定理剩5 设余p是一个素数，n是一个正整
证 (i) 因为 p 是奇素数，数 f( 所x，)=n以x≤n p+有.…那+么表a1同x达余+a式式0 ≡0(mod p)有n个
2020/6/13
数论
二 二次同余式的应用
x=2, y2 =5 (mod 7), 无解， x=3, y2 =4 (mod 7), y=2,5(mod 7)， x=4, y2 =0 (mod 7), y=0(mod 7)， x=5, y2 =6 (mod 7), 无解， x=6, y2 =0 (mod 7), y=0(mod 7).
2020/6/13
数论
二 二次同余式的应用
x=2, y2 =6 (mod 7), 无解， x=3, y2 =6(mod 7), 无解， x=4, y2 =3 (mod 7), 无解， x=5, y2 =3 (mod 7), 无解， x=6, y2 =5 (mod 7), 无解，
2020/6/13
数论
二次同余式(1)等价于同余式组：
ax2 bx c 0
(mod
p )1 1
ax 2
bx c 0
(mod pk ) k
2020/6/13
数论
一 二次同余式的概念
我们只需讨论模为素数幂 pa 的同余式: ax2 bx c 0(mod p ), p a (2)
将同余式的两端同乘以 4a,我们得到 4a2x2 4abx 4ac 0(mod p ) 或 (2ax b)2 b2 4ac(mod p ) 令 y=2ax+b,我们有
2020/6/13
数论
二 二次同余式的应用
例 6 求满足方程
E : y2 x3 2x 1(mod 7) 的所有点. 解：对 x=0,1,2,3,4,5,6,分别求出 y. x=0, y2 =1 (mod 7), y= 1, 6(mod 7). x=1, y2 =4 (mod 7), y=2,5(mod 7)
a a bn4 130,b b 2 131(mod 227)
4
3
4
5
4
(6) n5 =1,计算
a a bn5 5, b6 b 2 136(mod 227)
5
4
5
5
5
(7) n6 =1,计算
a a bn6 226(mod 227)
6
5
6
2020/6/13
数论
因此，137 为模 227 平方非剩余.
2020/6/13
数论
2020/6/13
数论
二 二次同余式的应用
例 4 求满足方程 E : y2 x3 x 1(mod 7) 的所有点. 解：对 x=0,1,2,3,4,5,6,分别求出 y. x=0, y2 =1 (mod 7), y= 1, 6(mod 7). x=1, y2 =3 (mod 7)，无解，
y2 b2 4ac(mod p )，特别地，当 p 是奇素
数时，(p ,2a)=1,上述同余式等价于同余式 (2)
2020/6/13
数论
一 二次同余式的概念
定义 1 设 m 是正整数，若同余式 x2 a(mod m),(a, m) 1
有解，则 a 叫做模 m 的平方剩余(二次剩余)； 否则，a 叫做模 m 的平方非剩余(或二次非剩余). 例 1 1 是模 4 的平方剩余，-1 是模 4 的平方 非剩余. 例 2 1，2，4 是模 7 的平方剩余，-1 ，3，5 是模 7 的平方非剩余.
第四章 二次同余式与平方剩余
一 二次同余式的概念 二 二次同余式的应用 三 模为奇素数的平方剩余与平方
非剩余
2020/6/13
数论
一 二次同余式的概念
二次同余式的一般形式是ax2 bx c 0(mod m)(1)
其中 a 0(mod m).
因为正整数
m 有素因数分解式 m
p1 1
pk ，所以 k
0
1
(2) n1 =0,计算
a a 137,b b 2 190(mod 227)
1
0
2
1
(3) n2 =0,计算
a a 137,b b 2 7(mod 227)
2
1
3
2
2020/6/13
数论
(4) n3 =0,计算
a a 137,b b 2 49(mod 227)
3
2
4
3
(5) n4 =1,计算
(ii)因为 p 是奇素数，(a, p)=1,根据 2.4 定
理 1（欧拉定理），我们有表达式
p1
p1
(a 2 1)(a 2 1) a p1 1 0(mod p)
2020/6/13
数论
三 模为奇素数的平方剩余
与平方非剩余
定理2 若p是素
再根据 1.4 定理 2，我们有
数，如果p| ab, 则有p| a 或 p| b
由 3.4 定理 5，此同余式的解数是 p 1，故
2
平方剩余的个数是 p 1，而平方非剩余个数是
2
p- 1 - p 1 = p 1.
2
2
2020/6/13
数论
再证明定理的第二部分： 若(4)中有两个数模 p 同余，即存在
k 1
k (mod 2
p) 使得k2 1
k2 (mod 2
p)
则
(k k )(k k ) 0(mod p)
p 1
p解1 的充分必要p条1 件是xp –x被f( x)
x p x x((x2 ) 2 a 除2 所) 得余(式a的2所有系1数) x都是P的倍数
p 1
(x2 a)xq(x) (a 2 1)x
其中 q(x)是 x 的整系数多项式. 若 a 是模 p 的平方剩余，即 x2 ≡a (mod p)
个数同余.
2020/6/13
数论
证: 由定理 1，平方剩余的个数等于同余式
p1
定理5 设p是一个素数，n是一个正整
x 2 1(mod p) 的解数数，，但n≤ p.那么同余式
p1
x 2 1| x p1 1
f( x)=xn +…+a1 x +a0 ≡0(mod p)有n个 解的充分必要条件是xp –x被f( x) 除所得余式的所有系数都是P的倍数
2020/6/13
数论
三 模为奇素数的平方剩余 与平方非剩余
我们讨论模为素数 p 的二次同余式
x2 a(mod p), (a, p) 1
(1)
定理 1（欧拉判别条件）设 p 是奇素数， (a, p)=1, 则 ( i ) a 是模 p 的平方剩余的充分必要条件是
2020/6/13
数论
三 模为奇素数的平方剩余 与平方非剩余
推论 设 p 是奇素数，(a1 ,p) =1,(a2 ,p)=1,则 (i) 如果 a1 ,a2 都是模 p 的平方剩余，则 a1 a2 是模 p 的平方剩余. (ii) 如果 a1 ,a2 都是模 p 的平方非剩余，则 a1 a2 是模 p 的平方剩余. (iii) 如果 a1 是模 p 的平方剩余，a2 是模 p 的平 平方非剩余，则 a1 a2 是模 p 的平方非剩余
137 (2271)/2 137113 (mod 227)
运用模重复平方计算法，设 m=227,b=137, 令 a = 1,将 113 写成二进制，
2020/6/13
数论
113 1 24 25 26
我们依次计算如下：
(1) n0 =1,计算
a a bn0 137,b b2 155(mod 227)
p1
p1
p | a 2 1或 p | a 2 1
因此，结论(i)告诉我们： a 是模 p 的 平方非剩余的充分必要条件是
p1
a 2 1(mod p)
2020/6/13
数论
例1 利用定理判断
2020/6/13
数论
例 2 判断 137 是否为模 227 平方剩余. 解： 根据定理 1，我们要计算：
数论
二 二次同余式的应用
x=2, y2 =0 (mod 7), y= 0(mod 7)， x=3, y2 =4 (mod 7), y=2,5(mod 7)， x=4, y2 =5 (mod 7), 无解， x=5, y2 =2 (mod 7), y=3,4(mod 7)， x=6, y2 =1 (mod 7), y= 1, 6(mod 7).
二次同余式的概念， 二次同余式的运用， 欧拉判别条件
2020/6/13
数论
作业
习题4.9 1 ，4，6，8 补充一题：
2020/6/13
数论
有二个解 x，根据 3.4 定理 5，余式的系数被
p 1
P 整除，即 p | a 2 1，所以(2)式成立.
2020/6/13
数论
三 模为奇素数的平方剩余 与平方非剩余
反过来，若(2)成立，则同样根据 3.4 定 理 5，我们有同余式 x2 ≡a (mod p) 有解，