簡化剩餘系(縮系)

簡化剩餘系

縮系一般指本詞條

簡化剩餘系(reduced residue system)也稱既約剩餘系或縮系,是m的完全剩餘系中與m互素的數構成的子集,如果模m的一個剩餘類里所有數都與m互素,就把它叫做與模m互素的剩餘類。在與模m互素的全體剩餘類中,從每一個類中各任取一個數作為代表組成的集合,叫做模m的一個簡化剩餘系。例如,模5的一個簡化剩餘系是1,2,3,4,模10的一個簡化剩餘系是1,3,7,9,模18的一個簡化剩餘系是1,5,7,11,13,17。

基本介紹

  • 中文名:簡化剩餘系
  • 外文名:reduced residues system
  • 別稱:既約剩餘系,縮系
  • 所屬學科:數學
  • 所屬問題:初等數論(同餘式)
基本介紹,簡化剩餘系的性質,簡化剩餘系的構造,

基本介紹

簡化剩餘系是一種特殊的完全剩餘系,在模m的每個互素剩餘類Cr(0≤r≤m-1,(r,m)=1)中任取一數ar,則所有的數ar(0≤r≤m-1,(r,m)=1)所組成的集,稱為模m的一個簡化(互素)剩餘系。有無窮多個簡化剩餘系,其一般形式為ar=qrm+r,0≤r≤m-1,qr可任意選取,qr=0是最常用的取法,這時ar=r,(r,m)=1,0≤r≤m-1。當m=p為素數時,最重要的簡化剩餘係為:1,2,…,p-1,模m的簡化剩餘系由φ(m)個整數組成,且任意φ(m)個整數組成模m的一組簡化剩餘系的充分必要條件是這些數與m互素,並對模m兩兩不同餘。

簡化剩餘系的性質

簡化剩餘系有下列性質:
1.設m為自然數,k,l為任意整數,(k,m)=1,則當x通過m的簡化剩餘系時,kx+lm亦通過模m的一組簡化剩餘系,例如x與m-x同時通過模m的簡化剩餘系。
2.設m1,m2為自然數,(m1,m2)=1,則當x,y分別通過模m1,m2的簡化剩餘系時,m2x+m1y通過模m=m1m2的簡化剩餘系。
3.設m1,m2,…,mk是k個兩兩互素的自然數,x1,x2,…,xk分別通過模m1,m2,…,mk的簡化剩餘系,則M1x1+M2x2+…+Mkxk通過m=m1m2…mk的簡化剩餘系,其中m=miMi(i=1,2,…,k)。
4.若m是大於1的正整數,a為整數,(a,m)=1,x通過模m的簡化剩餘系,則
縮同餘類的概念在近世代數中有套用,若A是模m的縮同餘類,把滿足Ax=C1的惟一的縮同餘類x表示成A-1,則Ax=B的惟一解可記為x=BA-1=A-1B(或寫成B/A),即只有模m的縮同餘類才能作分母,於是在模m的縮同餘類之間可以定義除法運算。特別地,當m為素數p時,除了C0之外,其他p-1個同餘類都是縮同餘類。因此,加減乘除四則運算在模p同餘類集合中都是可以進行的(當然C0不能作分母),這樣的集合稱為“域”,模p的p個縮同餘類構成了有限域,這為近世代數提供了有限域的實例。

簡化剩餘系的構造

簡化剩餘系的構造是對簡化剩餘系的一種刻畫,指用原根表達簡化剩餘系。若 ɡ是模m的原根,則模m的簡化剩餘系可表為:1, ɡ, ɡ2,…, ɡφ(m)-1。在一般情況下,正整數m不一定存在原根。
關於簡化剩餘系的構造有如下定理:
1.若m=pα(素數p≥2)存在原根 ɡ,則模m的簡化剩餘係為: ɡº, ɡ1, ɡ2,…, gφ(m)-1
2.若m=2α,α≥3,這時m無原根,則5和3對2α的階為2α-2,且
均構成模m=2的一個簡化剩餘系。
3.若正整數m的標準分解式為
, g1, g2,…, gs分別為模m的原根,則對任給一組數(r-1,r0,r1,…,rs),0≤r-1<c-1,0≤r0<c0,…,0≤ri<ci=
(1≤i≤s),一定存在數a,(a,m)=1,使a對
的指數組為(r-1,r0),對
的指數為ri,且當r-1,r0,r1,r2,…,rs分別通過c-1,c0,c1,c2,…,cs的完全剩餘系時,a通過模m的簡化剩餘系,反之亦然。

相關詞條

熱門詞條

聯絡我們