第三節(jié) 簡化剩余系

《第三節(jié) 簡化剩余系》由會員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。

1、初等數(shù)論第二章同余第三節(jié)簡化剩余系在模m的完全剩余系中，與m互素的整數(shù)所成的集合有一些特殊的性質(zhì)，我們要在這一節(jié)中對它們做些研究。定義1設(shè)R是模m的一個(gè)剩余類，若有a?R，使得(a,m)=1，則稱R是模m的一個(gè)簡化剩余類。顯然，若R是模的簡化剩余類，則R中的每個(gè)整數(shù)都與m互素。例如，模4的簡化剩余類有兩個(gè)：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的所有簡化剩余類的個(gè)數(shù)，稱j(k)為Euler函數(shù)，或Euler—j函數(shù)。例如，容易驗(yàn)證j(2)=1，j(3)=2，j(4)=2，

2、j(7)=6。顯然，j(m)就是在m的一個(gè)完全剩余系中與m互素的整數(shù)的個(gè)數(shù)。定義3對于正整數(shù)m，從模m的每個(gè)簡化剩余類中各取一個(gè)數(shù)xi，構(gòu)成一個(gè)集合{x1,x2,L,xj(m)}，稱為模m的一個(gè)簡化剩余系（或簡稱為簡化系）。顯然，由于選取方式的任意性，模m的簡化剩余系有無窮多個(gè)。例如，集合{9,-5,-3,-1}是模8的簡化剩余系，集合{1,3,5,7}也是模8的簡化剩余系，通常稱最小非負(fù)簡化剩余系。定理1整數(shù)集合A是模m的簡化剩余系的充要條件是(ⅰ)A中含有j(m)個(gè)整數(shù)；(ⅱ)A中的任何兩個(gè)整數(shù)對模m不同余；(ⅲ)A中的每個(gè)整數(shù)都與m互素。證明留作習(xí)題。定理2設(shè)a是整數(shù)，

3、(a,m)=1，B={x1,x2,L,xj(m)}是模m的簡化剩余系，則集合A={ax1,ax2,L,axj(m)}也是模m的簡化剩余系。證明顯然，集合A中有j(m)個(gè)整數(shù)。其次，由于(a,m)=1，所以，對于任意的xi（1￡i￡j(m)），xi?B，有(axi,m)=(xi,m)=1。因此，A中的每一個(gè)數(shù)都與m互素。最后，我們指出，A中的任何兩個(gè)不同的整數(shù)對模m不同余。事實(shí)上，若有x￠,x￠￠?B，使得ax￠oax￠￠(modm)，初等數(shù)論第二章同余第三節(jié)簡化剩余系在模m的完全剩余系中，與m互素的整數(shù)所成的集合有一些特殊的性質(zhì)，我們要在這一節(jié)中對它們做些研究。定義1設(shè)R是模

4、m的一個(gè)剩余類，若有a?R，使得(a,m)=1，則稱R是模m的一個(gè)簡化剩余類。顯然，若R是模的簡化剩余類，則R中的每個(gè)整數(shù)都與m互素。例如，模4的簡化剩余類有兩個(gè)：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的所有簡化剩余類的個(gè)數(shù)，稱j(k)為Euler函數(shù)，或Euler—j函數(shù)。例如，容易驗(yàn)證j(2)=1，j(3)=2，j(4)=2，j(7)=6。顯然，j(m)就是在m的一個(gè)完全剩余系中與m互素的整數(shù)的個(gè)數(shù)。定義3對于正整數(shù)m，從模m的每個(gè)簡化剩余類中各取一個(gè)數(shù)xi，構(gòu)成一個(gè)

5、集合{x1,x2,L,xj(m)}，稱為模m的一個(gè)簡化剩余系（或簡稱為簡化系）。顯然，由于選取方式的任意性，模m的簡化剩余系有無窮多個(gè)。例如，集合{9,-5,-3,-1}是模8的簡化剩余系，集合{1,3,5,7}也是模8的簡化剩余系，通常稱最小非負(fù)簡化剩余系。定理1整數(shù)集合A是模m的簡化剩余系的充要條件是(ⅰ)A中含有j(m)個(gè)整數(shù)；(ⅱ)A中的任何兩個(gè)整數(shù)對模m不同余；(ⅲ)A中的每個(gè)整數(shù)都與m互素。證明留作習(xí)題。定理2設(shè)a是整數(shù)，(a,m)=1，B={x1,x2,L,xj(m)}是模m的簡化剩余系，則集合A={ax1,ax2,L,axj(m)}也是模m的簡化剩余系。證明顯

6、然，集合A中有j(m)個(gè)整數(shù)。其次，由于(a,m)=1，所以，對于任意的xi（1￡i￡j(m)），xi?B，有(axi,m)=(xi,m)=1。因此，A中的每一個(gè)數(shù)都與m互素。最后，我們指出，A中的任何兩個(gè)不同的整數(shù)對模m不同余。事實(shí)上，若有x￠,x￠￠?B，使得ax￠oax￠￠(modm)，那么，因?yàn)?a,m)=1，所以x￠ox￠￠(modm)，于是x￠=x￠￠。由以上結(jié)論及定理1可知集合A是模m的一個(gè)簡化系。證畢。注：在定理2的條件下，若b是整數(shù)，集合{ax1+b,ax2+b,,L,axj(m)+b}不一定是模m的簡化剩余系。例如，取m=4，a=1，b=1，以及模4的簡化

7、剩余系{1,3}。定理3設(shè)m1,m2?N，(m1,m2)=1，又設(shè)分別是模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。顯然，AíA’。若m1y+m2x?R，則(m1y+m2x,m1m2)=1，所以(m1y+m2x,m1)=1，于是