競(jìng)賽數(shù)論基礎(chǔ)

《競(jìng)賽數(shù)論基礎(chǔ)》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫(kù)。

1、數(shù)論基礎(chǔ)A.1素?cái)?shù)與互素A.2同余與模運(yùn)算A.3歐拉定理A.4幾個(gè)有用的算法授課內(nèi)容A.1素?cái)?shù)與互素1整除定義1.1設(shè)a,b為整數(shù)，a≠0.若有一整數(shù)q,使得b=aq,則稱a是b的因數(shù),b是a的倍數(shù);并稱a整除b,記為a

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

3、b:=(?q)(b=aq)若a不能整除b，記為a?b.若b=aq,而a既非正負(fù)b又非正負(fù)1,則稱a是b的真因數(shù).1整除關(guān)于整除，顯然有下列定理：定理1.1①對(duì)所有a,1

4、a.②對(duì)所有a,a

5、0.③對(duì)所有a,a

6、a.④若a

7、b且b

8、c,則a

9、c.⑤若a

10、b,則對(duì)任意的c≠0,有ac

11、bc.⑥若ac

12、bc且c≠0,則a

13、b.1整除⑦

14、若a

15、b且a

16、c,則對(duì)任意的m,n,有a

17、(bm+cn).⑧若a

18、b,則b=0或

19、a

20、≤

21、b

22、,其中

23、a

24、是a的絕對(duì)值.⑨若a

25、b,則(-a)

26、b,a

27、(-b),(-a)

28、(-b),

29、a

30、

31、

32、b

33、.2素?cái)?shù)和合數(shù)在正整數(shù)中,1只能被它本身整除.任何大于1的整數(shù)都至少能被1和它本身整除．定義2.1一個(gè)大于1且只能被1和它本身整除的整數(shù),稱為素?cái)?shù);否則,稱為合數(shù).由該定義可知，正整數(shù)集合可分三類(lèi):素?cái)?shù)、合數(shù)和1.素?cái)?shù)常用p或p1,p2…,來(lái)表示.2素?cái)?shù)和合數(shù)定義2.2若正整數(shù)a有一因數(shù)b,而b又是素?cái)?shù),則稱b為a的素因數(shù)．例:12=3×4,其中3是12的素因數(shù),而4則不是.素

34、數(shù)有多少？公元前三世紀(jì),古希臘數(shù)學(xué)家歐幾里德Euclid就證明了素?cái)?shù)有無(wú)窮多個(gè).2素?cái)?shù)和合數(shù)素?cái)?shù)的一些基本結(jié)論：素?cái)?shù)有無(wú)窮多個(gè)素?cái)?shù)的整除性素?cái)?shù)定理算術(shù)基本定理：有限分解和唯一分解3最大公因數(shù)和最小公倍數(shù)定義3.1設(shè)al,a2,…,an和d都是正整數(shù),n≥2.若d

35、ai,1≤i≤n,則稱d是al,a2,…,an.的公因數(shù).在公因數(shù)中最大的那一個(gè)數(shù),稱為al,a2,…,an的最大公因數(shù),記為gcd{al,a2,…,an}.(greatestcommondivisor)或者(al,a2,…,an).若gcd(al,a2,…,an)=1,稱al,a2,…,an是互素的.3最大公

36、因數(shù)和最小公倍數(shù)在互素的正整數(shù)中,不一定有素?cái)?shù).例如(25,36)=1,但25和36都不是素?cái)?shù)而是合數(shù).在個(gè)數(shù)不少于3個(gè)的互素正整數(shù)中,不一定是每二個(gè)正整數(shù)都是互素的.例:(6,10,15)=1,但(6,10)=2,(6,15)=3,(10,15)=5.3最大公因數(shù)和最小公倍數(shù)最大公因子有下列性質(zhì)：任何不全為0的兩個(gè)整數(shù)的最大公因子存在且唯一設(shè)整數(shù)a與b不全為0，則存在整數(shù)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最大公因數(shù)和最小公倍數(shù)定義3.2設(shè)a1,a2,…,an和m都是正整數(shù),n≥2.若ai

42、m,1≤i≤n,則稱m是a1,a2,…,an的公倍數(shù).在a1,a2,…,an所有公倍數(shù)中最小的那一個(gè),稱為a1,a2,…,an的最小公倍數(shù),記為lcm{a1,a2,…,an}(leastcommonmultipler)或者[a1,a2,…,an].A.2同余與模運(yùn)算同余是數(shù)論中一個(gè)基本概念,它的引人簡(jiǎn)化了數(shù)論中的許多問(wèn)題同余的很多性質(zhì)和“等于”很類(lèi)似1帶余除法若a,b是二個(gè)正整數(shù),b≠0,則唯一存在二個(gè)整數(shù)k和r,使得下式成立:a=

43、bk+r,0≤r

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

45、a-b例A.2（參見(jiàn)教材p145）2整數(shù)同余與模運(yùn)算模n同余類(lèi)（剩余類(lèi)）任何整數(shù)a除以正整數(shù)n的余數(shù)一定在集合{0，1，2，…，n-1}

46、中，所有整數(shù)根據(jù)模n同余關(guān)系可以分成n個(gè)集合，每一個(gè)集合中的整數(shù)模n同余，這樣的集合稱為模n同余類(lèi)（剩余類(lèi)）思考：從同余類(lèi)的記法可以看出，它是否與代表元的選取有關(guān)？模n的完全剩余系從每一個(gè)模n同余類(lèi)中取一個(gè)數(shù)為代表，形成一個(gè)集合，此集合稱為模n的完全剩余系，記為ZnZn最簡(jiǎn)單表示就是集合{0，1，2，…,n-1},即Zn={0，1，2，…n-1}2整數(shù)同余與模運(yùn)算模運(yùn)算的性質(zhì)：自反性:a?a(modm).對(duì)稱性:若a?b(modm),則b?a(modm).傳遞性:若a?b(modm),b?c(modm),則:a?c(modm).可見(jiàn),同余