竞赛数论基础

《竞赛数论基础》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

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

2、b,可形式地表示为:a

3、b:=(q)(b=aq)若a不能整除b，记为ałb.若b=aq,而a既非正负b又非正负1,则称a是b的真因数.1整除关于整除，显然有下列定理：定理1.1①对所有a,1

4、a.②对所有a,a

5、0.③对所有a,a

6、a.④若a

7、b且b

8、c,则a

9、c.⑤若a

10、b,则对任意的c≠0,有ac

11、bc.⑥若ac

12、bc且c≠0,则a

13、b.1整除⑦

14、若a

15、b且a

16、c,则对任意的m,n,有a

17、(bm+cn).⑧若a

18、b,则b=0或

19、a

20、≤

21、b

22、,其中

23、a

24、是a的绝对值.⑨若a

25、b,则(-a)

26、b,a

27、(-b),(-a)

28、(-b),

29、a

30、

31、

32、b

33、.2素数和合数在正整数中,1只能被它本身整除.任何大于1的整数都至少能被1和它本身整除．定义2.1一个大于1且只能被1和它本身整除的整数,称为素数;否则,称为合数.由该定义可知，正整数集合可分三类:素数、合数和1.素数常用p或p1,p2…,来表示.2素数和合数定义2.2若正整数a有一因数b,而b又是素数,则称b为a的素因数．例:12=3×4,其中3是12的素因数,而4则不是.素

34、数有多少？公元前三世纪,古希腊数学家欧几里德Euclid就证明了素数有无穷多个.2素数和合数素数的一些基本结论：素数有无穷多个素数的整除性素数定理算术基本定理：有限分解和唯一分解3最大公因数和最小公倍数定义3.1设al,a2,…,an和d都是正整数,n≥2.若d

35、ai,1≤i≤n,则称d是al,a2,…,an.的公因数.在公因数中最大的那一个数,称为al,a2,…,an的最大公因数,记为gcd{al,a2,…,an}.(greatestcommondivisor)或者(al,a2,…,an).若gcd(al,a2,…,an)=1,称al,a2,…,an是互素的.3最大公

36、因数和最小公倍数在互素的正整数中,不一定有素数.例如(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

37、d,b

38、d)=1若gcd(a,x)=gcd(b,x)=1,那么gcd(ab,x

39、)=1若c

40、(ab),gcd(b,c)=1,则c

41、a3最大公因数和最小公倍数定义3.2设a1,a2,…,an和m都是正整数,n≥2.若ai

42、m,1≤i≤n,则称m是a1,a2,…,an的公倍数.在a1,a2,…,an所有公倍数中最小的那一个,称为a1,a2,…,an的最小公倍数,记为lcm{a1,a2,…,an}(leastcommonmultipler)或者[a1,a2,…,an].A.2同余与模运算同余是数论中一个基本概念,它的引人简化了数论中的许多问题同余的很多性质和“等于”很类似1带余除法若a,b是二个正整数,b≠0,则唯一存在二个整数k和r,使得下式成立:a=

43、bk+r,0≤r

44、a.ab(modm)a=km+bm

45、a-b例A.2（参见教材p145）2整数同余与模运算模n同余类（剩余类）任何整数a除以正整数n的余数一定在集合{0，1，2，…，n-1}

46、中，所有整数根据模n同余关系可以分成n个集合，每一个集合中的整数模n同余，这样的集合称为模n同余类（剩余类）思考：从同余类的记法可以看出，它是否与代表元的选取有关？模n的完全剩余系从每一个模n同余类中取一个数为代表，形成一个集合，此集合称为模n的完全剩余系，记为ZnZn最简单表示就是集合{0，1，2，…,n-1},即Zn={0，1，2，…n-1}2整数同余与模运算模运算的性质：自反性:aa(modm).对称性:若ab(modm),则ba(modm).传递性:若ab(modm),bc(modm),则:ac(modm).可见,同余