数论与有限域 第三章
更新时间:2023-06-11 23:38:01 阅读量: 实用文档 文档下载
- 数论与有限域董丽华答案推荐度:
- 相关推荐
数论与有限域
第三章 二次剩余
数论与有限域
第一节 二次剩余一、二次剩余的定义 二、二次剩余的性质
数论与有限域
一、二次剩余的定义定义3.1.1 设整数a与正整数m互素, 若同余式x2 a(modm)有解,则称a为模m的二次剩余; 若同余式x2 a(modm)无解,则称a为模m的非二次剩余。
例3.1.1 确定哪些整数是模10的二次剩余。 解:首先由于对任意的整数n,由带余数除法,存在唯一 的整数k与n1,使得 n=10k+n1,其中0≤n1<10,则 n2=100k2+20k·1+n12,于是 n n2≡n12(mod10),0≤n1<10, 因而为了确定哪些整数是模10的二次剩余,只需要关注整 数1,2,3,…,9的平方。
数论与有限域
一、二次剩余的定义例3.1.1 确定哪些整数是模10的二次剩余。 解:首先为了确定哪些整数是模10的二次剩余,只需要关 注整数1,2,3,…,9的平方。而 12≡92≡1 (mod 10), 22≡82≡4 (mod 10), 32≡72≡9 (mod 10), 42≡62≡6 (mod 10), 52≡5 (mod 10), 同时,由于在整数1,4,5,6,9中与10互素的整数只有1 和9,因而 只有1和9是模10的二次剩余, 而整数2,3,7,8中与10互素的整数只有3和7,因而 只有3和7是模10的二次非剩余。
数论与有限域
一、二次剩余的定义例3.1.2确定哪些整数是模11的二次剩余。 解:只需要关注整数1,2,3,…,10的平方。而 12≡102≡1 (mod 11), 22≡92≡4 (mod 11), 32≡82≡9 (mod 11), 42≡72≡5 (mod 11), 52≡62≡3 (mod 11), 同时由于整数1,2,3,…,10均与11互素,因而 整数1,3,4,5,9是模11的二次剩余, 而整数2,6,7,8,10是模11的二次非剩余。
数论与有限域
一、二次剩余的定义
例3.1.3确定哪些整数是模13的二次剩余。
解:类似于例3.1.1的讨论,这里我们只需要关注整数1,2, 3,…,12的平方。而 12≡122≡1 (mod 13), 22≡112≡4 (mod 13), 32≡102≡9 (mod 13), 42≡92≡3 (mod 13), 52≡82≡12 (mod 13), 62≡72≡10 (mod 13), 同时由于整数1,2,3,…,12均与13互素,因而 整数1,3,4,9,10,12是模13的二次剩余, 而整数2,5,6,7,8,11是模13的二次非剩余。
数论与有限域
二、二次剩余的性质引理3.1.1 设p是奇素数,a是整数,且p a,则同余式x2≡a (mod p)或者没有解或者恰有两个模p不同余的解。
证明:若同余式x2≡a(mod p)有一个解x=x0,则由于 (-x0)2=x02≡a(mod p), 因而可以同时找到同余式的另一个解 x=-x0。 用反证法来证明解x=-x0与x=x0不同余,假设 x0≡-x0 (mod p),即2x0≡0 (mod p)。 此时由x02≡a(modp),得到 p|(x02-a), 又p a,因而p x0;又p是奇数,进而 p 2x0,这与2x0≡0 (mod p)矛盾,
数论与有限域
二、二次剩余的性质引理3.1.1 设p是奇素数,a是整数,且p a,则同余式x2≡a (mod p) 或者没有解或者恰有两个模p不同余的解。 证明:接下来证明同余式x2≡a(mod p)的解不多于两个。假设 x=x0与x=x1都是同余式x2≡a (
mod p)的解,则 x02≡x12≡a (mod p),即 x02-x12=(x0+x1)(x0-x1)≡0 (mod p)。 因而 p|(x0+x1)或者p|(x0-x1),即 x0≡x1 (mod p)或x0≡-x1 (mod p)。 综上,若同余式x2≡a (mod p)有解,则恰有两个模p不同余的解。
数论与有限域
二、二次剩余的性质
定理3.1.1 若p是奇素数,则在整数1,2,…,p-1中恰有 (p-1)/2个模p的二次剩余,(p-1)/2个模p的二次非剩余。 证明:p-1个同余式 x2≡a (mod p),x=1, 2, …, p-1, 或者没有解 或者恰有两个模p不同余的解xi与p-xi,0≤xi≤p-1。 即1,2,…,p-1能且仅能为(p-1)/2个同余式提供解; 即1与p-1,2与p-2,3与p-3,…,(p-1)/2与(p+1)/2分别为 (p-1)/2个同余式的解, 因而整数1,2,…,p-1中恰有(p-1)/2个模p的二次剩 余,剩余的p-1-(p-1)/2=(p-1)/2个小于p-1的整数是模p 的二次非剩余。
数论与有限域
第二节 勒让德符号一、勒让德符号的定义
二、欧拉判别法三、高斯引理
数论与有限域
一、勒让德符号的定义定义3.2.1 设p是奇素数,a是整数,且p a,则 a 勒让德(Legendre)符号 定义为 p
若a是模p的二次剩余; a 1 p , 1 若a是模p的二次非剩余 . a 例3.2.1 由例3.1.3知道,勒让德符号 , a 1,2, ,12 13
的值如下 1 3 4 9 10 12 1 13 13 13 13 13 13
2 5 6 7 8 11 1 13 13 13 13 13 13
数论与有限域
二、欧拉判别法定理3.2.1(欧拉判别法)设p是奇素数,a是整数,且 a a ( p 1) / 2 (mod p ) p a,则 p a 证明:由于勒让德符号 的取值只有±1,因而 p
下面我们可以分两种情形来讨论. a 首先,若 =1,则a是模p的二次剩余,即 p
同余式x2≡a (mod p)有解,设其解为x=x0,即 x02≡a (mod p)。
数论与有限域
二、欧拉判别法证明: 由费马小定理,有 x02≡a (mod p)。
2 a ( p 1) / 2 ( x0 )( p 1) / 2 x0p 1 1(mod p).
a a 因而若 =1,则 a ( p 1) / 2 (mod p ) p p a 其次,若 =-1,则a是模p的二次非剩余,即 p 同余式x2≡a (mod p)无解。
数论与有限域
二、欧拉判别法又对每一个与p互素的整数i,线性同余式ix≡a (mod p) 都存在一个整数解j,即 ij≡a (mod p)。而 同余式x2≡a (mod p)无解,则 线性同余式ij≡a (mod p)中 i≠j,进而 可以将1,2,…,p-1中的整数划分成(p-1)/2对, 使得每对的乘积为a,将所有这些整数对乘在一起, 得到 (p-1)!≡a(p-1)/2(mod p)。 由Wil
son定理,有 -1≡a(p-1)/2(mod p)。
数论与有限域
二、欧拉判别法
例3.2.2 设p=13,a=132,由于 1326 (mod 13) ≡26 ≡-1 (mod 13), 132 由欧拉判别法有 13 =-1,因而132是模13的二次非剩余。
定理3.2.2 设p是奇素数,a,b是整数,p a且p b,则 (i) 若a≡b(mod p),则 a b ; p p a b ab (ii) ; p p p a2 (iii) =1。 p
数论与有限域
二、欧拉判别法 证明: 若a≡b(mod p),则同余式x2≡a (mod p)有解 同余式x2≡b
a b (mod p)有解,因而 。 p p b (p-1)/2 ≡b (mod p), p ab (mod p). p
(ii) 由欧拉判别法, a ≡a(p-1)/2(mod p), p
且
a b (p-1)/2 (p-1)/2 ≡a b =(ab) (p-1)/2≡ p p
ab p
≡(ab)(p-1)/2(mod p),因而
由于勒让德符号的值只有±1,因而结论成立。
数论与有限域
a (iii) 由于 =±1,由(ii)的结果得到 p
二、欧拉判别法 a 2 a a 1 p p p
由定理3.2.2的(ii)知: 一个素数的两个二次剩余或两个二次非剩余的乘 积是一个二次剩余,而一个素数的一个二次剩余 与一个二次非剩余的乘积是一个二次非剩余。 a a a n p1 1 p2 2 ps s 同时,任意给定正整数n的素分解式 由定理3.2.2可知要确定勒让德符号 n 的值, p
1 2 q 只需确定勒让德符号 , 以及 (其中q p p p 是一奇素数)的值。
数论与有限域
二、欧拉判别法若p 1(mod 4); 1 1 定理3.2.3 设p是奇素数,则 p 1 若p 1(mod 4). p 1 1 ( 1) 2 (mod p ) 证明:由欧拉判别法, p
由于p是奇素数,故p只能取 p=4k+1与p=4k+3,其中k为整数。 若p=4k+1,即p≡1(mod 4),则 1 (p-1)/2=(-1)2k=1,因而此时 p 1 (-1) 若p=4k+3,即p≡3(mod 4),则 1 (p-1)/2=(-1)2k+1=-1,因而此时 (-1) p 1
数论与有限域
三、高斯引理定理3.2.4(高斯引理)令奇素数p不整除整数n,同时设 在(p-1)/2个数n, 2n,…, (p-1)n/2对p取模得到的最小正 剩余中有m个大于p/2,则 n 1 m p
例3.2.3 p=13,n=63,则63,126,189,252,315,378 对13取模的最小剩余11,9,4,5,3,1中有两个大 63 于13/2,即m=2,进而由高斯引理有 1
13
例3.2.4 p=17,n=10,则10,20,30,40,50,60,70, 80对17取模的最小剩余10,3,13,6,16,9,2, 12中有5个大于17/2,即m=5,进而由高斯引理有 10 5 1 1 17
数论与有限域
三、高斯引理 2 ( p 2 1 ) / 8 定理3.2.5 若p是奇素数,则 1 p p 1(mod 8,则2为模p的二次剩余; ) 因而若 p 3(mod 8),则2为模p的二次非剩余。 若
证明:由于p是奇素数,可令 p=8a+r,r=1,3,5,7。 接下来计数(p-1)/2个整数2, 2×2,…, (p-1)×2/2对p取模 得到的最小正剩余中大于p/2的个数, 由于这(p-1)/2个整数已经在0和p之间,因而m的值是 满足不等式p/2<2k<p的k的个数,
数论与有限域
三、高斯引理 2 ( p 2 1 ) / 8 定理3.2.5 若p是奇素数,则 1 p
) 因而若 p 1(mod 8,则2为模p的二次剩余; 若 p 3(mod 8),则2为模p的二次非剩余。 证明:m的值是满足不等式p/2<2k<p的k的个数,即 m=[p/2]-[p/4]=[(8a+r)/2]-[(8a+r)]/4]=2a+[r/2]-[r/4] 当r分别取1,3,5,7时,m≡0, 1, 1, 0 (mod2)。 2 1 0 1 时, 故当p=8a+1或p=8a+7,即 p
2为模p的二次剩余; 2 1 1 1时, 而当p=8a+3或p=8a+5,即 p 2为模p的二次非剩余。
正在阅读:
数论与有限域 第三章06-11
电梯IC卡选层梯控说明05-16
项目水土保持合同201308-18
考点17 话题与交际-备战2022年浙江新高考一轮复习英语考点一遍过04-21
2012年电仪车电工班组培训计划 Microsoft Word 文档(2)10-01
成就型男形象必找对方法蓄须 docx06-02
15种法定公文写作格式和范文03-26
如何纠正驼背和盆骨前倾?04-26
丹东银通电力运检有限公司清算报告06-11
- 教学能力大赛决赛获奖-教学实施报告-(完整图文版)
- 互联网+数据中心行业分析报告
- 2017上海杨浦区高三一模数学试题及答案
- 招商部差旅接待管理制度(4-25)
- 学生游玩安全注意事项
- 学生信息管理系统(文档模板供参考)
- 叉车门架有限元分析及系统设计
- 2014帮助残疾人志愿者服务情况记录
- 叶绿体中色素的提取和分离实验
- 中国食物成分表2020年最新权威完整改进版
- 推动国土资源领域生态文明建设
- 给水管道冲洗和消毒记录
- 计算机软件专业自我评价
- 高中数学必修1-5知识点归纳
- 2018-2022年中国第五代移动通信技术(5G)产业深度分析及发展前景研究报告发展趋势(目录)
- 生产车间巡查制度
- 2018版中国光热发电行业深度研究报告目录
- (通用)2019年中考数学总复习 第一章 第四节 数的开方与二次根式课件
- 2017_2018学年高中语文第二单元第4课说数课件粤教版
- 上市新药Lumateperone(卢美哌隆)合成检索总结报告
- 数论
- 第三章
- 有限
- ABO血型鉴定和交叉配血实验
- 多年后的我60岁的那天早晨5点
- 《牛津小学英语》五年级下学期口语测试要求
- 《世界上最美丽的英文》
- 全镇2014年党建示范点简介精选
- 分析化学(第六版)课后习题参考解答 李发美
- 人教版下册第五章《相交线与平行线》同步单元解答典型习题
- 统计学2013年上半学年第一次作业1答案
- 营养与保健心得体会
- 浅谈八年制医学生的前列腺外科临床实习带教体会
- SQL之-建库、建表、建约束、关系SQL基本语句大全
- 设计院结构设计流程
- 陕甘边根据地创建与发展过程及其价值考证
- 2005年高考物理试卷分析
- 校团委学生会工作职能
- 山东省枣庄市峄城区吴林街道中学八年级体育第四周第11课时教案
- 制造烟火药安全管理条例详细版
- 数据中心机房空调机组设置与配置
- 江苏金飞达服装股份有限公司
- 如何设计全伺服卫生护垫项目可行性研究报告(技术工艺+设备选型+财务概算+厂区规划)投资方案