資源描述：
《第三節(jié) 簡化剩余系》由會員上傳分享，免費在線閱讀，更多相關內(nèi)容在行業(yè)資料-天天文庫。
1、初等數(shù)論第二章同余第三節(jié)簡化剩余系在模m的完全剩余系中，與m互素的整數(shù)所成的集合有一些特殊的性質(zhì)，我們要在這一節(jié)中對它們做些研究。定義1設R是模m的一個剩余類，若有a?R，使得(a,m)=1，則稱R是模m的一個簡化剩余類。顯然，若R是模的簡化剩余類，則R中的每個整數(shù)都與m互素。例如，模4的簡化剩余類有兩個：R1(4)={L,-7,-3,1,5,9,L}，R3(4)={L,-5,-1,3,7,11,L}。定義2對于正整數(shù)k，令函數(shù)j(k)的值等于模k的所有簡化剩余類的個數(shù)，稱j(k)為Euler函數(shù)，或Euler—j函數(shù)。例如，容易驗證j(2)=1，j
2、(3)=2，j(4)=2，j(7)=6。顯然，j(m)就是在m的一個完全剩余系中與m互素的整數(shù)的個數(shù)。定義3對于正整數(shù)m，從模m的每個簡化剩余類中各取一個數(shù)xi，構成一個集合{x1,x2,L,xj(m)}，稱為模m的一個簡化剩余系（或簡稱為簡化系）。顯然，由于選取方式的任意性，模m的簡化剩余系有無窮多個。例如，集合{9,-5,-3,-1}是模8的簡化剩余系，集合{1,3,5,7}也是模8的簡化剩余系，通常稱最小非負簡化剩余系。定理1整數(shù)集合A是模m的簡化剩余系的充要條件是(ⅰ)A中含有j(m)個整數(shù)；(ⅱ)A中的任何兩個整數(shù)對模m不同余；(ⅲ)A中的
3、每個整數(shù)都與m互素。證明留作習題。定理2設a是整數(shù)，(a,m)=1，B={x1,x2,L,xj(m)}是模m的簡化剩余系，則集合A={ax1,ax2,L,axj(m)}也是模m的簡化剩余系。證明顯然，集合A中有j(m)個整數(shù)。其次，由于(a,m)=1，所以，對于任意的xi（1￡i￡j(m)），xi?B，有(axi,m)=(xi,m)=1。因此，A中的每一個數(shù)都與m互素。最后，我們指出，A中的任何兩個不同的整數(shù)對模m不同余。事實上，若有x￠,x￠￠?B，使得ax￠oax￠￠(modm)，初等數(shù)論第二章同余第三節(jié)簡化剩余系在模m的完全剩余系中，與m互素的
4、整數(shù)所成的集合有一些特殊的性質(zhì)，我們要在這一節(jié)中對它們做些研究。定義1設R是模m的一個剩余類，若有a?R，使得(a,m)=1，則稱R是模m的一個簡化剩余類。顯然，若R是模的簡化剩余類，則R中的每個整數(shù)都與m互素。例如，模4的簡化剩余類有兩個：R1(4)={L,-7,-3,1,5,9,L}，R3(4)={L,-5,-1,3,7,11,L}。定義2對于正整數(shù)k，令函數(shù)j(k)的值等于模k的所有簡化剩余類的個數(shù)，稱j(k)為Euler函數(shù)，或Euler—j函數(shù)。例如，容易驗證j(2)=1，j(3)=2，j(4)=2，j(7)=6。顯然，j(m)就是在m的一
5、個完全剩余系中與m互素的整數(shù)的個數(shù)。定義3對于正整數(shù)m，從模m的每個簡化剩余類中各取一個數(shù)xi，構成一個集合{x1,x2,L,xj(m)}，稱為模m的一個簡化剩余系（或簡稱為簡化系）。顯然，由于選取方式的任意性，模m的簡化剩余系有無窮多個。例如，集合{9,-5,-3,-1}是模8的簡化剩余系，集合{1,3,5,7}也是模8的簡化剩余系，通常稱最小非負簡化剩余系。定理1整數(shù)集合A是模m的簡化剩余系的充要條件是(ⅰ)A中含有j(m)個整數(shù)；(ⅱ)A中的任何兩個整數(shù)對模m不同余；(ⅲ)A中的每個整數(shù)都與m互素。證明留作習題。定理2設a是整數(shù)，(a,m)=1
6、，B={x1,x2,L,xj(m)}是模m的簡化剩余系，則集合A={ax1,ax2,L,axj(m)}也是模m的簡化剩余系。證明顯然，集合A中有j(m)個整數(shù)。其次，由于(a,m)=1，所以，對于任意的xi（1￡i￡j(m)），xi?B，有(axi,m)=(xi,m)=1。因此，A中的每一個數(shù)都與m互素。最后，我們指出，A中的任何兩個不同的整數(shù)對模m不同余。事實上，若有x￠,x￠￠?B，使得ax￠oax￠￠(modm)，那么，因為(a,m)=1，所以x￠ox￠￠(modm)，于是x￠=x￠￠。由以上結(jié)論及定理1可知集合A是模m的一個簡化系。證畢。注：
7、在定理2的條件下，若b是整數(shù)，集合{ax1+b,ax2+b,,L,axj(m)+b}不一定是模m的簡化剩余系。例如，取m=4，a=1，b=1，以及模4的簡化剩余系{1,3}。定理3設m1,m2?N，(m1,m2)=1，又設分別是模m1與m2的簡化剩余系，則A={m1y+m2x；x?X，y?Y}是模m1m2的簡化剩余系。證明由第二節(jié)定理3推論可知，若以X￠與Y￠分別表示模m1與m2的完全剩余系，使得XìX￠，YìY￠，則A￠={m1y+m2x；x?X￠，y?Y￠}是模m1m2的完全剩余系。因此只需證明A￠中所有與m1m2互素的整數(shù)的集合R是集合A。顯然
8、，AíA’。若m1y+m2x?R，則(m1y+m2x,m1m2)=1，所以(m1y+m2x,m1)=1，于是
