• / 27

竞赛数论基础.ppt

配套讲稿:

如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。

特殊限制:

部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。

关 键  词:
竞赛数论基础.ppt
资源描述:

《竞赛数论基础.ppt》由会员分享,可在线阅读,更多相关《竞赛数论基础.ppt(27页珍藏版)》请在微传网上搜索。

1、数论基础,A.1 素数与互素A.2 同余与模运算A.3 欧拉定理A.4 几个有用的算法,授课内容,A.1 素数与互素,,1 整除,定义1.1 设 a,b为整数,a≠0. 若有一整数q, 使得 b = aq, 则称 a是b的因数,b是a的倍数; 并称a整除b, 记为a|b, 可形式地表示为: a|b:=(q)(b=aq)若a不能整除b,记为ałb.若b=aq,而a既非正负b又非正负1,则称a是b的真因数.,1 整除,关于整除,显然有下列定理:定理1.1 ①对所有a, 1|a. ②对所有a, a|0. ③对所有 a, a|a. ④若a。

2、|b且b|c, 则a|c. ⑤若a|b, 则对任意的c≠0, 有ac|bc. ⑥若ac|bc且c≠0, 则a|b.,1 整除,⑦若 a | b且a|c,则对任意的 m,n,有 a|(bm+cn).⑧若a|b, 则b=0或|a|≤|b|,其中|a|是a的绝对值.⑨若a|b, 则(-a)|b, a|(-b),(-a)|(-b), |a|||b|.,2素数和合数,在正整数中, 1只能被它本身整除. 任何大于1的整数都至少能被1和它本身整除.定义2.1 一个大于1且只能被1和它本身整除的整数, 称为素数; 否则, 称为合数.由该定义可知,正整数集合可分三类: 素数、合数。

3、和1.素数常用p或p1, p2…,来表示.,2 素数和合数,定义2.2 若正整数a有一因数b,而b又是素数,则称b为a的素因数.例:12=3×4, 其中3是12的素因数, 而4则不是.素数有多少?公元前三世纪, 古希腊数学家欧几里德Euclid就证明了素数有无穷多个.,2 素数和合数,素数的一些基本结论:素数有无穷多个素数的整除性素数定理算术基本定理:有限分解和唯一分解,3 最大公因数和最小公倍数,定义3.1 设al,a2,…,an和d都是正整数, n≥2. 若d|ai, 1≤i≤n, 则称d是al,a2,…,an.的公因数.在公因数中最大的那一个数, 称为al,a2,…,an。

4、的最大公因数, 记为gcd{al,a2,…,an}. (greatest common divisor)或者(al,a2,…,an).若gcd(al,a2,…,an)=1, 称al,a2,…,an是互素的.,3 最大公因数和最小公倍数,在互素的正整数中, 不一定有素数. 例如(25,36)=1, 但25和36都不是素数而是合数.在个数不少于3个的互素正整数中, 不一定是每二个正整数都是互素的.例: (6,10,15)= 1, 但(6,10)=2, (6,15)=3, (10,15)=5.,3 最大公因数和最小公倍数,最大公因子有下列性质:任何不全为0的两个整数的最大公因子存在且唯一设。

5、整数a与b不全为0,则存在整数x和y,使得ax+by=gcd(a,b)。特别地,如果a、b互素,则有ax+by=1若gcd(a,b)=d, 则gcd (a|d, b|d)=1若gcd(a,x)=gcd(b,x)=1,那么gcd(ab,x)=1若c|(ab),gcd(b,c)=1,则c|a,3 最大公因数和最小公倍数,定义3.2 设a1,a2,…,an和m都是正整数, n≥2. 若ai|m, 1≤i≤n, 则称m是a1,a2,…,an的公倍数.在a1,a2,…,an所有公倍数中最小的那一个, 称为a1,a2,…,an的最小公倍数, 记为lcm{a1,a2,…,an}(least comm。

6、on multipler)或者[a1,a2,…,an].,A.2 同余与模运算,同余是数论中一个基本概念, 它的引人简化了数论中的许多问题同余的很多性质和“等于”很类似,1 带余除法,若a,b是二个正整数,b≠0, 则唯一存在二个整数k和r, 使得下式成立: a=bk+r, 0≤r

7、称 a与b模m不同余, 记作ab(mod m).m称为模数,a(modm)称为a模m的余数。显然,a0(mod m) iff m| a.ab(mod m) a=km+b m|a-b例A.2(参见教材p145),,,2 整数同余与模运算,模n同余类(剩余类)任何整数a除以正整数n的余数一定在集合{0,1,2,…,n-1}中,所有整数根据模n同余关系可以分成n个集合,每一个集合中的整数模n同余,这样的集合称为模n同余类(剩余类)思考:从同余类的记法可以看出,它是否与代表元的选取有关?模n的完全剩余系从每一个模n同余类中取一个数为代表,形成一个集合,此集合称。

8、为模n的完全剩余系,记为ZnZn最简单表示就是集合{0,1,2,…,n-1},即Zn={0,1,2,…n-1},2 整数同余与模运算,模运算的性质: 自反性: aa (mod m). 对称性: 若ab(mod m), 则 ba(mod m). 传递性: 若ab(mod m), bc(mod m), 则: ac(mod m). 可见, 同余关系是等价关系.若ab(mod m), cd(mod m), 则: a±c  b±d(mod m) ac  bd(mod m).,,模运算具有普通运算的代数性质,可交换、可结合、可分配[(a mod n) + 。

9、(b mod n)] mod n=(a +b) mod n[(a mod n) - (b mod n)] mod n=(a - b) mod n[(a mod n) X (b mod n)] mod n=(a x b) mod n[(aXb) mod n) ± (aXc mod n)] mod n=(a x (b±c) mod n,,加法消去律: 如果a+b  a+c(mod n),则 b  c(mod n)乘法消去律:如果ab  ac(mod n)且gcd(a,n)=1,则 b  c(mod n)如果ab  dc(mod n)且 a  d(mod n)以及 gcd(。

10、a,n)=1,则 b  c(mod n)例A.3 参见教材P145。,,指数模运算可以变成模指数运算,从而使运算得以简化,例如887 mod 187=[(884 mod 187) x (882 mod 187) x (88 mod 187)] mod 187882 mod 187=7744 mod 187 =77884 mod 187=[(882 mod 187) x (882 mod 187)] mod 187 =(77 x 77) mod 187=132887 mod 187=(132 X 77 X88) mod 187=11例A.4 参见教材P146。,,消去律的条件逆元。

11、的概念加法逆元:设a,n∈Z且n>1,如果存在b∈Z使得a+b≡0(modn),则称a、b为互为模n的加法逆元,也称负元,记为b≡-a(modn)乘法逆元:设a,n∈Z且n>1,如果存在b∈Z使得ab≡1(modn),则称a、b为互为模n的乘法逆元,记为b≡a-1(modn)逆元的存在性加法逆元总存在,例如n-a乘法逆元存在的充要条件是a与n互素时,A.3 欧拉定理,,1 欧拉函数,对于正整数n,(n)定义为小于n且与n互质的正整数的个数。例如(6) = 2,这是因为小于6且与6互质的数有1和5共两个数再如(7) = 6,这是因为互质数有1,2,3,4,5,6共6个。如果n为素数,则(n)=n-1如果gcd(m,n)=1,则(mn)= (m)(n),2 欧拉定理,费尔马定理(欧拉定理实际上是费尔马定理的推广) 如果p是素数,则对任意的a,有,2 欧拉定理,如果p不是素数,则对任意的a,有,p1,p2,…,pk是p的所有素数因子,,例如,5(6) mod 6 = 52 mod 6= 25 mod 6 =1, 3(7) mod 7 = 36 mod 7= 729 mod 7 =1,也就是说,在对n求余的运算下, (n)指数具有周期性。,。

展开阅读全文
  微传网所有资源均是用户自行上传分享,仅供网友学习交流,未经上传用户书面授权,请勿作他用。
0条评论

还可以输入200字符

暂无评论,赶快抢占沙发吧。

关于本文
本文标题:竞赛数论基础.ppt
链接地址:https://www.weizhuannet.com/p-1155191.html
微传网是一个办公文档、学习资料下载的在线文档分享平台!

网站资源均来自网络,如有侵权,请联系客服删除!

 网站客服QQ:80879498  会员QQ群:727456886

copyright@ 2018-2028 微传网版权所有

     经营许可证编号:冀ICP备18006529号 公安局备案号:13028102000127

收起
展开