數論的基本知識
本文將簡(jiǎn)單地介紹有關(guān)整數集合Z={…,-2,-1,0,1,2,…}和自然數集合N={0,1,2,…}的最基本的數論概念。
可除性與約數
一個(gè)整數能被另一個(gè)整數整除的概念是數論中的一個(gè)中心概念，記號d|a（讀作“d 除a”）意味著(zhù)對某個(gè)整數k，有 a = kd。0可被每個(gè)整數整除。如果a>0且d|a，則|d|≤|a|。如果d|a，則我們也可以說(shuō)a是d的倍數。如果a不能被d整除，則寫(xiě)作dFa。
如果d|a并且d≥0，則我們說(shuō)d是a的約數。注意，d|a當且僅當(-d)|a，因此定義約數為非負整數不會(huì )失去一般性，只要明白a的任何約數的相應負數同樣能整除a。一個(gè)整數a的約數最小為1，最大為|a|。例如，24的約數有1，2，3，4，6，8，12和24。
每個(gè)整數a都可以被其平凡約數1和a整除。a的非平凡約數也稱(chēng)為a的因子。例如， 20的因子有2，4，5和10。
素數與合數
對于某個(gè)整數a>1，如果它僅有平凡約數1和a，則我們稱(chēng)a為素數(或質(zhì)數)。素數具有許多特殊性質(zhì)，在數論中舉足輕重。按順序，下列為一個(gè)小素數序列:
2，3，5，6，11，13，17，19，23，29，31，37，41，43，47，53，59，…
不是素數的整數a>1稱(chēng)為合數。例如，因為有3|39，所以39是合數。整數1被稱(chēng)為基數，它既不是質(zhì)數也不是合數。類(lèi)似地，整數 0和所有負整數既不是素數也不是合數。
定理 1
素數有無(wú)窮個(gè)。
證明：
假設素數只有有限的n個(gè)，從小到大依次排列為p1,p2,...,pn，則 x = (p1·p2·...·pn)+1 顯然是不能被p1,p2,...,pn中的任何一個(gè)素數整除的，因此x也是一個(gè)素數，這和只有n個(gè)素數矛盾，所以素數是無(wú)限多的。
這個(gè)證明的最早來(lái)自亞里士多德，非常漂亮，是反證法的經(jīng)典應用，這個(gè)證明被歐拉稱(chēng)為“直接來(lái)自上帝的證明”，歷代的數學(xué)家也對其評價(jià)很高。
除法定理，余數和同模
已知一個(gè)整數n，所有整數都可以分劃為是n的倍數的整數與不是n的倍數的整數。對于不是n的倍數的那些整數，我們又可以根據它們除以n所得的余數來(lái)進(jìn)行分類(lèi)，數論的大部分理論都是基于上述分劃的。下列定理是進(jìn)行這種分劃的基礎。
定理2 (除法定理)
對任意整數a和任意正整數n，存在唯一的整數q和r，滿(mǎn)足0 < r ≤ n，并且a = qn + r 。
這個(gè)定理是整數的基本定理之一，這里就不給出具體證明了。
值q=ëa/nû 稱(chēng)為除法的商（ë xû 表示地板符號floor，即小于等于x的最大整數）。值 r = a mod n 稱(chēng)為除法的余數。我們有n|a 當且僅當 a mod n = O，并且有下式成立：
(1)
或
(2)
當我們定義了一個(gè)整數除以另一個(gè)整數的余數的概念后，就可以很方便地給出表示同余的特殊記法。如果 (a mod n)=(b mod n)，就寫(xiě)作 a ≡ b (mod n)，并說(shuō)a和b對模n是相等的。換句話(huà)說(shuō)，當a和b除以n有著(zhù)相同的余數時(shí)，有a ≡ b (mod n)。等價(jià)地有，a ≡ b (mod n)當且僅當n|(b - a)。如果a和b對模n不相等，則寫(xiě)作a T b (mod n)。例如， 61≡ 6 (mod 11)，同樣，-13≡ 22≡2 (mod 5)。
根據整數模n所得的余數可以把整數分成n個(gè)等價(jià)類(lèi)。模n 等價(jià)類(lèi)包含的整數a為：
例如，[3]7={…,-11,-4,3,10,17,…}，該集合還有其他記法[-4]7和[10]7。a ∈[b]n 。就等同于a ≡ b(mod n)。所有這樣的等價(jià)類(lèi)的集合為:
(3)
我們經(jīng)常見(jiàn)到定義
(4)
如果用0表示[0]n，用1表示[1]n。等等，每一類(lèi)均用其最小的非負元素來(lái)表示，則上述兩個(gè)定義(3)和(4)是等價(jià)的。但是，我們必須記住相應的等價(jià)類(lèi)。例如，提到Zn的元素-1就是指[n-1]n，因為-1 = n-1 (mod n)。
公約數與最大公約數
如果d是a的約數并且也是b的約數，則d是a與b的公約數。例如，24與30的公約數為1,2,3和6。注意，1是任意兩個(gè)整數的公約數。
公約數的一條重要性質(zhì)為:
(5)
更一般地，對任意整數x和y，我們有
(6)
同樣，如果a|b，則或者|a|≤|b|，或者b=O，這說(shuō)明：
(7)
兩個(gè)不同時(shí)為0的整數a與b的最大公約數表示成gcd(a,b)。例如，gcd(24,30)=6，gcd(5,7)=1，gcd(0,9)=9。如果a與b不同時(shí)為0，則 gcd(a,b)是一個(gè)在1與min(|a|,|b|)之間的整數。我們定義gcd(O,0)=0，這個(gè)定義對于使gcd函數的一般性質(zhì)(如下面的式 (11))普遍正確是必不可少的。
下列性質(zhì)就是gcd函數的基本性質(zhì)：
(8)
(9)
(10)
(11)
(12)
定理 3
如果a和b是不都為0的任意整數，則gcd(a,b)是a與b的線(xiàn)性組合集合{ ax + by : x,y ∈Z}中的最小正元素。
證明：
設s是a與b的線(xiàn)性組合集中的最小正元素，并且對某個(gè)x,y ∈Z，有s = ax + by，設q = ëa/sû ，則
式(2)說(shuō)明
因此，a mod s也是a與b的一種線(xiàn)性組合。但由于a mod s < s，所以我們有a mod s = O，因為s是滿(mǎn)足這樣的線(xiàn)性組合的最小正數。因此有s|a，并且類(lèi)似可推得s|b。因此，s是a與b的公約數，所以gcd(a，b)≥ s。因為gcd(a，b)能同時(shí)被a與b整除并且s是a與b的一個(gè)線(xiàn)性組合，所以由
式(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，如果d|a并且d|b，則d|gcd(a,b)。
證明：
根據
定理3，gcd(a，b)是a與b的一個(gè)線(xiàn)性組合，所以從
式(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。
證明：
（略）
互質(zhì)數
如果兩個(gè)整數a與b僅有公因數1，即如果gcd(a,b)=1，則a與b稱(chēng)為互質(zhì)數。例如，8和15是互質(zhì)數，因為8的約數為1，2，4，8，而15的約數為1，3，5，15。下列定理說(shuō)明如果兩個(gè)整數中每一個(gè)數都與一個(gè)整數p互為質(zhì)數，則它們的積與p與互為質(zhì)數。
定理 7
對任意整數 a，b和p，如果gcd(a,p)=1且gcd(b,p)=1，則gcd(ab,p)=1。
證明：
由
定理3可知，存在整數x，y，x‘，y‘ 滿(mǎn)足
ax+py=1
bx‘+py‘=1
把上面兩個(gè)等式兩邊相乘，我們有
ab(xx‘)+p(ybx‘+y‘a(chǎn)x+pyy‘) = 1
因為1是ab與p的一個(gè)正線(xiàn)性組合，所以運用
定理3就可以證明所需結論。
對于整數n1,n2,…,nk，如果對任何 i≠j 都有g(shù)cd(ni,nj)=1，則說(shuō)整數n1,n2,…,nk兩兩互質(zhì)。
唯一的因子分解
下列結論說(shuō)明了關(guān)于素數的可除性的一個(gè)基本但重要的事實(shí)。
定理 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，于是產(chǎn)生矛盾，叢而證明定理成立。
從定理8可推斷出，一個(gè)整數分解為素數的因子分解式是唯一的。
定理 9 (唯一質(zhì)因子分解)
任意的整數a能且僅能寫(xiě)成一種如下積的形式
其中pi為自然數中的第i個(gè)素數，p1<p2<…<pr，且ei為非負整數（注意ei可以為0）。
證明：
（略）
例如，數6000可唯一地分解為24·31·53。
這個(gè)定理非常重要，在計算理論中很多重要的定理都可以基于這個(gè)定理來(lái)證明，因為這個(gè)定理實(shí)際上給出了Z和Z*的一一對應關(guān)系，換句話(huà)說(shuō)，任何的整數a都可以用一組整數(e1,e2,…,er)來(lái)表示，，反之也成立，其中a和(e1,e2,…,er)滿(mǎn)足定理9的公式。比如6000可以用一組整數(4,1,3)表示，因為6000=24·31·53。從另一個(gè)角度看，這也提供了一種大整數的壓縮方法，可惜由于這種分解太費時(shí)間，所以此壓縮方法并不可行:-(。但是在很多定理的證明中（尤其是計算理論，形式語(yǔ)言和數理邏輯的定理中），用這種方法可以將一串的整數用唯一的一個(gè)整數來(lái)表示。比如在一臺圖靈機中，輸入是一串長(cháng)度不定的整數，經(jīng)過(guò)某種轉換，輸出另外一串長(cháng)度不定的整數，我們可以用定理9將輸入和輸出都用唯一的一個(gè)整數來(lái)表示，這樣轉換的過(guò)程就看作是一個(gè)簡(jiǎn)單的從整數集到整數集的函數，對我們從理論上研究這種轉換過(guò)程提供了方便。歌德?tīng)柌淮_定性原理的證明中就利用了這種技巧，所以這種編碼方式又稱(chēng)為哥德?tīng)柧幋a。再舉個(gè)簡(jiǎn)單的例子，如果我們將中文的每個(gè)漢字編碼，用一個(gè)整數表示一個(gè)漢字；將英文的26個(gè)字母編碼，用一個(gè)整數表示一個(gè)字母，現在我們要將一句輸入的中文翻譯成英文句子輸出，輸入和輸出都可以用一組整數表示，利用上面的哥德?tīng)柧幋a，可以將輸入和輸出用唯一的一個(gè)確定的整數表示，翻譯的過(guò)程就是做某種函數運算，該函數是Z→Z的簡(jiǎn)單整數函數，只要找到了這個(gè)函數，就作出了機器翻譯機來(lái)。事實(shí)上，世界上所有的能夠用算法處理的過(guò)程都可以利用哥德?tīng)柧幋a轉化成簡(jiǎn)單的整數函數來(lái)研究，這就是為什么計算理論中只研究簡(jiǎn)單的整數函數。
