本文關(guān)鍵詞：數(shù)論，由筆耕文化傳播整理發(fā)布。

斷斷續(xù)續(xù)的學(xué)習(xí)數(shù)論已經(jīng)有一段時(shí)間了，學(xué)得也很雜，現(xiàn)在進(jìn)行一些簡單的回顧和總結(jié)。

學(xué)過的東西不能忘啊。。。

1、本原勾股數(shù)：

概念：一個(gè)三元組(a,b,c)，其中a,b,c沒有公因數(shù)而且滿足：a^2+b^2=c^2

首先，這種本原勾股數(shù)的個(gè)數(shù)是無限的，而且構(gòu)造的條件滿足：

a=s*t,b=(s^2-t^2)/2,c=(s^2+t^2)/2

其中s>t>=1是任意沒有公因數(shù)的奇數(shù)！

由以上概念就可以導(dǎo)出任意一個(gè)本原勾股數(shù)組。

2、素?cái)?shù)計(jì)數(shù)（素?cái)?shù)定理）

令π(x)為1到x中素?cái)?shù)的個(gè)數(shù)

19世紀(jì)最高的數(shù)論成就就是以下這個(gè)玩意兒：

lim(x->∞){π(x)/(x/ln(x))}=1

數(shù)論最高成就，最高成就！�。∮心居校。�！

3、哥德巴赫猜想(1+1)

一個(gè)大偶數(shù)(>=4)必然可以拆分為兩個(gè)素?cái)?shù)的和，雖然目前還沒有人能夠從理論上進(jìn)行證明，不過我根據(jù)科學(xué)家們利用計(jì)算機(jī)運(yùn)算的結(jié)果，如果有一個(gè)偶數(shù)不能進(jìn)行拆分，那么這個(gè)偶數(shù)至少是一個(gè)上百位的數(shù)！！

所以在ACM的世界中（數(shù)據(jù)量往往只有2^63以下）哥德巴赫猜想是成立的！！所以拆分程序一定能夠?qū)崿F(xiàn)的

4、哥德巴赫猜想的推廣

任意一個(gè)>=8的整數(shù)一定能夠拆分為四個(gè)素?cái)?shù)的和

證明：

先來說8=2+2+2+2，（四個(gè)最小素?cái)?shù)的和）不能再找到比2小的素?cái)?shù)了，所以當(dāng)n小于8，就一定不可能拆分為四個(gè)素?cái)?shù)的和！

那么當(dāng)n大于等于8，可以分情況討論：

（1）n&1==0(n為偶數(shù))，那么n就一定可以拆分為兩個(gè)偶數(shù)的和

那么根據(jù)哥德巴赫猜想，偶數(shù)可以拆分為兩個(gè)素?cái)?shù)的和，于是，n一定可以拆分為四個(gè)素?cái)?shù)的和

（2）n&1==1(n為奇數(shù))，n一定可以拆分為兩個(gè)偶數(shù)+1

由于有一個(gè)素?cái)?shù)又是偶數(shù)，2，那么奇數(shù)一定有如下拆分：2+3+素?cái)?shù)+素?cái)?shù)

得證。

5、歐拉函數(shù)（歐拉公式）

歐拉函數(shù)ph(n)的意思是所有小于n且與n互質(zhì)的數(shù)的個(gè)數(shù)

比如說ph(12)=4,[1,5,7,11與12互質(zhì)]

歐拉公式

a^ph(m)=1(mod m)

6、費(fèi)馬小定理

費(fèi)馬小定理是歐拉公式的一種特殊情況

由于當(dāng)p為質(zhì)數(shù)的時(shí)候ph(p)=p-1這是顯然的

那么帶入歐拉公式就得到了費(fèi)馬小定理

a^(p-1)=1(mod p)

p為質(zhì)數(shù)(prime)

7、抽屜原理

抽屜原理其實(shí)是廢話，關(guān)鍵在于運(yùn)用

這句廢話是說，如果現(xiàn)在有3個(gè)蘋果，放進(jìn)2個(gè)抽屜，那么至少有一個(gè)抽屜里面會有兩個(gè)蘋果，這個(gè)很廢話。

8、抽屜原理的運(yùn)用

抽屜原理本身只是一句廢話，不過他的運(yùn)用卻非常強(qiáng)大

現(xiàn)在假設(shè)有一個(gè)正整數(shù)序列a1,a2,a3,a4.....an，試證明我們一定能夠找到一段連續(xù)的序列和，讓這個(gè)和是n的倍數(shù)，該命題的證明就用到了抽屜原理

我們可以先構(gòu)造一個(gè)序列si=a1+a2+...ai

然后分別對于si取模，如果其中有一個(gè)sk%n==0，那么a1+a2+...+ak就一定是n的倍數(shù)（該種情況得證）

下面是上一種情況的反面，即任何一個(gè)sk對于n的余數(shù)都不為0

對于這種情況，我們可以如下考慮，因?yàn)閟i%n!=0

那么si%n的范圍必然在1——（n-1），所以原序列si就產(chǎn)生了n個(gè)范圍在1——（n-1）的余數(shù)，于是抽屜原理就來了，n個(gè)數(shù)放進(jìn)n-1個(gè)盒子里面，必然至少有兩個(gè)余數(shù)會重復(fù)，那么這兩個(gè)sk1,sk2之差必然是n的倍數(shù)，

而sk1-sk2是一段連續(xù)的序列，那么原命題就得到了證明了

9、判斷n!是否能夠被m整除

計(jì)算方法是把m進(jìn)行質(zhì)因數(shù)分解，看下m的每一個(gè)質(zhì)因數(shù)是否能夠在n!中找到；

n!中間包含了多少個(gè)x(x是任意的一個(gè)數(shù)，不過一般情況下我們都只討論x為質(zhì)數(shù))，這種問題的答案是：
n/x+n/(x^2)+n/(x^3).....[一直加到x的乘方不超過n]，，這個(gè)定理的證明也非常的簡單，這里就不再贅述了

根據(jù)以上觀點(diǎn)，就可以分別計(jì)算m的每一個(gè)質(zhì)因數(shù)是否被完全包含，如果有一個(gè)沒有被包含，那么就不能被整除！

10、因子和的計(jì)算方法

神馬叫因子和：一個(gè)數(shù)的所以因子的和就叫因子和。。。

好吧，舉個(gè)例子：12的因子和為：1+2+3+4+6+12

計(jì)算方法是把12分解為質(zhì)因數(shù)的表達(dá)形式2^2*3

那么他的因子和就是：(1+2+2^2)*(1+3)

證明寫起來比較麻煩，大體上思路就是牛頓二項(xiàng)式。。。

11、判斷組合數(shù)C(n,m)的奇偶性

有一個(gè)我也不知道證明的方法

當(dāng)n&m==m為奇數(shù)，反之就是偶數(shù)

就總結(jié)到這兒了。

以前大一也總結(jié)過一片類似的，不過那時(shí)候之總結(jié)了一點(diǎn)關(guān)于歐幾里得算法之類的。

                                                                                                                                             ——bingshen

  本文關(guān)鍵詞：數(shù)論，由筆耕文化傳播整理發(fā)布。