費馬小定理 - MBA智库百科

費馬小定律(Fermat's Little Theorem)費馬小定理是數論中的一個定理。

其內容為假如a是一個整數，p是一個質數的話，那麼:a^p = a \pmod{p}假如a不是p的倍數的話， ... 費馬小定理 用手机看条目 扫一扫，手机看条目 出自MBA智库百科(https://wiki.mbalib.com/) 費馬小定律(Fermat'sLittleTheorem) 目錄 1什麼是費馬小定律 2費馬小定律的廣義 3費馬小定律的歷史 4費馬小定律的證明 5費馬小定律的的實際應用 6相關條目 [編輯]什麼是費馬小定律 　　費馬小定理是數論中的一個定理。

其內容為假如a是一個整數，p是一個質數的話，那麼: 　　ap=a(modp) 　　假如a不是p的倍數的話，那麼這個定理也可以寫成: 　　ap−1=1(modp) 　　這個書寫方式更加常用些。

[編輯]費馬小定律的廣義 　　費馬小定理是歐拉定理(數論)的一個特殊情況：假如n和a的最大公約數是1的話，那麼: 　　 　　在這裡φ(n)是歐拉商數。

歐拉商數的值是所有小於n的自然數中與n沒有公約數的數的量。

假如n是一個質數，則φ(n)=n-1，即費馬小定理。

　　在費馬小定理的基礎上費馬提出了一種測試質數的演算法。

[編輯]費馬小定律的歷史 　　皮埃爾·德·費馬於1636年發現了這個定理，在一封1640年10月18日的信中他第一次使用了上面的書寫方式。

在他的信中費馬還提出a是一個質數的要求。

這個要求實際上不存在。

　　與費馬無關的有一個中國猜想。

這個猜想是中國數學家提出來的。

其內容為如果，而且只有當2p=2(modp)成立時p才是一個質數。

　　假如p是一個質數的話，則2p=2(modp)成立（這是費馬小定理的一個特殊情況）是對的。

但反過來，假如2p=2(modp)成立那麼p是一個質數是不成立的（比如341符合上述條件但不是一個質數）。

因此整個來說這個猜想是錯誤的。

　　一般認為中國數學家在費馬前2000年的時候就已經認識中國猜測了。

但也有人認為實際上中國猜測是1872年提出的，認為它早就為人所知是出於一個誤解。

[編輯]費馬小定律的證明 　　若n不整除a-b，x>0，(x,n)=1，則n也不整除x(a-b)。

取整數A為所有小於p的集（p不整除A），B為A中所有元素乘以a的集合。

因任何兩個A中的元素差都不能被p整除，所以任何兩個B中的元素差也無法被p整除。

因此: 　　 　　即: 　　 　　在這裡W=1·2·3·...·(p-1)。

將整個公式除以W即得到: 　　ap−1=1(modp) [編輯]費馬小定律的的實際應用 　　如上所述，中國猜測只有一半是正確的，符合中國猜測但不是質數的數被稱為偽質數。

　　假如所有符合1帮助与反馈>我的反馈） 知道了