簡(jiǎn)化剩余系與歐拉函數(shù).doc

《簡(jiǎn)化剩余系與歐拉函數(shù).doc》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。

1、§3簡(jiǎn)化剩余系與歐拉函數(shù)定義歐拉函數(shù)是一個(gè)定義在正整數(shù)集上的函數(shù)，的值等于系列中與互質(zhì)的整數(shù)的個(gè)數(shù)。當(dāng)時(shí)，當(dāng)為質(zhì)數(shù)時(shí)，定義如果一個(gè)模的剩余類里的數(shù)與互質(zhì)（在模的一個(gè)剩余類中，只要有其中一個(gè)數(shù)和互質(zhì)，則該剩余類中所有的數(shù)就都與互質(zhì)），就把它叫做一個(gè)與互質(zhì)的剩余類.在與互質(zhì)的全部剩余類中，各取一個(gè)數(shù)所組成的一組數(shù)，叫做模的一個(gè)簡(jiǎn)化剩余系.定理1模的一個(gè)簡(jiǎn)化剩余系含有個(gè)數(shù).證模的全部剩余類是.因?yàn)椋詫?duì)每個(gè)，是一個(gè)與互質(zhì)的剩余類的充要條件是因此，在模的全部剩余類中，與互質(zhì)的全部剩余類是滿足條件的所有剩余類.這樣的剩余類公有個(gè)，故由簡(jiǎn)化剩余系的定義知，模的簡(jiǎn)化剩余系含有個(gè)數(shù).

2、定理2若是個(gè)與互質(zhì)的整數(shù)，則是模的一個(gè)簡(jiǎn)化剩余系的充要條件是它們兩兩對(duì)模不同余.證必要性設(shè)是模的一個(gè)簡(jiǎn)化剩余系，則由簡(jiǎn)化剩余系的定義，這個(gè)數(shù)是取自模的不同剩余類的，故這個(gè)數(shù)兩兩對(duì)模不同余.充分性設(shè)與互質(zhì)的個(gè)整數(shù)兩兩對(duì)模不同余.因每個(gè)整數(shù)都與互質(zhì)，故每個(gè)整數(shù)都屬于一個(gè)與互質(zhì)的剩余類.因這個(gè)整數(shù)兩兩對(duì)模不同余，故這個(gè)整數(shù)分別屬于不同的與互質(zhì)的剩余類.另一方面，與互質(zhì)的剩余類共有個(gè)，故分別屬于這個(gè)與互質(zhì)的剩余類，故是模的一個(gè)簡(jiǎn)化剩余系.定理3若通過模的簡(jiǎn)化剩余系，則也通過模的簡(jiǎn)化剩余系。證當(dāng)通過模的簡(jiǎn)化剩余系時(shí)，通過個(gè)整數(shù).由于故故所通過的這個(gè)整數(shù)都與互質(zhì).下面證明這個(gè)整數(shù)兩

3、兩對(duì)模不同余.假設(shè)在這個(gè)整數(shù)中，有兩個(gè)整數(shù)對(duì)模同余，設(shè)（1）其中是所通過的模的簡(jiǎn)化剩余系中兩個(gè)不同的數(shù)，則由及（1）式得另一方面，因是所通過的模的簡(jiǎn)化剩余系中兩個(gè)不同的數(shù)，它們不屬于模的同一個(gè)剩余類，故它們對(duì)模不同余，矛盾.因此，根據(jù)定理2，這個(gè)整數(shù)組成模的簡(jiǎn)化剩余類.定理4若分別通過模的一個(gè)簡(jiǎn)化剩余系，則通過模的一個(gè)簡(jiǎn)化剩余系。證首先證明，當(dāng)分別通過模的一個(gè)簡(jiǎn)化剩余系時(shí)，個(gè)整數(shù)都與互質(zhì).因?yàn)樗云浯巫C明，當(dāng)分別通過模的一個(gè)簡(jiǎn)化剩余系時(shí)，個(gè)整數(shù)兩兩對(duì)模不同余.設(shè)這里是所通過的模的簡(jiǎn)化剩余系中的數(shù)，是所通過的模的簡(jiǎn)化剩余系中的數(shù)，則，同理，最后證明，與互質(zhì)的任意一個(gè)整數(shù)，

4、都會(huì)與某個(gè)對(duì)模同余，即因?yàn)?，所以因，故由定?得，會(huì)與某個(gè)對(duì)模同余，即同理，會(huì)與某個(gè)對(duì)模同余，即于是，因，故由上式得，由定理4，立即得到下面的推論。推論設(shè)則定理5設(shè)的標(biāo)準(zhǔn)分解式為，則證由定理4的推論得下面證明，當(dāng)為質(zhì)數(shù)時(shí)，由歐拉函數(shù)的定義，等于中所有與互質(zhì)的個(gè)數(shù)，也就是中所有與互質(zhì)的整數(shù)個(gè)數(shù).故等于減去在中與不互質(zhì)的整數(shù)個(gè)數(shù)。因?yàn)橘|(zhì)數(shù)，故在中，與不互質(zhì)的整數(shù)個(gè)數(shù)為.從而補(bǔ)充題若為模數(shù)的任一縮系，則證法一因?yàn)槟?shù)的一個(gè)縮系，，故也是模數(shù)的一個(gè)縮系，于是當(dāng)為奇數(shù)時(shí)，故此時(shí)命題成立。當(dāng)為偶數(shù)時(shí)，設(shè)這里為正整數(shù),為正奇數(shù)。因，故當(dāng)通過模數(shù)的一個(gè)縮系，通過模數(shù)的縮系時(shí)，通過模數(shù)的

5、一個(gè)縮系。因?yàn)槠鏀?shù)，故于是以上最后一個(gè)同余式成立是因?yàn)椋?dāng)時(shí)，因，故此時(shí)；當(dāng)時(shí)，為偶數(shù)，此時(shí)，證法二因?yàn)榈囊粋€(gè)縮系，故（1）因，故為偶數(shù)。若，則（因?yàn)槿簦瑒t，由此會(huì)引出矛盾.當(dāng)為奇數(shù)時(shí)顯然是矛盾的：當(dāng)為偶數(shù)時(shí)，，這與矛盾.）且因此，在模的完全剩余系中，與?；ベ|(zhì)的數(shù)是成對(duì)出現(xiàn)的，每一對(duì)與互質(zhì)的數(shù)滿足且其中一個(gè)在區(qū)間中，另一個(gè)在區(qū)間，共有對(duì).故（2）由（1），（2）兩式即可得作業(yè)P61：2，3，4.習(xí)題選解2.若是大于的正整數(shù)，是整數(shù)，通過模的簡(jiǎn)化剩余系，則（1）其中表示展布在所通過的一切值上的和式。證因?qū)θ我庹麛?shù)及任意實(shí)數(shù)，有由此易得，若，則因通過模的簡(jiǎn)化剩余系，故通過模

6、的簡(jiǎn)化剩余系.（2）因，故為偶數(shù).若，則（因?yàn)槿?，則，由此會(huì)引出矛盾.當(dāng)為奇數(shù)時(shí)顯然是矛盾的：當(dāng)為偶數(shù)時(shí)，，這與矛盾.）且因此，在模的完全剩余系中，與?；ベ|(zhì)的數(shù)是成對(duì)出現(xiàn)的，每一對(duì)與互質(zhì)的數(shù)滿足且其中一個(gè)在區(qū)間中，另一個(gè)在區(qū)間，共有對(duì).故（3）由（2），（3）兩式即知，（1）式成立.3.(ⅰ)證明質(zhì)數(shù).(ⅱ)證明，其中表示展布在的一切正因數(shù)上的和式.證(ⅰ)因故(ⅱ)證一當(dāng)時(shí)，結(jié)論顯然成立。下設(shè)又設(shè)的標(biāo)準(zhǔn)分解式為下面對(duì)用數(shù)學(xué)歸納法證明，當(dāng)時(shí)，由(ⅰ)知結(jié)論正確。假設(shè)結(jié)論對(duì)成立，下證結(jié)論對(duì)也成立.由(ⅰ)中的結(jié)論及歸納假設(shè)得證二當(dāng)時(shí)，結(jié)論顯然成立.下設(shè)又設(shè)的標(biāo)準(zhǔn)分解式為則

7、4.若是個(gè)兩兩互質(zhì)的正整數(shù)，分別通過模的簡(jiǎn)化剩余系，則通過模的簡(jiǎn)化剩余系，其中證法一：因是個(gè)兩兩互質(zhì)的正整數(shù)，故由上一節(jié)習(xí)題2知，若分別通過模的完全剩余系，則通過模的完全剩余系。若，則反之，若，則從而這就證明了定理的結(jié)論.證法二：首先證明，當(dāng)分別通過模的一個(gè)簡(jiǎn)化剩余系時(shí)，個(gè)整數(shù)都與互質(zhì).因?yàn)樗云浯巫C明，當(dāng)分別通過模的一個(gè)簡(jiǎn)化剩余系時(shí)，個(gè)整數(shù)兩兩對(duì)模不同余.設(shè)這里是所通過的模的簡(jiǎn)化剩余系中的數(shù)，，則，最后證明，與互質(zhì)的任意一個(gè)整數(shù)，都會(huì)與某個(gè)對(duì)模同余，即因?yàn)?，所以因，故由定?得，會(huì)與某個(gè)對(duì)模同余，即于是，因是個(gè)兩兩互質(zhì)的正整數(shù)，故由上式