費馬小定理- 維基百科，自由的百科全書

費馬小定理（英語：Fermat's little theorem）是數論中的一個定理。

假如 a {\displaystyle a} a ... 不是質數。

滿足費馬小定理的合數被稱為費馬偽質數。

費馬小定理 維基百科，自由的百科全書 跳至導覽 跳至搜尋 費馬小定理（英語：Fermat'slittletheorem）是數論中的一個定理。

假如 a {\displaystylea} 是一個整數， p {\displaystylep} 是一個質數，那麼 a p − a {\displaystylea^{p}-a} 是 p {\displaystylep} 的倍數，可以表示為 a p ≡ a ( mod p ) {\displaystylea^{p}\equiva{\pmod{p}}} 如果 a {\displaystylea} 不是 p {\displaystylep} 的倍數，這個定理也可以寫成更加常用的一種形式 a p − 1 ≡ 1 ( mod p ) {\displaystylea^{p-1}\equiv1{\pmod{p}}} [1][註1] 費馬小定理的逆敘述不成立，即假如 a p − a {\displaystylea^{p}-a} 是 p {\displaystylep} 的倍數， p {\displaystylep} 不一定是一個質數。

例如 2 341 − 2 {\displaystyle2^{341}-2} 是 341 {\displaystyle341} 的倍數，但 341 = 11 × 31 {\displaystyle341=11\times31} ，不是質數。

滿足費馬小定理的合數被稱為費馬偽質數。

目次 1歷史 1.1卡邁克爾數 2證明 2.1方法一 2.2方法二 2.3方法三 3應用 4推廣 4.1歐拉定理 4.2卡邁克爾函數 4.3多項式除法 5注釋 6參見 7參考 歷史[編輯] 皮埃爾·德·費馬 皮埃爾·德·費馬於1636年發現了這個定理。

在一封1640年10月18日的信中他第一次使用了上面的書寫方式。

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

1736年，歐拉出版了一本名為「一些與質數有關的定理的證明」（拉丁文：TheorematumQuorundamadNumerosPRIMOSSpectantiumDemonstratio）」[2]的論文集，其中第一次給出了證明。

但從萊布尼茨未發表的手稿中發現他在1683年以前已經得到幾乎是相同的證明。

有些數學家獨立提出相關的假說（有時也被錯誤地稱為中國猜想），當 2 p ≡ 2 ( mod p ) {\displaystyle2^{p}\equiv2{\pmod{p}}} 成立時，p是質數。

這是費馬小定理的一個特殊情況。

然而，這一假說的前設是錯的：例如， 2 341 ≡ 2 ( mod 341 ) {\displaystyle2^{341}\equiv2{\pmod{341}}} ，而341=11×31是一個偽質數。

所有的偽質數都是此假說的反例。

卡邁克爾數[編輯] 主條目：卡邁克爾數 如上所述，中國猜想僅有一半是正確的。

符合中國猜想但不是質數的數被稱為偽質數。

更極端的反例是卡麥可數： 假設 a {\displaystylea} 與561互質，則 a 560 {\displaystylea^{560}} 被561除都餘1。

這樣的數被稱為卡邁克爾數，561是最小的卡邁克爾數。

Korselt在1899年就給出了卡邁克爾數的等價定義，但直到1910年才由卡邁克爾（RobertDanielCarmichael）發現第一個卡邁克爾數：561。

1994年WilliamAlford、AndrewGranville及CarlPomerance證明了卡邁克爾數有無窮多個。

證明[編輯] 方法一[編輯] 若n不能整除 a − b {\displaystylea-b} ， x > 0 {\displaystylex>0} ， ( x , n ) = 1 {\displaystyle(x,n)=1} ，則n也不能整除 x ( a − b ) {\displaystylex(a-b)} 。

取整數集 A {\displaystyleA} 為所有小於 p {\displaystylep} 的集合（ A {\displaystyleA} 構成 p {\displaystylep} 的完全剩餘系，即 A {\displaystyleA} 中不存在兩個數同餘 p {\displaystylep} ）， B {\displaystyleB} 是 A {\displaystyleA} 中所有的元素乘以a組成的集合。

因為 A {\displaystyleA} 中的任何兩個元素之差都不能被p整除，所以B中的任何兩個元素之差也不能被p整除。

換句話說， gcd ( a , p ) = 1 {\displaystyle\gcd(a,p)=1} ，考慮 1 × a , 2 × a , 3 × a , . . . . ( p − 1 ) × a {\displaystyle1\timesa,2\timesa,3\timesa,....(p-1)\timesa} 共 ( p − 1 ) {\displaystyle(p-1)} 個數，將它們分別除以p，餘數分別為 r 1 , r 2 , r 3 , . . . . , r p − 1 {\displaystyler_{1},r_{2},r_{3},....,r_{p-1}} ，則集合{r1,r2,r3,...,rp-1}為集合{1,2,3,...,(p-1)}的重新置換，即1,2,3,....,(p-1)在餘數中恰好各出現一次；這是因為對於任兩個相異k*a而言（k=1,2,3....(p-1)），其差不是p的倍數（所以不會有相同餘數），且任一個k*a亦不為p的倍數（所以餘數不為0）。

因此 1 ⋅ 2 ⋅ 3 ⋅ ⋯ ⋅ ( p − 1 ) ≡ ( 1 ⋅ a ) ⋅ ( 2 ⋅ a ) ⋅ ⋯ ⋅ ( ( p − 1 ) ⋅ a ) ( mod p ) , {\displaystyle1\cdot2\cdot3\cdot\dots\cdot(p-1)\equiv(1\cdota)\cdot(2\cdota)\cdot\dots\cdot((p-1)\cdota){\pmod{p}},} 即 W ≡ W ⋅ a p − 1 ( mod p ) , {\displaystyleW\equivW\cdota^{p-1}{\pmod{p}},} 在這裡W=1·2·3·...·(p-1)，且(W,p)=1，因此將整個公式除以W即得到： a p − 1 ≡ 1 ( mod p ) {\displaystylea^{p-1}\equiv1{\pmod{p}}} [3] 方法二[編輯] 參見：中一新生之夢 考慮二項式係數 ( p n ) = p ! n ! ( p − n ) ! {\displaystyle{\tbinom{p}{n}}={\tfrac{p!}{n!(p-n)!}}} ，並限定n不為p或0，則由於分子有質數p，但分母不含p，故分子的p能保留，不被約分而除去，即 ( p n ) {\displaystyle{\tbinom{p}{n}}} 恆為p的倍數[4]。

再考慮(b+1)p的二項式展開，模p，則 ( b + 1 ) p ≡ ( p p ) b p + ( p p − 1 ) b p − 1 + ( p p − 2 ) b p − 2 + ⋯ + ( p 2 ) b 2 + ( p 1 ) b 1 + ( p 0 ) b 0 ( mod p ) {\displaystyle(b+1)^{p}\equiv{\dbinom{p}{p}}b^{p}+{\dbinom{p}{p-1}}b^{p-1}+{\dbinom{p}{p-2}}b^{p-2}+\dots+{\dbinom{p}{2}}b^{2}+{\dbinom{p}{1}}b^{1}+{\dbinom{p}{0}}b^{0}{\pmod{p}}} ≡ ( p p ) b p + ( p 0 ) b 0 ( mod p ) {\displaystyle\equiv{\dbinom{p}{p}}b^{p}+{\dbinom{p}{0}}b^{0}{\pmod{p}}} ≡ b p + 1 ( mod p ) {\displaystyle\equivb^{p}+1{\pmod{p}}} 因此 ( b + 1 ) p ≡ b p + 1 ( mod p ) {\displaystyle(b+1)^{p}\equivb^{p}+1{\pmod{p}}} ≡ ( b − 1 ) p + 1 + 1 ( mod p ) {\displaystyle\equiv(b-1)^{p}+1+1{\pmod{p}}} ≡ ( b − 2 ) p + 1 + 1 + 1 ( mod p ) {\displaystyle\equiv(b-2)^{p}+1+1+1{\pmod{p}}} ≡ ( b − 3 ) p + 1 + 1 + 1 + 1 ( mod p ) {\displaystyle\equiv(b-3)^{p}+1+1+1+1{\pmod{p}}} … {\displaystyle\dots} ≡ 1 + 1 + ⋯ + 1 + 1 ⏟ b + 1 ( mod p ) {\displaystyle\equiv{\begin{matrix}\underbrace{1+1+\dots+1+1}\\b+1\end{matrix}}{\pmod{p}}} ≡ b + 1 ( mod p ) {\displaystyle\equivb+1{\pmod{p}}} 令b=a-1，即得 a p ≡ a ( mod p ) {\displaystylea^{p}\equiva{\pmod{p}}} 。

[3] 方法三[編輯] 在抽象代數教科書中，費馬小定理常作為教授拉格朗日定理時的一個簡單例子[5]。

顯然只需考慮 ( a , p ) = 1 {\displaystyle(a,p)=1} 情形。

此時模 p {\displaystylep} 所有非零的餘數，在同餘意義下對乘法構成一個群，這個群的階是 p − 1 {\displaystylep-1} 。

考慮群中的任何一個元素 b {\displaystyleb} ，根據拉格朗日定理， b {\displaystyleb} 的階必整除群的階。

證畢。

應用[編輯] 計算 2 100 {\displaystyle2^{100}} 除以13的餘數 2 100 ≡ 2 12 × 8 + 4 ( mod 13 ) {\displaystyle2^{100}\equiv2^{12\times8+4}{\pmod{13}}} ≡ ( 2 12 ) 8 ⋅ 2 4 ( mod 13 ) {\displaystyle\equiv(2^{12})^{8}\cdot2^{4}{\pmod{13}}} ≡ 1 8 ⋅ 16 ( mod 13 ) {\displaystyle\equiv1^{8}\cdot16{\pmod{13}}} ≡ 16 ( mod 13 ) {\displaystyle\equiv16{\pmod{13}}} ≡ 3 ( mod 13 ) {\displaystyle\equiv3{\pmod{13}}} 故餘數為3。

證明對於任意整數a而言， a 13 − a {\displaystylea^{13}-a} 恆為2730的倍數。

易由 a p − 1 ≡ 1 ( mod p ) {\displaystylea^{p-1}\equiv1{\pmod{p}}} 推得 a n ( p − 1 ) + 1 ≡ 1 n ⋅ a ≡ a ( mod p ) {\displaystylea^{n(p-1)+1}\equiv1^{n}\cdota\equiva{\pmod{p}}} ，其中 n {\displaystylen} 為正整數。

故對指數13操作如下：13減1為12，12的正因數有1,2,3,4,6,12，分別加1，為2,3,4,5,7,13，其中2,3,5,7,13為質數，根據定理的延伸表達式， a 13 − a {\displaystylea^{13}-a} 為2的倍數、為3的倍數、為5的倍數、為7的倍數、為13的倍數，即2*3*5*7*13=2730的倍數。

推廣[編輯] 歐拉定理[編輯] 費馬小定理是歐拉定理的一個特殊情況：如果 ( a , n ) = 1 {\displaystyle(a,n)=1} ，那麼 a φ ( n ) ≡ 1 ( mod n ) {\displaystylea^{\varphi(n)}\equiv1{\pmod{n}}} 這裡 φ ( n ) {\displaystyle\varphi(n)} 是歐拉函數。

歐拉函數的值是所有小於或等於 n {\displaystylen} 的正整數中與 n {\displaystylen} 互質的數的個數。

假如 n {\displaystylen} 是一個質數，則 φ ( n ) = n − 1 {\displaystyle\varphi(n)=n-1} ，即費馬小定理。

證明 上面證明費馬小定理的群論方法，可以同理地證明歐拉定理。

考慮所有與 n {\displaystylen} 互質的數，這些數模 n {\displaystylen} 的餘數所構成的集合，記為 S {\displaystyle{\cal{S}}} ，並將群乘法定義為相乘後模 n {\displaystylen} 的同餘。

顯然 S {\displaystyle{\cal{S}}} 是一個群，因為它對群乘法封閉（若 ( a , n ) = 1 {\displaystyle(a,n)=1} 和 ( b , n ) = 1 {\displaystyle(b,n)=1} 則 ( a b , n ) = 1 {\displaystyle(ab,n)=1} ），含單位元素（即「1」），且任何一個元素 a {\displaystylea} 的反元素也在集合中（因為若 a ∈ S {\displaystylea\in{\cal{S}}} 則由群乘法封閉性任何 a {\displaystylea} 的冪次都在 S {\displaystyle{\cal{S}}} 中，所以 ⟨ a ⟩ {\displaystyle\langlea\rangle} 是 S {\displaystyle{\cal{S}}} 這個有限集的子集）。

根據定義， S {\displaystyle{\cal{S}}} 的階是 φ ( n ) {\displaystyle\varphi(n)} ，於是根據拉格朗日定理， S {\displaystyle{\cal{S}}} 中任何一個元素的階必整除 φ ( n ) {\displaystyle\varphi(n)} 。

證畢。

卡邁克爾函數[編輯] 主條目：卡邁克爾函數 卡邁克爾函數比歐拉函數更小。

費馬小定理也是它的特殊情況。

a λ ( n ) ≡ 1 ( mod n ) {\displaystylea^{\lambda(n)}\equiv1{\pmod{n}}} 多項式除法[編輯] p | x p − x ⇒ p k | ( x p − x ) k {\displaystylep|x^{p}-x\Rightarrowp^{k}|(x^{p}-x)^{k}} 除式： x p k ≡ ∑ i = 1 k ( − 1 ) i − 1 ( k i ) x p k − ( p − 1 ) i ( mod p k ) {\displaystyle\displaystylex^{pk}\equiv\sum_{i=1}^{k}(-1)^{i-1}{\binom{k}{i}}x^{pk-(p-1)i}{\pmod{p^{k}}}} 餘式： x p k + ( p − 1 ) n ≡ ∑ i = 1 k ( − 1 ) i − 1 ( n + i − 1 i − 1 ) ( n + k k − i ) x p k − ( p − 1 ) i ( mod p k ) {\displaystyle\displaystylex^{pk+(p-1)n}\equiv\sum_{i=1}^{k}(-1)^{i-1}{\binom{n+i-1}{i-1}}{\binom{n+k}{k-i}}x^{pk-(p-1)i}{\pmod{p^{k}}}} n=0時為除式，用數學歸納法證明餘式。

[6] 求 x 1000 ( mod 5 2 ) {\displaystylex^{1000}{\pmod{5^{2}}}} x 10 + 4 n ≡ ( n + 2 ) x 6 − ( n + 1 ) x 2 ( mod 5 2 ) {\displaystylex^{10+4n}\equiv(n+2)x^{6}-(n+1)x^{2}{\pmod{5^{2}}}} x 1000 ≡ 249 x 8 − 248 x 4 ≡ 24 x 8 − 23 x 4 ( mod 5 2 ) {\displaystylex^{1000}\equiv249x^{8}-248x^{4}\equiv24x^{8}-23x^{4}{\pmod{5^{2}}}} 注釋[編輯] ^符號的應用請參見同餘和模算數。

參見[編輯] 費馬大定理 拉格朗日定理 參考[編輯] ^Fermat'sLittleTheorem（頁面存檔備份，存於網際網路檔案館）.WolframMathWorld.（英文） ^Aproofofcertaintheoremsregardingprimenumbers.[2012-12-11].（原始內容存檔於2015-06-16）.  ^3.03.1許介彥.費馬小定理(PDF).科學教育月刊(私立大葉大學電機工程學系).2006年10月,(第293期):37–44[2015-04-18].（原始內容(PDF)存檔於2015-04-18）.  ^Howis(x+y)^p≡x^p+y^pmodpforanyprimenumberp.MathematicsStackExchange.2018-09-27[2021-04-26].（原始內容存檔於2022-03-25）（英語）.  ^聶靈沼;丁石孫.代数学引论第二版.北京:高等教育出版社.2000:第33頁.ISBN 7-04-008893-2. 使用|accessdate=需要含有|url=(幫助) ^黃嘉威.多项式除法解高次同余.數學學習與研究.2015,(9):第104頁[2015-07-19].（原始內容存檔於2020-10-20）.  取自「https://zh.wikipedia.org/w/index.php?title=费马小定理&oldid=72872271」 分類：​同餘數學定理隱藏分類：​CS1英語來源(en)含有訪問日期但無網址的引用的頁面含有英語的條目 導覽選單 個人工具 沒有登入討論貢獻建立帳號登入 命名空間 條目討論 臺灣正體 不转换简体繁體大陆简体香港繁體澳門繁體大马简体新加坡简体臺灣正體 查看 閱讀編輯檢視歷史 更多 搜尋 導航 首頁分類索引特色內容新聞動態近期變更隨機條目資助維基百科 說明 說明維基社群方針與指引互助客棧知識問答字詞轉換IRC即時聊天聯絡我們關於維基百科 工具 連結至此的頁面相關變更上傳檔案特殊頁面靜態連結頁面資訊引用此頁面維基數據項目 列印/匯出 下載為PDF可列印版 其他專案 維基共享資源 其他語言 العربيةБеларускаяБългарскиCatalàکوردیČeštinaDanskDeutschΕλληνικάEnglishEsperantoEspañolEuskaraفارسیSuomiVõroFrançaisArpetanעבריתMagyarBahasaIndonesiaItaliano日本語ქართულიҚазақша한국어LietuviųLatviešuമലയാളംМонголNederlandsNorskbokmålPolskiPiemontèisPortuguêsRomânăРусскийSrpskohrvatski/српскохрватскиSimpleEnglishSlovenčinaSlovenščinaShqipСрпски/srpskiSvenskaதமிழ்ไทยTürkçeУкраїнськаOʻzbekcha/ўзбекчаTiếngViệt 編輯連結