1、精選優質文檔-傾情為你奉上數論基礎知識.txt丶喜歡的歌，靜靜的聽，喜歡的人，遠遠的看我笑了當初你不挺傲的嗎現在您這是又玩哪出呢？全文:數論的基本知識本文將簡單地介紹有關整數集合Z=,-2,-1,0,1,2,和自然數集合N=0,1,2,的最基本的數論概念。可除性與約數一個整數能被另一個整數整除的概念是數論中的一個中心概念，記號d|a（讀作“d 除a”）意味著對某個整數k，有 a = kd。0可被每個整數整除。如果a>0且d|a，則|d|a|。如果d|a，則我們也可以說a是d的倍數。如果a不能被d整除，則寫作dFa。如果d|a并且d0，則我們說d是a的約數。注意，d|a當且僅當(-d)|a

2、，因此定義約數為非負整數不會失去一般性，只要明白a的任何約數的相應負數同樣能整除a。一個整數a的約數最小為1，最大為|a|。例如，24的約數有1，2，3，4，6，8，12和24。每個整數a都可以被其平凡約數1和a整除。a的非平凡約數也稱為a的因子。例如， 20的因子有2，4，5和10。素數與合數對于某個整數a>1，如果它僅有平凡約數1和a，則我們稱a為素數(或質數)。素數具有許多特殊性質，在數論中舉足輕重。按順序，下列為一個小素數序列:2，3，5，6，11，13，17，19，23，29，31，37，41，43，47，53，59，不是素數的整數a>1稱為合數。例如，因為有3|39，所

3、以39是合數。整數1被稱為基數，它既不是質數也不是合數。類似地，整數 0和所有負整數既不是素數也不是合數。定理 1素數有無窮個。證明：假設素數只有有限的n個，從小到大依次排列為p1,p2,.,pn，則 x = (p1·p2·.·pn)+1 顯然是不能被p1,p2,.,pn中的任何一個素數整除的，因此x也是一個素數，這和只有n個素數矛盾，所以素數是無限多的。這個證明的最早來自亞里士多德，非常漂亮，是反證法的經典應用，這個證明被歐拉稱為“直接來自上帝的證明”，歷代的數學家也對其評價很高。除法定理，余數和同模已知一個整數n，所有整數都可以分劃為是n的倍數的整數與不是n的

4、倍數的整數。對于不是n的倍數的那些整數，我們又可以根據它們除以n所得的余數來進行分類，數論的大部分理論都是基于上述分劃的。下列定理是進行這種分劃的基礎。定理2 (除法定理)對任意整數a和任意正整數n，存在唯一的整數q和r，滿足0 < r n，并且a = qn + r 。這個定理是整數的基本定理之一，這里就不給出具體證明了。值q=?a/n? 稱為除法的商（? x? 表示地板符號floor，即小于等于x的最大整數）。值 r = a mod n 稱為除法的余數。我們有n|a 當且僅當 a mod n = O，并且有下式成立： (1)或 (2)當我們定義了一個整數除以另一個整數的余數的概念后，就

5、可以很方便地給出表示同余的特殊記法。如果 (a mod n)=(b mod n)，就寫作 a b (mod n)，并說a和b對模n是相等的。換句話說，當a和b除以n有著相同的余數時，有a b (mod n)。等價地有，a b (mod n)當且僅當n|(b - a)。如果a和b對模n不相等，則寫作a T b (mod n)。例如， 61 6 (mod 11)，同樣，-13 222 (mod 5)。根據整數模n所得的余數可以把整數分成n個等價類。模n 等價類包含的整數a為： 例如，37=,-11,-4,3,10,17,，該集合還有其他記法-47和107。a bn 。就等同于a b(mod n)。

6、所有這樣的等價類的集合為: (3)我們經常見到定義 (4)如果用0表示0n，用1表示1n。等等，每一類均用其最小的非負元素來表示，則上述兩個定義(3)和(4)是等價的。但是，我們必須記住相應的等價類。例如，提到Zn的元素-1就是指n-1n，因為-1 = n-1 (mod n)。公約數與最大公約數如果d是a的約數并且也是b的約數，則d是a與b的公約數。例如，24與30的公約數為1,2,3和6。注意，1是任意兩個整數的公約數。公約數的一條重要性質為: (5)更一般地，對任意整數x和y，我們有 (6)同樣，如果a|b，則或者|a|b|，或者b=O，這說明： (7)兩個不同時為0的整數a與b的最大公約

7、數表示成gcd(a,b)。例如，gcd(24,30)=6，gcd(5,7)=1，gcd(0,9)=9。如果a與b不同時為0，則 gcd(a,b)是一個在1與min(|a|,|b|)之間的整數。我們定義gcd(O,0)=0，這個定義對于使gcd函數的一般性質(如下面的式 (11)普遍正確是必不可少的。下列性質就是gcd函數的基本性質： (8) (9) (10) (11) (12) 定理 3如果a和b是不都為0的任意整數，則gcd(a,b)是a與b的線性組合集合 ax + by : x,y Z中的最小正元素。證明：設s是a與b的線性組合集中的最小正元素，并且對某個x,y Z，有s = ax + b

8、y，設q = ?a/s? ，則式(2)說明因此，a mod s也是a與b的一種線性組合。但由于a mod s < s，所以我們有a mod s = O，因為s是滿足這樣的線性組合的最小正數。因此有s|a，并且類似可推得s|b。因此，s是a與b的公約數，所以gcd(a，b) s。因為gcd(a，b)能同時被a與b整除并且s是a與b的一個線性組合，所以由式(6)可知gcd(a,b)| s 。但由gcd(a,b)|s 和s > O，可知 gcd(a,b)s。而上面已證明gcd(a,b)s，所以得到gcd(a,b) = s，我們因此可得到s是a與b的最大公約數。推論 4對任意整數a與b，如

9、果d|a并且d|b，則d|gcd(a,b)。證明：根據定理3，gcd(a，b)是a與b的一個線性組合，所以從式(6)可推得該推論成立。推論 5對所有整數a 和b以及任意非負整數n，gcd(an ,bn)=n gcd(a,b)。證明：如果n = 0，該推論顯然成立。如果n 0，則gcd(an,bn)是集合anx + bny中的最小正元素，即為集合ax + by中的最小正元素的n倍。推論 6對所有正整數n，a和b，如果n|ab并且gcd(a,n)=1，則n|b。證明：（略）互質數如果兩個整數a與b僅有公因數1，即如果gcd(a,b)=1，則a與b稱為互質數。例如，8和15是互質數，因為8的約數為1

10、，2，4，8，而15的約數為1，3，5，15。下列定理說明如果兩個整數中每一個數都與一個整數p互為質數，則它們的積與p與互為質數。定理 7對任意整數 a，b和p，如果gcd(a,p)=1且gcd(b,p)=1，則gcd(ab,p)=1。證明：由定理3可知，存在整數x，y，x'，y' 滿足ax+py=1bx'+py'=1把上面兩個等式兩邊相乘，我們有ab(xx')+p(ybx'+y'ax+pyy') = 1因為1是ab與p的一個正線性組合，所以運用定理3就可以證明所需結論。對于整數n1,n2,nk，如果對任何 ij 都有gcd(ni

11、,nj)=1，則說整數n1,n2,nk兩兩互質。唯一的因子分解下列結論說明了關于素數的可除性的一個基本但重要的事實。定理 8對所有素數p和所有整數a，b，如果p|ab，則pla或者p|b。證明：為了引入矛盾，我們假設p|ab，但pFa并且pFb。因此，gcd(a,p)=1 且gcd(b,p)=1，這是因為p的約數只有1和p。又因為假設了p既不能被a也不能被b整除。據定理7可知，gcd(ab,p)=1；又由假設p|ab可知gcd(p,ab)=p，于是產生矛盾，叢而證明定理成立。從定理8可推斷出，一個整數分解為素數的因子分解式是唯一的。定理 9 (唯一質因子分解)任意的整數a能且僅能寫成一種如下積

12、的形式其中pi為自然數中的第i個素數，p1<p2<<pr，且ei為非負整數（注意ei可以為0）。證明：（略）例如，數6000可唯一地分解為24·31·53。這個定理非常重要，在計算理論中很多重要的定理都可以基于這個定理來證明，因為這個定理實際上給出了Z和Z*的一一對應關系，換句話說，任何的整數a都可以用一組整數(e1,e2,er)來表示，反之也成立，其中a和(e1,e2,er)滿足定理9的公式。比如6000可以用一組整數(4,1,3)表示，因為6000=24·31·53。從另一個角度看，這也提供了一種大整數的壓縮方法，可惜由于這種分解太費時間，所以此壓縮方法并不可行:-(。但是在很多定理的證明中（尤其是計算理論，形式語言和數理邏輯的定理中），用這種方法可以將一串的整數用唯一的一個整數來表示。比如在一臺圖靈機中，輸入是一串長度不定的整數，經過某種轉換，輸出另外一串長度不定的整數，我們可以用定理9將輸入和輸出都用唯一的一個整數來表示，這樣轉換的過程就看作是一個簡單的從整數集到整數集的函數，對我們從理論上研究這種轉換過程提供了方便。歌德爾不確定性原理的證明中就利用了這種技巧，所以這種編碼方式又稱為哥德爾編碼。再舉個簡單的例子，如果我們將中文的每個漢字編碼，用一個整數表示一個漢字；將英文的26個字母編碼，用一個整