【文章內(nèi)容簡(jiǎn)介】 ，11，13，14 (ii) 最小正簡(jiǎn)化剩余系：1，2，4，7，8，11，13，14(iii) 最大非正簡(jiǎn)化剩余系：－1,－2,－4,－7,－8,－11，－13，－14(iv) 最大負(fù)簡(jiǎn)化剩余系：－1,－2,－4,－7,－8,－11，－13，－14(v) 絕對(duì)（值）最小簡(jiǎn)化剩余系：－7，－4,－2，－1，1，2，4，7【例6】（例6）素?cái)?shù)p的簡(jiǎn)化剩余系為 1，2，……，p－1，即＝p－1【】（定理2）設(shè)整數(shù)，…，均與m互素，且兩兩模m不同余，則它們構(gòu)成模m的一個(gè)簡(jiǎn)化剩余系。（證）由題意知，…，是來(lái)自模m的不同簡(jiǎn)化剩余類的剩余，故是m的一個(gè)簡(jiǎn)化剩余系?！尽浚ㄑa(bǔ)）設(shè)整數(shù)，…，均與m互素，若它們構(gòu)成模m的一個(gè)簡(jiǎn)化剩余系，則這些必兩兩模m不同余。（證）由題意知，…，是來(lái)自模m的不同簡(jiǎn)化剩余類的剩余，而不同剩余類中的數(shù)必互不同余。【推論】（補(bǔ)）設(shè)整數(shù)，…，均與m互素，則它們構(gòu)成模m的簡(jiǎn)化剩余系的充分必要條件是這些兩兩模m不同余?！尽浚ǘɡ?）設(shè)m為正整數(shù)，a是滿足(a，m)＝1的整數(shù)。那么，若x遍歷模m的一個(gè)簡(jiǎn)化剩余系，則ax也遍歷模m的一個(gè)簡(jiǎn)化剩余系。（證）首先，由(a，m)＝1及(x，m)＝1知(ax，m)＝1，即ax是簡(jiǎn)化剩余類的剩余。其次，若 （mod m），則必有 （mod m）（否則，由 （mod m）及(a，m)＝1可得 （mod m），矛盾）因此x遍歷模m的一個(gè)簡(jiǎn)化剩余系時(shí)，ax遍歷個(gè)數(shù)，且它們兩兩m不同余?！纠?】（例7）已知1，7，11，13，17，19，23，29是模30的簡(jiǎn)化剩余系，(7，30)＝1，則7，19，17，1，29，13，11，23也是模30的簡(jiǎn)化剩余系?！纠?】設(shè)m＝7，a＝1，2，3，4，5，6，則ax為： x 123456112345622461353362514441526355316426654321【】（補(bǔ)）當(dāng)x遍歷m的簡(jiǎn)化剩余系時(shí)，x177。km也遍歷m的簡(jiǎn)化剩余系。（證）首先，由(x，m)＝1知(x177。km，m)＝1，即二者互素。其次，當(dāng) mod m，必有 177。km≠177。km （mod m）【推論】（補(bǔ)）設(shè)m為正整數(shù)，a是滿足(a，m)＝1的整數(shù)，則當(dāng)x遍歷m的簡(jiǎn)化剩余系時(shí)，m177。ax也遍歷m的簡(jiǎn)化剩余系?！尽浚ǘɡ?）設(shè)m為正整數(shù)，a是滿足(a，m)＝1的整數(shù)。則存在整數(shù)（1≤＜m）使得a≡1 （mod m）（證）（構(gòu)造性證明）由(a，m)＝1知存在整數(shù)s，t，使得sa＋tm＝(a，m)＝1即sa－1＝(－t)m因此，所求＝s?！纠?0】（例10）設(shè)m＝737，a＝635，求，滿足aa＇≡1 （mod m）（解）利用廣義歐幾里得除法，可找到s＝－224，t＝193，使得(－224) 635＋193737＝1 ∴ a＇≡－224≡513 mod 737即 635(－224) ≡1 mod 737【】（定理5）設(shè)，是兩個(gè)互素的正整數(shù)，若分別遍歷模，的簡(jiǎn)化剩余系，則遍歷模的簡(jiǎn)化剩余系。（證）先證屬于模的某個(gè)簡(jiǎn)化剩余類，即證（，）＝1事實(shí)上，由（，）＝1及（，）＝1和（，）＝1知（，）＝（，）＝（，）＝1（，）＝（，）＝（，）＝1∴ （，）＝1其次，證明：當(dāng) mod ， mod 時(shí)，有≠ mod 事實(shí)上，完全剩余系包含簡(jiǎn)化剩余系，故完全剩余系的性質(zhì)適用于簡(jiǎn)化剩余系?！緫?yīng)用】利用小的數(shù)的簡(jiǎn)化剩余系構(gòu)造大的數(shù)的簡(jiǎn)化剩余系?！纠浚ㄑa(bǔ)）設(shè)m＝77＝711，利用7和11的簡(jiǎn)化剩余系構(gòu)造77的簡(jiǎn)化剩余系。（解）取7的最小正簡(jiǎn)化剩余系為 x≡1，2，3，4，5，6 取11的最小正簡(jiǎn)化剩余系 y≡1，2，3，……，10則77的一個(gè)簡(jiǎn)化剩余系為11x＋7y即 18，25，32，39，46，53，60，67，74，81（x≡1）29，36，43，50，57，64，71，78，85，92（x≡2）40，47，54，61，68，75，82，89，96，103（x≡3）51，58，65，72，79，86，93，100，107，114（x≡4）62，69，76，83，90，97，104，111，118，125（x≡5）73，80，87，94，101，108，115，122，129，136（x≡6）或簡(jiǎn)化剩余系為（取最小非負(fù)簡(jiǎn)化剩余系）11x＋7y mod 7718，25，32，39，46，53，60，67，74， 4 （x≡1）29，36，43，50，57，64，71， 1， 8，15 （x≡2）40，47，54，61，68，75， 5，12，19，26 （x≡3）51，58，65，72， 2， 9，16，23，30，37 （x≡4）62，69，76， 6，13，20，27，34，41，48 （x≡5）73， 3，10，17，24，31，38，45，52，63 （x≡6）即 1， 2， 3， 4， 5， 6， 8， 9，10，12，13，15，16，17，18，19，20，23，24，25，26，27，29，30，31，32，34，36，37，38，39，40，41，43，45，46，47，48，50，51，52，53，54，57，58，59，60，61，62，64，65，67，68，69，71，72，73，74，75，76若選絕對(duì)值最小簡(jiǎn)化剩余系，則為38，37，36，34，32，31，30，29，27，26，25，24，23，20，19，18，17，16，15，13，12，10，9， 8， 6， 5， 4， 3， 2， 1，1， 2， 3， 4， 5， 6， 8， 9， 10， 12，13， 15， 16， 17， 18， 19， 20，23，24， 25，26， 27， 29， 30， 31， 32， 34，36，37， 38即 177。1， 177。2， 177。3， 177。4， 177。5， 177。6， 177。8， 177。9，177。10，177。12，177。13，177。15，177。16，177。17，177。18，177。19，177。20，177。23，177。24，177。25，177。26，177。27，177。29，177。30，177。31，177。32，177。34，177。36，177。37，177。38(三) 整數(shù)a模p的逆（1） 定義【】（對(duì)模m）的逆，記為。即 a≡1 mod m實(shí)質(zhì)上，a與互為逆元素?！纠繉?duì)任何模數(shù)m＞1而言，至少有兩個(gè)數(shù)有逆。即≡1， ≡m－1（mod m）（或≡－1）（2） 性質(zhì)【性質(zhì)1】若a可逆，則（a，m）=1。（證）a可逆，則a的逆存在，且滿足a≡1 （mod m）即存在整數(shù)k，使得a=1＋km= km＋1再由最大公因子的性質(zhì)知（a，m）=（m，1）=1而 （a，m）=1 （a，m）=1且（，m）=1【推論】a是模m的逆的充分必要條件是（a，m）=1?！拘再|(zhì)2】不唯一。即若存在，則＋km都是a的逆，其中k為任意整數(shù)。（證）只需直接驗(yàn)證：已知是a的逆，即a≡1 （mod m）那么，對(duì)任意整數(shù)k，有a(＋km) ≡a＋ akm≡a＋0≡1 （mod m）【例】設(shè)m＝7，a＝2，直接計(jì)算有……，2(－3)≡1 mod 7，24≡1 mod 7，211≡1 mod 7，218≡1 mod 7，……即對(duì)模7而言，整數(shù)4＋7k都是2的逆（k∈z）【性質(zhì)3】若b和c都是a的逆，則有b≡c （mod m）。（證）已知ab≡1 （mod m）， ac≡1 （mod m） 從而 ab≡ac （mod m）而(a,m)＝1，故由消去律知 b≡c （mod m）?！就普?】設(shè)整數(shù)a有逆，則整數(shù)b是a的逆的充分必要條件是b≡ （mod m）。即b＝+km（k∈z）。（證）只要驗(yàn)證當(dāng)b≡ （mod m）時(shí)，b也是a的逆即可。顯然?！纠吭O(shè)m＝50，3模50的逆為17，那么，只要b≡17 mod 50。如b＝……，－33，67，……都是3的逆。反之，20≠17 mod 50，則20不是3的逆?！就普?】在模m的一個(gè)簡(jiǎn)化剩余系中，a的逆是唯一的。【例】設(shè)m＝7，選模7的最小正簡(jiǎn)化剩余系{1，2，…，6}，則a＝2的逆＝4且唯一?！拘再|(zhì)4】（1）≡a。（2）≡（證）直接驗(yàn)證即可?！就普摗俊??！纠吭O(shè)m＝55，求8和24模55的逆。（解）首先可以觀察出2模55的逆為 ＝28所以 ≡≡≡≡7 mod 55≡≡≡≡37≡39（3） 計(jì)算的方法【方法1】利用簡(jiǎn)化剩余類的性質(zhì)枚舉求逆例 m＝11，a＝5，則51≡5， 52≡10， 53≡4， 55≡3，56≡8， 59≡1∴ ＝9 mod 11【方法2】利用輾轉(zhuǎn)相除法（） 【方法3】利用有關(guān)性質(zhì)（求大的數(shù)的逆）【方法4】利用歐拉函數(shù)和歐拉定理的結(jié)論（見后） 歐拉定理 費(fèi)馬小定理(一) 歐拉定理【】（Euler定理）（定理1）設(shè)m是大于1的整數(shù)，若整數(shù)a滿足(a，m)＝1，則有≡1 （mod m）（證）設(shè)為m的最小正簡(jiǎn)化剩余系，則當(dāng)(a，m)＝1時(shí)，也為模m的一個(gè)簡(jiǎn)化剩余系。故是模m的最小正剩余的某個(gè)排列。所以≡ （mod m）即≡ （mod m）又由(，m)＝1知，(，m)＝1，故有≡1 （mod m）【例1】（例1）設(shè)m＝7，a＝2，則(2，7)＝1 ，(7)＝6 模7的最小正簡(jiǎn)化剩余系為：1，2，3，4，5，6，則21≡2，22≡4，23≡6，24≡1，25≡3，26≡5 mod 7各等式兩邊相乘，有≡ mod 7即