第一講數(shù)論初步學(xué)習(xí)資料

第一講數(shù)論初步---喻鵬舉基本概念

數(shù)論是研究數(shù)的性質(zhì)的學(xué)科，數(shù)論基本上可分為初等數(shù)論、解析數(shù)論、代數(shù)數(shù)論等幾個(gè)較大的分支。整數(shù)的整除性

整除與約數(shù)、倍數(shù).注意負(fù)數(shù)a除以非0整數(shù)b商為整數(shù)，且余數(shù)為零。（我們就說a能被b整除或說b能整除a，記作b|a）可整除性的基本性質(zhì)若a|b,a|c,則a|(b+c)若a|b,那么對(duì)所有整數(shù)c,a|bc若a|b,b|c,則a|c整除關(guān)系具有傳遞性.素?cái)?shù)和合數(shù)如果大于1的正整數(shù)p僅有的正因子是1和p,稱p為素?cái)?shù)(prime)大于1又不是素?cái)?shù)的正整數(shù)稱為合數(shù)(compound)如果n是合數(shù),則n必有一個(gè)小于或等于n1/2的素因子除法和同余令a為整數(shù)，d為正整數(shù)，那么有惟一的整數(shù)q和r，其中0≤r<d，使得a=dq+r可以用這個(gè)定理來定義除法：d叫除數(shù)，a叫被除數(shù)，q叫商，r叫余數(shù)。如果兩個(gè)數(shù)a,b除以一個(gè)數(shù)c的余數(shù)相等，說a和b關(guān)于模c同余，記作a≡b(modc)最大公約數(shù)和最小公倍數(shù)令a和b是不全為0的兩個(gè)整數(shù)，能使d|a和d|b的最大整數(shù)稱為a和b的最大公約數(shù)，用gcd(a,b)表示，或者記為(a,b)。令a和b是不全為0的兩個(gè)整數(shù)，能使a|d和b|d的最小整數(shù)稱為a和b的最小公倍數(shù)，用lcm(a,b)表示，或者記為[a,b]定理:ab=gcd(a,b)*lcm(a,b)如果gcd（a,b）=1,a,b互質(zhì)定理的證明使用惟一分解定理.設(shè)則有:容易驗(yàn)證定理成立求出1—n的全部素?cái)?shù)；法一：Eratosthenes的篩子2是素?cái)?shù),刪除2*2,2*3,2*4,…,2*50第一個(gè)沒被刪除的是3,刪除3*3,3*4,3*5,…,3*33第一個(gè)沒被刪除的是5,刪除5*5,5*6,…5*20得到素?cái)?shù)p時(shí),需要?jiǎng)h除p*p,p*(p+1),…p*[n/p],運(yùn)算量為[n/p]-p,其中p不超過n1/2(想一想,為什么)近似公式(Legendre常數(shù)B=-1.08366)素?cái)?shù)判定枚舉法:O(n1/2),指數(shù)級(jí)別改進(jìn)的枚舉法:O(phi(n1/2))=O(n1/2/logn),仍然是指數(shù)級(jí)別概率算法:Miller-Rabin測(cè)試+Lucas-Lehmer測(cè)試對(duì)于奇數(shù)n,記n=2r*s+1,其中s為奇數(shù)隨機(jī)選a(1<=a<=n-1),n通過測(cè)試的條件是as≡1(modn),或者存在0<=j<=r-1使得a2^j*s≡-1(modn)素?cái)?shù)對(duì)于所有a通過測(cè)試,合數(shù)通過測(cè)試的概率不超過1/4只測(cè)試a=2,3,5,7,則2.5*1013以內(nèi)唯一一個(gè)可以通過所有測(cè)試的數(shù)為3215031751最大公約數(shù)方法一:使用惟一分解定理,先分解素因數(shù),然后求最大公約數(shù)方法二:(Euclid算法)利用公式gcd(a,b)=gcd(b,amodb),時(shí)間復(fù)雜度為O(logb)方法三:(二進(jìn)制算法)若a=b,gcd(a,b)=a,否則A和b均為偶數(shù),gcd(a,b)=2*gcd(a/2,b/2)A為偶數(shù),