費馬小定理 許介彥 私立大葉大學電機工程學系 壹 前言 我們在小時候都背過九九乘法表 ; 以 下是一個 六六乘法表 : 4 5 6 4 5 6 4 6 8 0 6 9 5 8 4 4 8 6 0 4 5 5 0 5 0 5 0 6 6 8 4 0 6 上表中的每個乘積除以 7 的餘數分別是 : 4 5 6 4 5 6 4 6 5 6 5 4 4 4 5 6 5 5 6 4 6 6 5 4 上表具有一個有趣的性質 : 它的每一 列 ( 及每一行 都是,,, 4, 5, 6 這六數 的一個排列 ; 同一列中沒有任何兩數相同 這個性質其實並不普遍 ; 對任意一個 大於 的正整數, 如果我們先畫出一個 ( ( 乘法表, 然後將表中的每個數 以該數除以 的餘數取代, 所得的表的每 一列未必都會是,,,, 等數的一 個排列, 例如當 = 6 質 : 時就不滿足上述性 4 5 4 5 4 0 4 0 0 4 4 0 4 5 5 4 如果您再多畫幾個表, 多嘗試幾個不 同的 值, 您將發現滿足上述性質的 由 小而大依序為,, 5, 7,,, K ; 為質數 似乎 是滿足上述性質的充要條件 當 不是質數時我們不難理解上述性 質為什麼一定不滿足, 因為如果 = b 且 與 b 皆大於, 那麼表中第 列的第 b 個 數將是 b 除以 的餘數, 也就是 0, 而 0 並非,,,, 等數之一 下面我們說明當 為質數時上述性質 一定能滿足, 即當 為質數時, 對任意一 個小於 的正整數, 表中第 列的,,, K,( 等 個數除以 的餘 數一定會是,,,, 等數的一個排 列, 也就是說, 這些餘數一定全都不為 0, 而且其中不會有任何兩個餘數相等 首先, 由於 是質數, 任意兩個小於 的正整數 ( 一定都與 互質 的乘積不 - 7 -
科學教育月刊第 9 期中華民國九十五年十月 可能是 的倍數, 因此第 列的所有 個 餘數的確全都不會是 0 接著我們利用歸謬證法來說明第 列 的 個餘數皆相異 假設有某兩個餘數 相等 : s t (mod 其中 s < t, 經過移項可得 即 t s ( t s 0 (mod 與 的乘積是 的倍數, 但這顯然 不可能, 因為 互質 t s 和 都小於, 都與 事實上, 仿照上面的論述, 您不難自 行證明 : 對任意整數 ( > 及整數, 只要 與 互質,,,, K,( 等數 一定會與,,,, 等數對模 而言同 餘 ( 不考慮順序的話 貳 費馬小定理 當 是質數時, 對任意與 互質的整 數, 由上面的討論我們知道,,,, ( 等數一定會與,,, K, 等數對 模 而言同餘, 因此,,, K,( 等 數的乘積一定會與,,, K, 等數的乘 積對模 同餘 : L ( L( (mod 即 (! (! (mod 由於 (! 與 互質, 我們可將上式左右 兩邊的 (! 消去而得 (mod. 這是數學上有名的 費馬小定理 (Fermt s little theorem, 因法國數學家 Pierre de Fermt(60665 而得名 如 果我們將上式的左右兩邊同時乘以 又可 得 (mod. 這是費馬小定理的另一個常見的形式 請 注意後面這個形式的費馬小定理對任意整 數 皆成立 ( 即使 是 的倍數仍成立 參 另一個證明 以下是費馬小定理的另一種證明方 式 首先, 我們用數學歸納法證明 : 當 為質數時, 對任意非負整數, 模 而言同餘 0 0 當 = 0 及 = 與 對 時顯然成立, 因為 且 假設當 為某正整數時 與 對模 同餘, 我們考慮 ( + 是否與 +同餘 由二項式定理可知 ( + = + + L + + 上式等號右邊除了頭尾兩項之外的每一項 都是 的倍數 ( 見參考資料 [], 因此對 模 而言, ( + + (mod 又由於我們假設, 所以由上式可得 ( + + (mod 因此 ( + 果然與 + 同餘 數學歸納法 的證明於焉完成 我們接著考慮 為負整數的情形 如 果 等於, 那麼 = = ( 顯然是 的倍數 ( 因為 與 兩數中必有 一數為偶數, 因此 與 對模 一定同餘 如果 不是, 那麼 一定是奇數, - 8 -
費馬小定理 因此 = [( ( ] 而我們已知 ( ( 是 的倍數 ( 因為 ( 為正整數, 所以此時的 也是 的倍數 綜合以上情形可知對任意質數 及任意整數, 與 對模 而言一定同餘 肆 有幾條項鍊? 以下我們換個角度, 從排列組合的觀 點來說明費馬小定理為什麼成立 假設我 們有 種不同顏色的珠子, 每種珠子各有 無窮多顆 ; 請考慮以下問題 : 從這些珠子 中挑出顏色不全相同的 顆珠子來串成項 鍊, 總共可作出多少種不同的項鍊? 我們 假設這裡的 是正整數, 是質數, 而如 果某串項鍊可經由另一串項鍊旋轉而得, 我們將這兩串項鍊視為同一種項鍊 如果我們先只考慮將任意 顆珠子串 成如下圖的一長條 珠串, 那麼作法顯然 有 種, 因為每顆珠子的顏色都有 種選擇 ( 下圖的 為 5: 每條珠串若依下面的方式將頭尾相接即對 應到一條項鍊 : 上述 條珠串中, 整條鍊子的珠子全部同色的有 條, 因此顏色不全相同的有 條 ; 但是這個數目還不是我們想要的答案, 因為我們要的是顏色不全相同的 項鍊而非珠串, 而 條珠串中有許多 珠串其實對應到相同的項鍊, 例如下面五 條珠串就都對應到同一條項鍊 : 我們尚待解決的問題是 : 一條項鍊有 可能在 中被重覆算了幾次? 以下我們將說明 : 每條項鍊都被算了不多不少正 好 次, 也就是如果我們將一條項鍊在不 同的位置剪斷, 所得的 條珠串必定全都 不同 採歸謬證法 ; 假設某條項鍊可在某兩 個不同的位置剪斷而得到兩條相同的珠 串 ; 如果這兩個剪斷的位置以反時鐘方向 來看是隔著 d( d < 顆珠子, 那麼將這 條項鍊往反時鐘方向旋轉 d 個位置後所得 的項鍊將會與原來的項鍊 重合 每 個位置的珠子的顏色都與旋轉之前相同 請留意由於 d = 將意味著項鍊上所有的 珠子同色, 因此 d 的值一定大於 既然這條項鍊旋轉 d 個位置後所得的 項鍊與原來的項鍊重合, 再旋轉 d 個位置 後所得的項鍊還是會與原來的項鍊重合, 依此類推, 旋轉 d, d, d, 4d, K 個位置後所 得的項鍊都將與原來的項鍊重合 ; 如果 = qd + r, 0 < r < d ( 因為 為質數所以 r 0, 那麼旋轉 qd 個位置後所得的項鍊一定與原來的項鍊重 合 ; 又由於旋轉 個位置後所得的項鍊也 一定會與原來的項鍊重合 ( 每顆珠子都繞 - 9 -
科學教育月刊第 9 期中華民國九十五年十月 了一整圈, 因此我們推知其實只須旋轉 qd = r 個位置 ( r < d 就能讓所得的項 鍊與原來的項鍊重合 依此類推, 我們由 r 又一定能找到一個更小的正整數 r ( 0 < r < r 使得旋轉 r 個位置後所得的項鍊與原來的項鍊重合, 由 r 我們又一定能找到一個更小的 r, 由 r 我們又一定能找到一個更小的 r ; 由於介於 0 與 d 之間的整數個數有限, 我們不可能可以無窮 盡地找下去 ( 無窮遞降, 可見一開始的假 設是錯的, 因此對任意一條珠子顏色不全 相同的項鍊, 如果我們在不同的位置將項 鍊剪斷, 所得的珠串一定不同 既然每條項鍊在 中都被算了正好 次, 我們所求的項鍊個數因此就等於 ( / ; 此數既然是項鍊的 個數 當 然一定是一個整數, 因此 必定是 的倍數, 也就是說, 與 對模 而言一定同餘, 這就說明了費馬小定理在 為正 整數時的情形 伍 幾個應用 下面是費馬小定理的三個簡單的應用 例題一 : 求出 8000 5 除以 7 的餘數是多少 由於 5 和 7 互質, 由費馬小定理可 知對模 7 而言, 5 6, 所以 5 8000 5 5 因此所求為 例題二 : 6 + 4 (5 6 5 假設 為任意一個大於 5 的質數 試證 : 必可整除 = K( 假設這是十進 制中由 個 構成的數 由於 和 0 互質而且 9 = 0, 由費馬小定理可知對模 而言, 0, 因此 一定能整除 9 又由於 和 9 互質, 因此 一定能整除 例題三 : 假設 = k + 是一個質數 試證 : 如 果 可整除 + b + b( 和 b 都是整數, 那麼 和 b 必定都是 的倍數 由於 可整除 + b + b, 必定也能 整除 ( b( + b + b = b, 因此 b (mod 左右兩邊同時取 k 次方, 得 k k b (mod ( 假設 不能整除, 那麼 必定也不 能整除 b; 由費馬小定理可知對模 而言, b 將 = k + 代入上式得 因此 k + k+ b ( 綜合 ( 式與 ( 式可知 b (mod, + b + b + + ; 既然 是 的倍數且 和 互質, 可知 一定是 的倍數, 這與我們假設的 不能整 除 矛盾 ; 因此 和 b 必定都是 的倍數 陸 形如 4k+ 的質數個數 在本刊第 54 期 數不盡的質數 一文中, 筆者曾經介紹如何證明形如 k + 的質數與形 如 4 k + 的質數都各有無窮多個 以下我們證 - 40 -
費馬小定理 明形如 4 k + 的質數也有無窮多個 假設 是任意一個大於 的正整數 ; +! 顯然為偶數, 因此 (! 為奇數, 而 + (! 的每個質因數都可表為 4k 或 4 k + 的形式 + 假設 = 4k 是 (! 的一個質因 數 ( 可知 和! 互質, 由於 (! (mod 將左右兩邊同時取 ( / 次方, 得 (! ( ( / (mod 由於 ( / = k 為奇數, 因此 (! (mod 但這與費馬小定理牴觸, 因為根據費馬小 定理, 由於 和! 互質,(! 必定會和 對模 同餘 + 由此我們推知 (! 不可能有形如 + 4k 的質因數, 也就是 (! 只有形如 + 4 k + 的質因數 又由於 (! 的每個質 因數顯然都大於, 因此我們證明了 : 不 管 是多少, 一定有比 大而且形如 4 k + 的質數存在, 這就說明了等差數列, 5, 9,,K 中包含著無窮多個質數 柒 費馬小定理的逆命題 當 為質數, 由費馬小定理我們知道 必定是 的倍數 ( 即前面的討論中當 = 的情形 ; 反過來說成不成立呢? 也就是說, 如果有某個正整數 可以整除, 我們能不能斷定 一定是質數呢? 如果可以的話, 這將是個不錯的判別任意 整數 是否為質數的方法 ; 歷史上確實曾 經有一段時期數學家們猜測這個方法是可 行的, 不過法國數學家 Pierre Srrus 於西 元 89 年指出 = 4是一個反例 ;4 是 與 的乘積, 因此不是質數, 但是由 4 = [( 0 4 ] = [( ( L] = (0( L = ((4( L 可知 4 能整除 4 對任意正整數, 如果有某個大於 的正整數 本身不是質數卻能整除, 我們稱 對底數 而言是一個 偽質數 ( 英文常稱作 -seudorime 因此 對底數 而言,4 是一個偽質數 ( 即 4 4 是一個 -seudorime 幾個衍生出來的問題是 :4 是唯一 的 -seudorime 嗎? 除了奇數的偽質數 外, 是否還存在著 偶偽質數? 對任意 正整數,-seudorime 的個數是有限或 是無限? 對底數 而言, 如果 是一個奇偽質 數, 我們不難證明 將是另一個更大的奇偽質數 ( 見練習題 4; 既然我們已知奇 偽質數 4 的存在, 對底數 來說奇偽質 數的個數因此是無窮的 尋找偶偽質數 ( 對 底數 而言 的工作比尋找奇偽質數要困 難許多, 其中最小的數直到西元 950 年才 由美國數學家 D. H. Lehmer 找到, 其值為 608 = 7 0 由於 608 = ( 607 0 要說明 608 可以整除 608, 我們只需說明 7 與 0( 此兩數皆為質數 都 能整除 607 即可 由於 607 可經質 - 4 -
科學教育月刊第 9 期中華民國九十五年十月 因數分解為 9 67, 因此 607 = ( 9 9 67 9 67 = ( = (5( L = 7(7( L 可知 7 能整除 607 又由於 607 = ( 9 9 67 9 67 = ( 9 ( L ( L = (0(48677( L 因此 0 的確也能整除 607 數學家 N. G. W. H. Beeger 於 95 年證明了對底 數 而言, 偶偽質數的個數也是無窮的 數學上還能證明 : 對任意正整數, 以 為底數的偽質數的個數都是無窮的 捌 絕對的偽質數 -seudorime 的個數是無窮的, -seudorime 的個數也是無窮的 ; 是否存 在整數 使得 既是 -seudorime 又是 -seudorime 呢? 答案是肯定的 ; 令人訝 異的是, 我們甚至還能找到合數 使得不 管 是多少, 都能整除 存在合數 使得 9, 也就是說,,, 4 4, K全 都是 的倍數 這樣的 不僅存在而且還 有不只一個, 其中最小的是 56 = 7 由於 56 = ( = [( 560 0 而由費馬小定理可知 數, 因此 56 = [( 0 ( L] = ( 56 56 ] ( L 必定是 的倍 也必定是 的倍數 經 由類似的方法可推知 也必定是 的倍數和 7 的倍數, 因此不論 是多少, 56 必定是 56 的倍數 如果不論 是多少, 合數 都能整除 56 ( 即 都是 -seudorime, 數學上稱 為一個 絕對偽質數 ( bsolute seudorime, 亦稱作 Crmichel umber, 因美國數學家 R. D. Crmichel 而得名 ; 他在西元 909 年首先注意到有這 種數的存在, 最小的十個依序為 56, 05, 79, 465, 8, 660, 89, 0585, 584, 94 Crmichel umber 的總數 到底是有限或是無限的問題曾經困擾了數 學家許多年, 直到 994 年才被證明出來其 個數是無窮的 Crmichel umbers 在數線上的分布 比質數稀疏許多, 例如在所有小於一百萬 的正整數中, 總共有 78498 個質數, 總共 有 45 個 -seudorime, 但是總共只有 4 個 Crmichel umber 玖 需要洗幾次牌? 考慮以下動作 : 將一副撲克牌 (5 張 由中間分成各含 6 張牌的兩小疊, 然後洗 牌使得這兩疊牌一張一張交錯, 重新組合 成 5 張牌 下圖顯示了洗牌前後位置的變 化 : 6 7 8 9 5 7 8 9 我們稱上述動作為洗牌一次 請問 : 經過洗牌幾次後可使得每張牌都回到它最 原始的位置? 6-4 -
費馬小定理 由上圖洗牌前後的位置變化, 我們看 到原來在位置編號,,, K, 6 的牌經過一 次洗牌後將被放到編號, 4, 6, K, 5 的位 置, 而原來編號 7, 8, 9, K, 5 的牌則被放 到了編號,, 5,, 5 的位置, 因此如果 某張牌原來的位置為 x, 經過一次洗牌後 的位置為 y, 那麼 y 與 x 的關係為 y x (mod 5 ; 因此這張牌經過 次洗 牌後的位置必定與 x 對模 5 同餘, 而我們的目標是希望能找到某個 使得對所有 x 5, x x (mod 5. 既然 x 與 5 互質 ( 因為 5 為質數, 我們可將上式左右兩邊的 x 約掉而得 (mod 5 由費馬小定理我們知道 = 5 一定滿足上 式 ; 事實上,5 是滿足上式最小的 ( 我 們在此不予證明 因此經過 5 次洗牌後 所有的牌必定都回到了原始的位置 一般而言, 如果一副牌有 m 張 (m 為 偶數, 而正整數 滿足 (mod m + 那麼經過上述方式洗牌 次後所有的牌必 定都回到了原始的位置 舉例來說, 如果 m = 6, 那麼我們只 需洗牌 6 次即可, 因為 6 (mod 6 選擇的一個整數, 與 對模 同餘的機率並不高 我們在小學都學過如何判斷一個正 整數 是否為質數, 只要測試介於 與 之間的整數是否有 的因數即可 ( 事實上只須測試 個數即足夠 ; 但是當 很大時 ( 例如當 是 00 位數, 要判斷 是否 為質數的工作將變得相當困難 我們這裡 所謂的 難 當然不是說完全沒有方法解 決, 而是很難在短時間內解決 ; 然而質數 的判定卻是某些領域裡常需面臨的問題, 例如密碼學裡就有許多演算法在應用上需 要由電腦隨機產生很大的質數, 因此實際 應用上很需要有較快的方法來判斷一個大 整數是否為質數 當我們要判斷 是否為質數, 如果我 們選擇幾個不同的 值 ( 例如 =,, 5, 7, 分別計算 除以 的餘數, 結果發現所有的餘數都是, 那麼 為質數的機率其實相當高, 而如果有任何 一個餘數不是 我們立即可確定 不是質 數 這個方式雖然不能保證通過測試的 一定是質數, 但是在大部分情形下卻可以 有效地將合數剔除, 可以在判斷質數的過 程中提供初步而快速的篩選, 因此為許多 實際程式所採用 拾 質數的判定 費馬小定理的逆命題 (coverse 雖然不成立, 不過偽質數與 Crmichel umbers 的數量在所有正整數中畢竟只占少數, 因此如果 不是質數, 對我們任意 拾壹 結語 費馬小定理最早出現於西元 640 年 Fermt 寫給友人的一封信上, 他在信中聲稱他知道如何證明這個定理, 只是因為信紙的空間太小了以至未能寫下其證明 ( 這 - 4 -
科學教育月刊第 9 期中華民國九十五年十月 是他出了名的 習慣 正式發表的證明 要等到大約 00 年後才由數學家 Euler 於 76 年提出,Euler 所用的方法是本文介 紹的第二種證明方式 ( 即利用二項式定理 的方式 ; 不過由數學家 Leibiz 留下的未 發表過的手稿顯示他應該早在 68 年之 前就已經用相同的方法證明出來了 如果某個合數 滿足 : 對任意整數, 只要 與 互質, 就一定能整除, 那麼 其實就是一個 Crmichel umber; 這是 Crmichel umbers( 即絕 對偽質數 的另一種常見的定義方式 ; 兩 種方式本質上並無不同 既然有費馬小定理自然有費馬 大 定理 (Fermt s gret theorem; 費馬大定 理也就是一般俗稱的費馬最後定理 (Fermt s lst theorem 小 與 大 只是在名稱上做區隔 ; 就重要性而言, 費 馬小定理其實並不小, 它所表達的關係不 僅漂亮, 在數學上更有相當廣泛的應用 拾貳 練習題 以下是幾個與本文相關的問題, 提供 讀者參考. 試說明當 為質數且不等於 時, 必定可被 整除. 試證 : 對任意正整數 與 b, 等差數 列, + b, + b, K 中必含有無窮多 個合數. 試證 : 對任意質數, 的每個質因數都大於 4. 試證 : 如果 對底數 而言是奇偽 質數, 那麼 必定也是一個奇偽質數 5. 假設我們將手上的一疊撲克牌的最 頂端與最底端的兩張牌抽出來放在 桌上, 再將剩下的牌的最頂端與最底 端的兩張牌抽出來疊在桌上的兩張 牌上面, 並持續上述動作以完成一次 洗牌 以 8 張牌為例, 洗牌前後的位 置變化如下圖所示 : 4 5 6 7 8 試證 : 如果一開始有 4 5 6 7 8 張牌, 經過 + 次洗牌後必可使得每張牌都回 到它原始的位置 6. 假設 為質數且 與 互質 試證 : 參考資料 如果 d 是滿足 d (mod 的最小正整數, 那麼 d 一定是 的因數 許介彥.(00, 數不盡的質數, 科學教育月刊, 第 54 期 許介彥.(00, 同餘的基本概念, 科學教育月刊, 第 6 期 許介彥.(004, 巴斯卡三角形的幾個性質, 科學教育月刊, 第 75 期 G. H. Hrdy d E. M. Wright, A Itroductio to the Theory of Numbers, 5th editio, Oxford, 979. - 44 -