数论与有限域-第三章.ppt

上传人:99****p 文档编号:1518333 上传时间:2019-03-04 格式:PPT 页数:67 大小:1.47MB
下载 相关 举报
数论与有限域-第三章.ppt_第1页
第1页 / 共67页
数论与有限域-第三章.ppt_第2页
第2页 / 共67页
数论与有限域-第三章.ppt_第3页
第3页 / 共67页
数论与有限域-第三章.ppt_第4页
第4页 / 共67页
数论与有限域-第三章.ppt_第5页
第5页 / 共67页
点击查看更多>>
资源描述

1、第三章 二次剩余第一节 二次剩余一、二次剩余的定义二、二次剩余的性质定义 3.1.1 设整数 a与正整数 m互素,若同余式 x2a(modm)有解,则称 a为 模 m的二次剩余;若同余式 x2a(modm)无解,则称 a为模 m的非二次剩余。例 3.1.1 确定哪些整数是模 10的二次剩余。解 : 首先 由于对任意的整数 n,由带余数除法,存在唯一的整数 k与 n1,使得n=10k+n1,其中 0n110,则n2=100k2+20kn1+n12,于是n2n12(mod10), 0n110,因而为了确定哪些整数是模 10的二次剩余,只需要关注整数 1, 2, 3, , 9的平方。 一、二次剩余的

2、定义例 3.1.1 确定哪些整数是模 10的二次剩余。解 : 首先 为了确定哪些整数是模 10的二次剩余,只需要关注整数 1, 2, 3, , 9的平方。而12921 (mod 10),22824 (mod 10),32729 (mod 10),42626 (mod 10),525 (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的二次剩余。解 :

3、只需要关注整数 1, 2, 3, , 10的平方。而121021 (mod 11),22924 (mod 11),32829 (mod 11),42725 (mod 11),52623 (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的平方。而121221 (mod 13),221124 (mod 13

4、),321029 (mod 13),42923 (mod 13),528212 (mod 13),627210 (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是整数,且 pa,则同余式x2a (mod p)或者没有解或者恰有两个模 p不同余的解。证明 :若同余式 x2a(mod p)有一个解 x=x0,则由于(-x0)2=x02a(mod p),因而可以同时找到同余式的另一个解x

5、=-x0。用反证法来证明解 x=-x0与 x=x0不同余 ,假设x0-x0 (mod p),即 2x00 (mod p)。此时由 x02a(modp),得到p|(x02-a),又 pa,因而 px0;又 p是奇数,进而p2x0,这与 2x00 (mod p)矛盾,二、二次剩余的性质引理 3.1.1 设 p是奇素数, a是整数,且 pa,则同余式 x2a (mod p)或者没有解或者恰有两个模 p不同余的解。证明 : 接下来证明同余式 x2a(mod p)的解不多于两个。 假设x=x0与 x=x1都是同余式 x2a (mod p)的解,则x02x12a (mod p),即x02-x12=(x0+

6、x1)(x0-x1)0 (mod p)。因而p|(x0+x1)或者 p|(x0-x1),即x0x1 (mod p)或 x0-x1 (mod p)。综上,若同余式 x2a (mod p)有解,则恰有两个模 p不同余的解。 二、二次剩余的性质定理 3.1.1 若 p是奇素数,则在整数 1, 2, , p-1中恰有 (p-1)/2个模 p的二次剩余, (p-1)/2个模 p的二次非剩余。证明 : p-1个同余式x2a (mod p), x=1, 2, , p-1,或者没有解或者恰有两个模 p不同余的解 xi与 p-xi, 0xip-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的二次非剩余。二、二次剩余的性质第二节 勒让德符号一、勒让德符号的定义二、 欧拉判别法三、高斯引理

展开阅读全文
相关资源
相关搜索

当前位置:首页 > 教育教学资料库 > 课件讲义

Copyright © 2018-2021 Wenke99.com All rights reserved

工信部备案号浙ICP备20026746号-2  

公安局备案号:浙公网安备33038302330469号

本站为C2C交文档易平台,即用户上传的文档直接卖给下载用户,本站只是网络服务中间平台,所有原创文档下载所得归上传人所有,若您发现上传作品侵犯了您的权利,请立刻联系网站客服并提供证据,平台将在3个工作日内予以改正。