數論及數論四大定理

本文是同門何健同學所做！請勿轉載

數論及數論四大定理hankin2015.github.io

數論 （數學分支）

數論是純粹數學的分支之一，主要研究整數的性質。整數可以是方程式的解（丟番圖方程）。有些解析函數（像黎曼ζ函數）中包括了一些整數、質數的性質，透過這些函數也可以了解一些數論的問題。透過數論也可以建立實數和有理數之間的關係，並且用有理數來逼近實數（丟番圖逼近）。

按研究方法來看，數論大致可分為初等數論和高等數論。初等數論是用初等方法研究的數論，它的研究方法本質上說，就是利用整數環的整除性質，主要包括整除理論、同餘理論、連分數理論。高等數論則包括了更為深刻的數學研究工具。它大致包括代數數論、解析數論、計算數論等等。

費馬大定理(費馬定理) （數學史上著名的定理）

費馬大定理，又被稱為「費馬最後的定理」，由17世紀法國數學家皮耶·德·費瑪提出。

它斷言當整數n >2時，關於x, y, z的方程 x^n + y^n = z^n 沒有正整數解。

德國佛爾夫斯克曾宣布以10萬馬克作為獎金獎給在他逝世後一百年內，第一個證明該定理的人，吸引了不少人嘗試並遞交他們的「證明」。

被提出後，經歷多人猜想辯證，歷經三百多年的歷史，最終在1995年被英國數學家安德魯·懷爾斯徹底證明。

同餘定理(同餘)

數論中的重要概念。給定一個正整數m，如果兩個整數a和b滿足a-b能夠被m整除，即(a-b)/m得到一個整數，那麼就稱整數a與b對模m同餘，記作a≡b(mod m)。對模m同餘是整數的一個等價關係。

偽素數

費馬小定理: 假如p是質數，若p不能整除a，則 a^(p-1) ≡1 (mod p)，若p能整除a，則a^(p-1) ≡0 (mod p)。

偽素數，又叫做偽質數：它滿足費馬小定理，但其本身卻不是素數。最小的偽素數是341。有人已經證明了偽素數的個數是無窮的。事實上，費馬小定理給出的是關於素數判定的必要非充分條件。若n能整除2^(n-1)-1，並n是非偶數的合數，那麼n就是偽素數。第一個偽素數341是薩魯斯（Sarrus)在1819年發現的。

費馬小定理也就是說如果一個數p滿足gcd(a, p) = 1 並且a^(p-1) ≡0 (mod p), 則p是質數。但存在其特例，也就是說費馬小定理有BUG，但也不能這麼說。費馬小定理只能正推，不能反推。所以說是p滿足費馬小定理，但p不是質數，而是另外一個稱呼偽素數(一定是奇數)。

註：gcd為最大公約數（greatest common divisor）

求偽素數

//求偽素數#include <iostream>#include <cmath>using namespace std;bool IsPrime(int n){ for(int i = 2; i <= sqrt(n); i++) { if(n % i == 0) return false; } return true;}int QuickPow(int a, int b, int mod){ int ret = 1; a = a % mod; while(b) { if(b & 1) ret =( ret * a )% mod; a =( a * a )% mod; b >>= 1; } return ret;}int main(){ for(int i = 2; i < 800000; i++) { if(QuickPow(2, i - 1, i) == 1) { if(!IsPrime(i)) { cout << i << endl; } } } return 0;}

指數循環節

其實就是歐拉定理的一種推廣。

（其中 為歐拉函數）

質數和素數

質數（prime number）又稱素數，有無限個。質數定義為在大於1的自然數中，除了1和它本身以外不再有其他因數。

數論四大定理

威爾遜定理、歐拉定理、孫子定理、費馬小定理並稱數論四大定理。

1、威爾遜定理

若p為質數，則p可整除(p-1)!+1。

如：7為質數，則7可整除(7 - 1)! + 1 = 721，即721 % 7 == 0。

2、歐拉定理

在數論中，歐拉定理（Euler Theorem，也稱費馬-歐拉定理或歐拉函數定理）是一個關於同餘的性質。歐拉定理得名於瑞士數學家萊昂哈德·歐拉，該定理被認為是數學世界中最美妙的定理之一。歐拉定理實際上是費馬小定理的推廣。此外還有平面幾何中的歐拉定理、多面體歐拉定理(在一凸多面體中，頂點數-棱邊數+面數=2)。西方經濟學中歐拉定理又稱為產量分配凈盡定理，指在完全競爭的條件下，假設長期中規模收益不變，則全部產品正好足夠分配給各個要素。另有歐拉公式。

歐拉定理，也稱費馬-歐拉定理或歐拉函數定理。歐拉定理實際上是費馬小定理的推廣。

若n,a為正整數，且n,a互素，即gcd(a,n) = 1，則a^φ(n) ≡ 1 (mod n), 其中φ(n)為歐拉函數。

如：n = 5, a = 7. 因為與5互質的有1、2、3、4，即φ(5) = 4，則(7 ^ 4) % 5 = 2401 % 5 = 1。

歐拉函數

在數論，對正整數n，歐拉函數是小於n的正整數中與n互質的數的數目（φ(1)=1）。此函數以其首名研究者歐拉命名(Euler』so

totient function)，它又稱為Euler』s totient function、φ函數、歐拉商數等。

例如φ(8)=4，因為1,3,5,7均和8互質。 從歐拉函數引伸出來在環論方面的事實和拉格朗日定理構成了歐拉定理的證明。

通式

φ(x) = x (1 - 1/p1) … * (1 - 1/pn)

其中p1, p2……pn為x的所有質因數，x是不為0的整數。

φ(1)=1（唯一和1互質的數(小於等於1)就是1本身）。

注意：每種質因數只一個。 比如12=223那麼φ（12）=12（1-1/2）(1-1/3)=4

特例

• 若n是質數p的k次冪，

，因為除了p的倍數外，其他數都跟n互質。

• 設n為正整數，以 φ(n)表示不超過n且與n互素的正整數的個數，稱為n的歐拉函數值
  φ：N→N，n→φ(n)稱為歐拉函數。
• 歐拉函數是積性函數——若m,n互質，

• 特殊性質：當n為奇數時，

, 證明與上述類似。

• 若n為質數，則 φ(n) = n - 1 ，如11，1、2、3、4、5、6、7、8、9、10都是與11互質的數。

//質數的快速求法[利用辛達拉姆篩進行素數判定]

利用辛達拉姆篩進行素數判定

因數數的快速求法

//因數數的快速求法，時間複雜度根號n。#include <iostream>#include <cmath>using namespace std;int main(){ int n; while(cin >> n) { int temp = sqrt(n); for(int i = 1; i < temp; i++) { if(n % i == 0) { cout << i << << n / i << ; } } if(temp * temp == n) cout << temp; cout << endl; } return 0;}

質因數的快速求法

//質因數的快速求法#include <iostream>#include <cmath>using namespace std;int main(){ int n; while(cin >> n) { //Pollard Rho因數分解，時間複雜度是n^0.25？不是n for(int i = 2; i <= n; i++) { if(n % i == 0) cout << i << ; while(n % i == 0) n /= i; } cout << endl; } return 0;}

歐拉函數

//歐拉函數#include <iostream>#include <cmath>using namespace std;int gcd(int a, int b){ return b ? gcd(b, a % b) : a;}int eular(int n){ int ret=1,i; for(i=2;i*i<=n;i++) { if(n%i==0) { n/=i,ret*=i-1; while(n%i==0) n/=i,ret*=i; } } if(n>1) ret*=n-1; return ret;}/*線性篩O(n)時間複雜度內篩出maxn內歐拉函數值*/int m[maxn],phi[maxn],p[maxn],pt;//m[i]是i的最小素因數，p是素數，pt是素數個數int make(){ phi[1]=1; int N=maxn; int k; for(int i=2;i<N;i++) { if(!m[i])//i是素數 p[pt++]=m[i]=i,phi[i]=i-1; for(int j=0;j<pt&&(k=p[j]*i)<N;j++) { m[k]=p[j]; if(m[i]==p[j])//為了保證以後的數不被再篩，要break { phi[k]=phi[i]*p[j];/*這裡的phi[k]與phi[i]後面的∏(p[i]-1)/p[i]都一樣（m[i]==p[j]）只差一個p[j]，就可以保證∏(p[i]-1)/p[i]前面也一樣了*/ break; } else phi[k]=phi[i]*(p[j]-1);//積性函數性質，f(i*k)=f(i)*f(k) } }}int main(){ int n; while(cin >> n) { //小於n的正整數中與n互質的數的數目 int cnt = 0; for(int i = 1; i < n; i++) { if(gcd(i, n) == 1) cnt++; } cout << cnt << endl; //根據通式計算 int ans = n; for(int i = 2; i <= n; i++) { if(n % i == 0) { ans = (ans / i) * (i - 1); } while(n % i == 0) n /= i; } cout << ans << endl; } return 0;}

3、孫子定理

孫子定理，又稱中國剩餘定理。孫子定理是中國古代求解一次同餘式組（見同餘）的方法。是數論中一個重要定理。又稱中國餘數定理。一元線性同餘方程組問題最早可見於中國南北朝時期（公元5世紀）的數學著作《孫子算經》卷下第二十六題，叫做「物不知數」問題，原文如下：

有物不知其數，三三數之剩二，五五數之剩三，七七數之剩二。問物幾何？即，一個整數除以三餘二，除以五餘三，除以七餘二，求這個整數。《孫子算經》中首次提到了同餘方程組問題，以及以上具體問題的解法，因此在中文數學文獻中也會將中國剩餘定理稱為孫子定理。

公元前後的《孫子算經》中有「物不知數」問題：「今有物不知其數，三三數之餘二 ，五五數之餘三 ，七七數之餘二，問物幾何？」答為「23」。

明朝程大位用歌謠給出了該題的解法：「三人同行七十稀，五樹梅花廿一枝，七子團圓月正半，除百零五便得知。」

以現代的說法，是找出三個關鍵數70，21，15。解法的意思就是用70乘3除所得的餘數，21乘5除所得的餘數，15乘7除所得的餘數，然後總加起來，除以105的餘數就是答案。

4、費馬小定理

假如p是質數，若p不能整除a，則 a^(p-1) ≡1（mod p），若p能整除a，則a^(p-1) ≡0（mod p）。

若p是質數，且a,p互質，那麼 a的(p-1)次方除以p的餘數恆等於1。

證明：

因為p是質數，且（a，p)=1，所以φ(p)=p-1。由歐拉定理可得a^(p-1) ≡1（mod p）。證畢。對於該式又有a^p ≡a（mod p），所以，費馬小定理的另一種表述為：假如p是質數，且gcd(a,p)=1，那麼a^p ≡a（mod p）。

歐拉定理，也稱費馬-歐拉定理或歐拉函數定理。歐拉定理實際上是費馬小定理的推廣。

推薦閱讀：