資源描述：
《簡化剩余系與歐拉函數(shù).doc》由會員上傳分享，免費在線閱讀，更多相關內(nèi)容在教育資源-天天文庫。
1、§3簡化剩余系與歐拉函數(shù)定義歐拉函數(shù)是一個定義在正整數(shù)集上的函數(shù)，的值等于系列中與互質(zhì)的整數(shù)的個數(shù)。當時，當為質(zhì)數(shù)時，定義如果一個模的剩余類里的數(shù)與互質(zhì)（在模的一個剩余類中，只要有其中一個數(shù)和互質(zhì)，則該剩余類中所有的數(shù)就都與互質(zhì)），就把它叫做一個與互質(zhì)的剩余類.在與互質(zhì)的全部剩余類中，各取一個數(shù)所組成的一組數(shù)，叫做模的一個簡化剩余系.定理1模的一個簡化剩余系含有個數(shù).證模的全部剩余類是.因為，所以對每個，是一個與互質(zhì)的剩余類的充要條件是因此，在模的全部剩余類中，與互質(zhì)的全部剩余類是滿足條件的所有剩余類.這樣的剩余類公有個，故由簡化剩余系的定義知，模的簡化剩余系含有個數(shù).
2、定理2若是個與互質(zhì)的整數(shù)，則是模的一個簡化剩余系的充要條件是它們兩兩對模不同余.證必要性設是模的一個簡化剩余系，則由簡化剩余系的定義，這個數(shù)是取自模的不同剩余類的，故這個數(shù)兩兩對模不同余.充分性設與互質(zhì)的個整數(shù)兩兩對模不同余.因每個整數(shù)都與互質(zhì)，故每個整數(shù)都屬于一個與互質(zhì)的剩余類.因這個整數(shù)兩兩對模不同余，故這個整數(shù)分別屬于不同的與互質(zhì)的剩余類.另一方面，與互質(zhì)的剩余類共有個，故分別屬于這個與互質(zhì)的剩余類，故是模的一個簡化剩余系.定理3若通過模的簡化剩余系，則也通過模的簡化剩余系。證當通過模的簡化剩余系時，通過個整數(shù).由于故故所通過的這個整數(shù)都與互質(zhì).下面證明這個整數(shù)兩
3、兩對模不同余.假設在這個整數(shù)中，有兩個整數(shù)對模同余，設（1）其中是所通過的模的簡化剩余系中兩個不同的數(shù)，則由及（1）式得另一方面，因是所通過的模的簡化剩余系中兩個不同的數(shù)，它們不屬于模的同一個剩余類，故它們對模不同余，矛盾.因此，根據(jù)定理2，這個整數(shù)組成模的簡化剩余類.定理4若分別通過模的一個簡化剩余系，則通過模的一個簡化剩余系。證首先證明，當分別通過模的一個簡化剩余系時，個整數(shù)都與互質(zhì).因為所以其次證明，當分別通過模的一個簡化剩余系時，個整數(shù)兩兩對模不同余.設這里是所通過的模的簡化剩余系中的數(shù)，是所通過的模的簡化剩余系中的數(shù)，則，同理，最后證明，與互質(zhì)的任意一個整數(shù)，
4、都會與某個對模同余，即因為，所以因，故由定理3得，會與某個對模同余，即同理，會與某個對模同余，即于是，因，故由上式得，由定理4，立即得到下面的推論。推論設則定理5設的標準分解式為，則證由定理4的推論得下面證明，當為質(zhì)數(shù)時，由歐拉函數(shù)的定義，等于中所有與互質(zhì)的個數(shù)，也就是中所有與互質(zhì)的整數(shù)個數(shù).故等于減去在中與不互質(zhì)的整數(shù)個數(shù)。因為質(zhì)數(shù)，故在中，與不互質(zhì)的整數(shù)個數(shù)為.從而補充題若為模數(shù)的任一縮系，則證法一因為模數(shù)的一個縮系，，故也是模數(shù)的一個縮系，于是當為奇數(shù)時，故此時命題成立。當為偶數(shù)時，設這里為正整數(shù),為正奇數(shù)。因，故當通過模數(shù)的一個縮系，通過模數(shù)的縮系時，通過模數(shù)的
5、一個縮系。因為奇數(shù)，故于是以上最后一個同余式成立是因為，當時，因，故此時；當時，為偶數(shù)，此時，證法二因為的一個縮系，故（1）因，故為偶數(shù)。若，則（因為若，則，由此會引出矛盾.當為奇數(shù)時顯然是矛盾的：當為偶數(shù)時，，這與矛盾.）且因此，在模的完全剩余系中，與模互質(zhì)的數(shù)是成對出現(xiàn)的，每一對與互質(zhì)的數(shù)滿足且其中一個在區(qū)間中，另一個在區(qū)間，共有對.故（2）由（1），（2）兩式即可得作業(yè)P61：2，3，4.習題選解2.若是大于的正整數(shù)，是整數(shù)，通過模的簡化剩余系，則（1）其中表示展布在所通過的一切值上的和式。證因?qū)θ我庹麛?shù)及任意實數(shù)，有由此易得，若，則因通過模的簡化剩余系，故通過模
6、的簡化剩余系.（2）因，故為偶數(shù).若，則（因為若，則，由此會引出矛盾.當為奇數(shù)時顯然是矛盾的：當為偶數(shù)時，，這與矛盾.）且因此，在模的完全剩余系中，與?；ベ|(zhì)的數(shù)是成對出現(xiàn)的，每一對與互質(zhì)的數(shù)滿足且其中一個在區(qū)間中，另一個在區(qū)間，共有對.故（3）由（2），（3）兩式即知，（1）式成立.3.(ⅰ)證明質(zhì)數(shù).(ⅱ)證明，其中表示展布在的一切正因數(shù)上的和式.證(ⅰ)因故(ⅱ)證一當時，結(jié)論顯然成立。下設又設的標準分解式為下面對用數(shù)學歸納法證明，當時，由(ⅰ)知結(jié)論正確。假設結(jié)論對成立，下證結(jié)論對也成立.由(ⅰ)中的結(jié)論及歸納假設得證二當時，結(jié)論顯然成立.下設又設的標準分解式為則
7、4.若是個兩兩互質(zhì)的正整數(shù)，分別通過模的簡化剩余系，則通過模的簡化剩余系，其中證法一：因是個兩兩互質(zhì)的正整數(shù)，故由上一節(jié)習題2知，若分別通過模的完全剩余系，則通過模的完全剩余系。若，則反之，若，則從而這就證明了定理的結(jié)論.證法二：首先證明，當分別通過模的一個簡化剩余系時，個整數(shù)都與互質(zhì).因為所以其次證明，當分別通過模的一個簡化剩余系時，個整數(shù)兩兩對模不同余.設這里是所通過的模的簡化剩余系中的數(shù)，，則，最后證明，與互質(zhì)的任意一個整數(shù)，都會與某個對模同余，即因為，所以因，故由定理3得，會與某個對模同余，即于是，因是個兩兩互質(zhì)的正整數(shù)，故由上式
