數(shù)論的基本知識(shí)

本文將簡(jiǎn)單地介紹有關(guān)整數(shù)集合Z={…,-2,-1,0,1,2,…}和自然數(shù)集合N={0,1,2,…}的最基本的數(shù)論概念。

可除性與約數(shù)

一個(gè)整數(shù)能被另一個(gè)整數(shù)整除的概念是數(shù)論中的一個(gè)中心概念，記號(hào)d|a（讀作“d 除a”）意味著對(duì)某個(gè)整數(shù)k，有 a = kd。0可被每個(gè)整數(shù)整除。如果a>0且d|a，則|d|≤|a|。如果d|a，則我們也可以說a是d的倍數(shù)。如果a不能被d整除，則寫作dFa。

如果d|a并且d≥0，則我們說d是a的約數(shù)。注意，d|a當(dāng)且僅當(dāng)(-d)|a，因此定義約數(shù)為非負(fù)整數(shù)不會(huì)失去一般性，只要明白a的任何約數(shù)的相應(yīng)負(fù)數(shù)同樣能整除a。一個(gè)整數(shù)a的約數(shù)最小為1，最大為|a|。例如，24的約數(shù)有1，2，3，4，6，8，12和24。

每個(gè)整數(shù)a都可以被其平凡約數(shù)1和a整除。a的非平凡約數(shù)也稱為a的因子。例如， 20的因子有2，4，5和10。

素?cái)?shù)與合數(shù)

對(duì)于某個(gè)整數(shù)a>1，如果它僅有平凡約數(shù)1和a，則我們稱a為素?cái)?shù)(或質(zhì)數(shù))。素?cái)?shù)具有許多特殊性質(zhì)，在數(shù)論中舉足輕重。按順序，下列為一個(gè)小素?cái)?shù)序列:

2，3，5，6，11，13，17，19，23，29，31，37，41，43，47，53，59，…

不是素?cái)?shù)的整數(shù)a>1稱為合數(shù)。例如，因?yàn)橛?|39，所以39是合數(shù)。整數(shù)1被稱為基數(shù)，它既不是質(zhì)數(shù)也不是合數(shù)。類似地，整數(shù) 0和所有負(fù)整數(shù)既不是素?cái)?shù)也不是合數(shù)。

定理 1

素?cái)?shù)有無窮個(gè)。

證明：

假設(shè)素?cái)?shù)只有有限的n個(gè)，從小到大依次排列為p₁,p₂,...,p_n，則 x = (p₁·p₂·...·p_n)+1 顯然是不能被p₁,p₂,...,p_n中的任何一個(gè)素?cái)?shù)整除的，因此x也是一個(gè)素?cái)?shù)，這和只有n個(gè)素?cái)?shù)矛盾，所以素?cái)?shù)是無限多的。

這個(gè)證明的最早來自亞里士多德，非常漂亮，是反證法的經(jīng)典應(yīng)用，這個(gè)證明被歐拉稱為“直接來自上帝的證明”，歷代的數(shù)學(xué)家也對(duì)其評(píng)價(jià)很高。

除法定理，余數(shù)和同模

已知一個(gè)整數(shù)n，所有整數(shù)都可以分劃為是n的倍數(shù)的整數(shù)與不是n的倍數(shù)的整數(shù)。對(duì)于不是n的倍數(shù)的那些整數(shù)，我們又可以根據(jù)它們除以n所得的余數(shù)來進(jìn)行分類，數(shù)論的大部分理論都是基于上述分劃的。下列定理是進(jìn)行這種分劃的基礎(chǔ)。

定理2 (除法定理)

對(duì)任意整數(shù)a和任意正整數(shù)n，存在唯一的整數(shù)q和r，滿足0 < r ≤ n，并且a = qn + r 。

這個(gè)定理是整數(shù)的基本定理之一，這里就不給出具體證明了。

值q=ëa/nû 稱為除法的商（ë xû 表示地板符號(hào)floor，即小于等于x的最大整數(shù)）。值 r = a mod n 稱為除法的余數(shù)。我們有n|a 當(dāng)且僅當(dāng) a mod n = O，并且有下式成立：

        (1)

或

        (2)

當(dāng)我們定義了一個(gè)整數(shù)除以另一個(gè)整數(shù)的余數(shù)的概念后，就可以很方便地給出表示同余的特殊記法。如果 (a mod n)=(b mod n)，就寫作 a ≡ b (mod n)，并說a和b對(duì)模n是相等的。換句話說，當(dāng)a和b除以n有著相同的余數(shù)時(shí)，有a ≡ b (mod n)。等價(jià)地有，a ≡ b (mod n)當(dāng)且僅當(dāng)n|(b - a)。如果a和b對(duì)模n不相等，則寫作a T b (mod n)。例如， 61≡ 6 (mod 11)，同樣，-13≡ 22≡2 (mod 5)。

根據(jù)整數(shù)模n所得的余數(shù)可以把整數(shù)分成n個(gè)等價(jià)類。模n 等價(jià)類包含的整數(shù)a為：

例如，[3]₇={…,-11,-4,3,10,17,…}，該集合還有其他記法[-4]₇和[10]₇。a ∈[b]_n 。就等同于a ≡ b(mod n)。所有這樣的等價(jià)類的集合為:

            (3)

我們經(jīng)常見到定義

            (4)

如果用0表示[0]_n，用1表示[1]_n。等等，每一類均用其最小的非負(fù)元素來表示，則上述兩個(gè)定義(3)和(4)是等價(jià)的。但是，我們必須記住相應(yīng)的等價(jià)類。例如，提到Z_n的元素-1就是指[n-1]_n，因?yàn)?1 = n-1 (mod n)。

公約數(shù)與最大公約數(shù)

如果d是a的約數(shù)并且也是b的約數(shù)，則d是a與b的公約數(shù)。例如，24與30的公約數(shù)為1,2,3和6。注意，1是任意兩個(gè)整數(shù)的公約數(shù)。

公約數(shù)的一條重要性質(zhì)為: 

        (5)

更一般地，對(duì)任意整數(shù)x和y，我們有

        (6)

同樣，如果a|b，則或者|a|≤|b|，或者b=O，這說明：

        (7)

兩個(gè)不同時(shí)為0的整數(shù)a與b的最大公約數(shù)表示成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|)之間的整數(shù)。我們定義gcd(O,0)=0，這個(gè)定義對(duì)于使gcd函數(shù)的一般性質(zhì)(如下面的式 (11))普遍正確是必不可少的。

下列性質(zhì)就是gcd函數(shù)的基本性質(zhì)：

	(8)
	(9)
	(10)
	(11)
	(12)

定理 3

如果a和b是不都為0的任意整數(shù)，則gcd(a,b)是a與b的線性組合集合{ ax + by : x,y ∈Z}中的最小正元素。

證明：

設(shè)s是a與b的線性組合集中的最小正元素，并且對(duì)某個(gè)x,y ∈Z，有s = ax + by，設(shè)q = ëa/sû ，則式(2)說明

因此，a mod s也是a與b的一種線性組合。但由于a mod s < s，所以我們有a mod s = O，因?yàn)閟是滿足這樣的線性組合的最小正數(shù)。因此有s|a，并且類似可推得s|b。因此，s是a與b的公約數(shù)，所以gcd(a，b)≥ s。因?yàn)間cd(a，b)能同時(shí)被a與b整除并且s是a與b的一個(gè)線性組合，所以由式(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的最大公約數(shù)。

推論 4

對(duì)任意整數(shù)a與b，如果d|a并且d|b，則d|gcd(a,b)。

證明：

根據(jù)定理3，gcd(a，b)是a與b的一個(gè)線性組合，所以從式(6)可推得該推論成立。

推論 5

對(duì)所有整數(shù)a 和b以及任意非負(fù)整數(shù)n，gcd(an ,bn)=n gcd(a,b)。

證明：

如果n = 0，該推論顯然成立。如果n ≠ 0，則gcd(an,bn)是集合{anx + bny}中的最小正元素，即為集合{ax + by}中的最小正元素的n倍。

推論 6

對(duì)所有正整數(shù)n，a和b，如果n|ab并且gcd(a,n)=1，則n|b。

證明：

（略）

互質(zhì)數(shù)

如果兩個(gè)整數(shù)a與b僅有公因數(shù)1，即如果gcd(a,b)=1，則a與b稱為互質(zhì)數(shù)。例如，8和15是互質(zhì)數(shù)，因?yàn)?的約數(shù)為1，2，4，8，而15的約數(shù)為1，3，5，15。下列定理說明如果兩個(gè)整數(shù)中每一個(gè)數(shù)都與一個(gè)整數(shù)p互為質(zhì)數(shù)，則它們的積與p與互為質(zhì)數(shù)。

定理 7

對(duì)任意整數(shù) a，b和p，如果gcd(a,p)=1且gcd(b,p)=1，則gcd(ab,p)=1。

證明：

由定理3可知，存在整數(shù)x，y，x‘，y‘ 滿足

ax+py=1

bx‘+py‘=1

把上面兩個(gè)等式兩邊相乘，我們有

ab(xx‘)+p(ybx‘+y‘a(chǎn)x+pyy‘) = 1

因?yàn)?是ab與p的一個(gè)正線性組合，所以運(yùn)用定理3就可以證明所需結(jié)論。

對(duì)于整數(shù)n₁,n₂,…,n_k，如果對(duì)任何 i≠j 都有g(shù)cd(n_i,n_j)=1，則說整數(shù)n₁,n₂,…,n_k兩兩互質(zhì)。

唯一的因子分解

下列結(jié)論說明了關(guān)于素?cái)?shù)的可除性的一個(gè)基本但重要的事實(shí)。

定理 8

對(duì)所有素?cái)?shù)p和所有整數(shù)a，b，如果p|ab，則pla或者p|b。

證明：

為了引入矛盾，我們假設(shè)p|ab，但pFa并且pFb。因此，gcd(a,p)=1 且gcd(b,p)=1，這是因?yàn)閜的約數(shù)只有1和p。又因?yàn)榧僭O(shè)了p既不能被a也不能被b整除。據(jù)定理7可知，gcd(ab,p)=1；又由假設(shè)p|ab可知gcd(p,ab)=p，于是產(chǎn)生矛盾，叢而證明定理成立。

從定理8可推斷出，一個(gè)整數(shù)分解為素?cái)?shù)的因子分解式是唯一的。

定理 9 (唯一質(zhì)因子分解)

任意的整數(shù)a能且僅能寫成一種如下積的形式

其中p_i為自然數(shù)中的第i個(gè)素?cái)?shù)，p₁<p₂<…<p_r，且e_i為非負(fù)整數(shù)（注意e_i可以為0）。

證明：

（略）

例如，數(shù)6000可唯一地分解為2^4·3^1·5³。

這個(gè)定理非常重要，在計(jì)算理論中很多重要的定理都可以基于這個(gè)定理來證明，因?yàn)檫@個(gè)定理實(shí)際上給出了Z和Z*的一一對(duì)應(yīng)關(guān)系，換句話說，任何的整數(shù)a都可以用一組整數(shù)(e₁,e₂,…,e_r)來表示，，反之也成立，其中a和(e₁,e₂,…,e_r)滿足定理9的公式。比如6000可以用一組整數(shù)(4,1,3)表示，因?yàn)?000=2^4·3^1·5³。從另一個(gè)角度看，這也提供了一種大整數(shù)的壓縮方法，可惜由于這種分解太費(fèi)時(shí)間，所以此壓縮方法并不可行:-(。但是在很多定理的證明中（尤其是計(jì)算理論，形式語言和數(shù)理邏輯的定理中），用這種方法可以將一串的整數(shù)用唯一的一個(gè)整數(shù)來表示。比如在一臺(tái)圖靈機(jī)中，輸入是一串長(zhǎng)度不定的整數(shù)，經(jīng)過某種轉(zhuǎn)換，輸出另外一串長(zhǎng)度不定的整數(shù)，我們可以用定理9將輸入和輸出都用唯一的一個(gè)整數(shù)來表示，這樣轉(zhuǎn)換的過程就看作是一個(gè)簡(jiǎn)單的從整數(shù)集到整數(shù)集的函數(shù)，對(duì)我們從理論上研究這種轉(zhuǎn)換過程提供了方便。歌德爾不確定性原理的證明中就利用了這種技巧，所以這種編碼方式又稱為哥德爾編碼。再舉個(gè)簡(jiǎn)單的例子，如果我們將中文的每個(gè)漢字編碼，用一個(gè)整數(shù)表示一個(gè)漢字；將英文的26個(gè)字母編碼，用一個(gè)整數(shù)表示一個(gè)字母，現(xiàn)在我們要將一句輸入的中文翻譯成英文句子輸出，輸入和輸出都可以用一組整數(shù)表示，利用上面的哥德爾編碼，可以將輸入和輸出用唯一的一個(gè)確定的整數(shù)表示，翻譯的過程就是做某種函數(shù)運(yùn)算，該函數(shù)是Z→Z的簡(jiǎn)單整數(shù)函數(shù)，只要找到了這個(gè)函數(shù)，就作出了機(jī)器翻譯機(jī)來。事實(shí)上，世界上所有的能夠用算法處理的過程都可以利用哥德爾編碼轉(zhuǎn)化成簡(jiǎn)單的整數(shù)函數(shù)來研究，這就是為什么計(jì)算理論中只研究簡(jiǎn)單的整數(shù)函數(shù)。