竞赛数论基础.ppt
《竞赛数论基础.ppt》由会员分享,可在线阅读,更多相关《竞赛数论基础.ppt(27页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、数论基础,A.1 素数与互素 A.2 同余与模运算 A.3 欧拉定理 A.4 几个有用的算法,授课内容,A.1 素数与互素,1 整除,定义1.1 设 a,b为整数,a0. 若有一整数q, 使得 b = aq, 则称 a是b的因数,b是a的倍数; 并称a整除b, 记为a|b, 可形式地表示为: a|b:=(q)(b=aq) 若a不能整除b,记为ab. 若b=aq,而a既非正负b又非正负1,则称a是b的真因数.,1 整除,关于整除,显然有下列定理: 定理1.1 对所有a, 1|a. 对所有a, a|0. 对所有 a, a|a. 若a|b且b|c, 则a|c. 若a|b, 则对任意的c0, 有ac|
2、bc. 若ac|bc且c0, 则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和它本身整除的整数, 称为素数; 否则, 称为合数. 由该定义可知,正整数集合可分三类: 素数、合数和1. 素数常用p或p1, p2,来表示.,2 素数和合数,定义2.2 若正整数a有一因数b,而b又是素数,则称b
3、为a的素因数 例:12=34, 其中3是12的素因数, 而4则不是. 素数有多少?公元前三世纪, 古希腊数学家欧几里德Euclid就证明了素数有无穷多个.,2 素数和合数,素数的一些基本结论: 素数有无穷多个 素数的整除性 素数定理 算术基本定理:有限分解和唯一分解,3 最大公因数和最小公倍数,定义3.1 设al,a2,an和d都是正整数, n2. 若d|ai, 1in, 则称d是al,a2,an.的公因数. 在公因数中最大的那一个数, 称为al,a2,an的最大公因数, 记为gcdal,a2,an. (greatest common divisor)或者(al,a2,an). 若gcd(al
4、,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的两个整数的最大公因子存在且唯一 设整数a与b不全为0,则存在整数x和y,使得ax+by=gcd(a,b)。特别地,如果a、b互素,则有ax+by=1 若gcd(a,b)=d, 则gcd (a|
5、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都是正整数, n2. 若ai|m, 1in, 则称m是a1,a2,an的公倍数. 在a1,a2,an所有公倍数中最小的那一个, 称为a1,a2,an的最小公倍数, 记为lcma1,a2,an(least common multipler)或者a1,a2,an.,A.2 同余与模运算,同余是数论中一个基本概念, 它的引人简化了数论中的许多问题 同余的很多性质和“等于”很类似,1 带余除法,若a,b是
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 竞赛 数论 基础
限制150内