【正文】 即存在整數(shù) t，使得 m = 1 ? 2pt。 解 取奇素?cái)?shù) p， (p, a(a2 ? 1)) = 1，令 111111 22 ????????? aaaaaam ppp， 則 m顯然是合數(shù)。即若有整數(shù) a， (a, n) = 1，使得 a n ?1 ? 1 (mod n)， (6) 并不能保證 n 是素?cái)?shù)。 當(dāng) n ? 5時(shí)，有 n ? 1 2n， 2n ? 1? n2 。 顯然， 122921的素因數(shù)也在 31， 127或者數(shù)列 (5)中。 58 例 7 將 235 ? 1 = 34359738367分解因數(shù)。 注 ：例 5提供了一個(gè)求素因數(shù)的方法，就是說，整數(shù) bn ? 1的素因數(shù) p，是 bd ? 1（當(dāng) d?n時(shí)）的素因數(shù)，或者是形如 kn ? 1的數(shù)（當(dāng)2|? n， p 2時(shí)，是形如 2kn ? 1的數(shù) )。 若 d n，則結(jié)論 (ⅰ )得證。 若 x 0， y 0，由式 (4)知 1 ? b cy = b db ?ax = b d(ba) ?x ? b d (mod m)。 這與 d0的定義矛盾，所以式 (3)必成立。 因此，由上式及 d0的定義，利用定理 1，我們得到 1 ? rrqdm aaa ?? ?0)(? (mod m)， 即整數(shù) r滿足 a r ? 1 (mod m)， 0 ? r d0 。 解 記 P = x1x2? x?(m)，則 (P, m) = 1。 例 1 設(shè) n是正整數(shù)，則 5|? 1n ? 2n ? 3n ? 4n的充要條件是 4?n。 定理 2(Fermat) 設(shè) p是素?cái)?shù)，則對于任意的整數(shù) a，有 a p ? a (mod p)。 定理 1?Euler? 設(shè) m是正整數(shù)， (a, m) = 1，則 a??m) ? 1 (mod m)。 4. 設(shè) m與 n是正整數(shù)，證明： ?(mn)?((m, n)) = (m, n)?(m)?(n)。 習(xí) 題 三 1. 證明定理 1。 因?yàn)?n ? 1 3，所以 n ? 1與 n ? 1都不等于 3，當(dāng)然不被 3整除，所以 3?n，因此 6?n。 解 將正整數(shù) 1, 2, ? , n按它們與整數(shù) n的最大的公約數(shù)分類，則 n =? ? ? ? ? ? ????????????ni ndnidni nddndidndi nd ndddn1 |1),( |11),( | |)()(111 ??。 由定理 5可知， ?(n) = 1的充要條件是 n = 1或 2。 定理 5 設(shè) n是正整數(shù)， p1, p2, ? , pk是它的全部素因數(shù)，則 52 ?(n) = ? ?????npk pnpppn |21 )()())((11111111 ?。證畢。 由此及 (m1, m2) = 1得到 (m2x ? m1y, m1) = (m2x, m1) = 1 以及 (m2x ? m1y, m2) = (m1y, m2) = 1。 若 m1y ? m2x?R，則 (m1y ? m2x, m1m2) = 1，所以 (m1y ? m2x, m1) = 1，于是 (m2x, m1) = 1， (x, m1) = 1， x?X。 定理 3 設(shè) m1, m2?N， (m1, m2) = 1，又設(shè) },{},{ )(21)(21 21 mm yyyYxxxX ?? ?? ?? 與 分別是模 m1與 m2的簡化剩余系，則 A = { m1y ? m2x； x?X， y?Y } 是模 m1m2的簡化剩余系。 由以上結(jié)論及定理 1可知集合 A是模 m的一個(gè)簡化系。其次，由于 (a, m) = 1，所以，對于任意的 xi（ 1 ? i ? ?(m)）， xi?B，有 (axi, m) = (xi, m) = 1。 定理 1 整數(shù)集合 A是模 m的簡化剩余系的充要條件是 (ⅰ ) A中含有 ?(m)個(gè)整數(shù)； (ⅱ ) A中的 任何兩個(gè)整數(shù)對模 m不同余； (ⅲ ) A中的每個(gè)整數(shù)都與 m互素。 顯然， ?(m)就是在 m的一個(gè)完全剩余系中與 m互素的整數(shù)的個(gè)數(shù)。 顯然，若 R是模的簡化剩余類，則 R中的每個(gè)整數(shù)都與 m互素。 6. 設(shè) m1, m2, ? ,mn是兩兩互素的正整數(shù)， ?i（ 1 ? i ? n）是整數(shù)，并且 ?i ? 1 (mod mi)， 1 ? i ? n， ?i ? 0 (mod mj)， i ? j， 1 ? i, j ? n。 2. 證明：若 2p ? 1是奇素?cái)?shù)，則 (p!)2 ? (?1)p ? 0 (mod 2p ? 1)。 (7) 49 同理 ?? ?mi i mb1 2 (mod m)。 (6) 因此，整數(shù) 2, 3, ? , p ? 2可以兩兩配對使得式 (6)成立。這證明了唯一性。 解 因?yàn)?(a, p) = 1，所以由定理 2，式 (4)中的數(shù)構(gòu)成模 p的一個(gè)完全剩余系，因此必有數(shù) b滿足式 (5)。 例 1 設(shè) A = {x1, x2, ? , xm}是模 m的一個(gè)完全剩余系，以 {x}表示x的小數(shù) 部分，證明：若 (a, m) = 1，則 ?? ???mi i mm bax1 )1(21}{ 。 證明 由定理 1只需證明：若 xi?, xi???Xi， 1 ? i ? n，則由 A1x1? ? A2x2? ? ? ? Anxn? ? A1x1?? ? A2x2?? ? ? ? Anxn?? (mod m1? mn) (3) 可以得到 xi? = xi??， 1 ? i ? n。定理由歸納法得證。 當(dāng) n = 2時(shí)，由定理 3知定理結(jié)論成立。 證畢。證畢。 定理 2 設(shè) m ? 1， a， b是整數(shù)， (a, m) = 1， {x1, x2, ? , xm}是模 m的一個(gè)完全剩余系，則 {ax1 ? b, ax2 ? b, ? , axm ? b}也是模 m的一個(gè)完全剩余系。 由于 xi的選取是任意的，所以模 m的完全剩余系有無窮多個(gè)，通常稱 (ⅰ ) {0, 1, 2, ? , m ? 1}是模 m的最小非負(fù)完全剩余系； (ⅱ ) ）（當(dāng) mmm |22,1,0,1,12 }{ ?? ??? 或 ）（當(dāng) mmm |22 1,1,0,1,2 1 }{ ????? ?? 是模 m的絕對最小完全剩余系。 是模 m的一個(gè)剩余類。 6. 已知 99? 42762?? ，求 ?與 ?。 2. 證明定理 4。 (6) 由于 0 ? x, y ? 9，所以由式 (5)與式 (6)分別得出 x ? y ? 1 = 9或 18， 3 ? y ? x = 0或 11。 解 由 a2 ? 1 (mod p) ? p?a2 ? 1 = (a ? 1)(a ? 1)， 所以必是 p?a ? 1或 p?a ? 1， 即 a ? ?1 (mod p)或 a ?1 (mod p)。 設(shè)式 (4)對于 n = k成立，則有 ka2 ? 1 (mod 2k + 2) ?ka2 = 1 ? q2k + 2， 其中 q?Z，所以 12?ka = (1 ? q2k + 2)2 = 1 ? q ?2k + 3 ? 1 (mod 2k + 3)， 其中 q ?是某個(gè)整數(shù)。 例 6 證明：若 n是正整數(shù)，則 13?42n + 1 ? 3 n + 2 。 例 5 求 n = 77 的個(gè)位數(shù)。 注 ：一般地，計(jì)算 ab (mod m)常是一件比較繁復(fù)的工作 。 由于 789 ? 456 ? 123 ? 1 = 455， 7?455， 所以 7?1123456789。 為了證明結(jié)論 (ⅳ )，只需利用式 (2)及 100 ? 1， 101 ? ?3， 102 ? ?4， 103 ? ?1， ? (mod 13) 和 N = ?? ??????? 334500120201 1010 aaaaaaaaaa nn 。 證畢。 (2) 證明 留作習(xí)題。 定理 3 設(shè) a， b， c， d是整數(shù)，并且 a ? b (mod m)， c ? d (mod m)， (1) 則 (ⅰ ) a ? c ? b ? d (mod m)； (ⅱ ) ac ? bd (mod m)。 定理 1 下面的三個(gè)敘述是等價(jià)的： (ⅰ ) a ? b (mod m)； (ⅱ ) 存在整數(shù) q，使得 a = b ? qm； (ⅲ ) 存在整數(shù) q1， q2，使得 a = q1m ? r， b = q2m ? r， 0 ? r m。 39 第二章 同 余 同余是數(shù)論中的一個(gè)基本概念。 如果整數(shù) a與 b之差不能被 m整除，則稱 a與 b對于模 m不同余，或稱 a與 b不同余，模 m，記為 a?? b (mod m)。 證明 留作習(xí)題。 定理 4 設(shè) ai， bi（ 0 ? i ? n）以及 x， y都是整數(shù)，并且 x ? y (mod m)， ai ? bi (mod m)， 0 ? i ? n， 則 ?? ?? ? ni iini ii ybxa 00 (mod m)。 (ⅴ ) 由 ac ? bc (mod m) 得到 m│c(a ? b)，再由 (c, m) = 1和第一章第三節(jié)定理 4得到 m│a ? b，即 a ? b (mod m)。 結(jié)論 (ⅱ )， (ⅲ )用同樣方法證明。 解 100 ? 1， 101 ? 3， 102 ? 2， 103 ? ?1 (mod 7)，因此 ，)7( m o d1010678345012334500120201????????????? ??aaaaaaaaaaaaaaaaaaaN nn 42 即 7?N ? 7? ???? 678345012 aaaaaaaaa 。 因此 1252 ? ? 0 (mod 641)， 即 641? 1252 ? 。 解 利用定理 4有 (25733 ? 46)26 ? (733 ? 4)26 = [7?(72)16 ? 4]26 ? [7?( ?1)16 ? 4]26 = (7 ? 4)26 ? 326