簡化剩餘系

簡化剩餘系(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的每個互素剩餘類C_r(0≤r≤m-1，(r，m)=1)中任取一數a_r，則所有的數a_r(0≤r≤m-1，(r，m)=1)所組成的集，稱為模m的一個簡化(互素)剩餘系。有無窮多個簡化剩餘系，其一般形式為a_r=q_rm+r，0≤r≤m-1，q_r可任意選取，q_r=0是最常用的取法，這時a_r=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.設m₁，m₂為自然數，(m₁，m₂)=1，則當x，y分別通過模m₁，m₂的簡化剩餘系時，m₂x+m₁y通過模m=m₁m₂的簡化剩餘系。

3.設m₁，m₂，…，m_k是k個兩兩互素的自然數，x₁，x₂，…，x_k分別通過模m₁，m₂，…，m_k的簡化剩餘系，則M₁x₁+M₂x₂+…+M_kx_k通過m=m₁m₂…m_k的簡化剩餘系，其中m=m_iM_i(i=1，2，…，k)。

4.若m是大於1的正整數，a為整數，(a，m)=1，x通過模m的簡化剩餘系，則。

縮同餘類的概念在近世代數中有套用，若A是模m的縮同餘類，把滿足Ax=C₁的惟一的縮同餘類x表示成A^-1，則Ax=B的惟一解可記為x=BA^-1=A^-1B(或寫成B/A)，即只有模m的縮同餘類才能作分母，於是在模m的縮同餘類之間可以定義除法運算。特別地，當m為素數p時，除了C₀之外，其他p-1個同餘類都是縮同餘類。因此，加減乘除四則運算在模p同餘類集合中都是可以進行的(當然C₀不能作分母)，這樣的集合稱為“域”，模p的p個縮同餘類構成了有限域，這為近世代數提供了有限域的實例。

簡化剩餘系的構造

簡化剩餘系的構造是對簡化剩餘系的一種刻畫，指用原根表達簡化剩餘系。若 ɡ是模m的原根，則模m的簡化剩餘系可表為：1， ɡ， ɡ²，…， ɡ^φ(m)-1。在一般情況下，正整數m不一定存在原根。

關於簡化剩餘系的構造有如下定理：

1.若m=p^α(素數p≥2)存在原根 ɡ，則模m的簡化剩餘係為： ɡº， ɡ¹， ɡ²，…， g^φ(m)-1。

2.若m=2^α，α≥3，這時m無原根，則5和3對2^α的階為2^α-2，且

及

均構成模m=2的一個簡化剩餘系。

3.若正整數m的標準分解式為， g₁， g₂，…， g_s分別為模m的原根，則對任給一組數(r_-1，r₀，r₁，…，r_s)，0≤r_-1<c_-1，0≤r₀<c₀，…，0≤r_i<c_i=(1≤i≤s)，一定存在數a，(a，m)=1，使a對的指數組為(r_-1，r₀)，對的指數為r_i，且當r_-1，r₀，r₁，r₂，…，r_s分別通過c_-1，c₀，c₁，c₂，…，c_s的完全剩餘系時，a通過模m的簡化剩餘系，反之亦然。