完全剩餘系

一、完全剩餘系的概念

在模m的整數集合{0,1,2,…,m-1}中，如果集合S = {a1,a2,…,an}滿足以下兩個條件，則S為模m的完全剩餘系：

1. S中的每個元素都是模m的剩餘類；

2. S中的元素兩兩不同餘，即ai≠aj (i≠j)。

簡單地說，如果取模後得到的餘數均不相同，而且包含了所有的可能剩餘類，則這些餘數構成了模m的完全剩餘系。

二、簡述模m的完全剩餘系特徵

模m的完全剩餘系共有m個元素，每個數都是模m的剩餘類。

模m的完全剩餘系的元素之間兩兩不同餘，從而形成一個無序的、呈現散列分布的集合。

通過完全剩餘系，在模m的剩餘類中相當於僅保留了一個最小非負剩餘，即將每個剩餘系中最小的元素代表這個剩餘系。

三、剩餘系和完全剩餘系概念

剩餘系是指在模m的整數集合{0,1,2,…,m-1}中，任意取另一個整數a，將模m下的所有a的倍數歸到同一類中，則這些類所組成的集合就是模m下的一個剩餘系。

而完全剩餘系是指模m的一個剩餘系中不重不漏地包含了所有的模m下的剩餘類。

四、完全剩餘系怎麼計算

計算模m的完全剩餘系，需要從模0開始，依次枚舉模m的每個非負整數k，然後判斷k是否是模m的剩餘系中的元素。

def get_full_residue_system(m):
    s = set()
    for i in range(m):
        s.add(i%m)
    return s

五、完全剩餘系的加法表

模m的完全剩餘系中的任意兩個元素相加，其和仍然屬於模m的完全剩餘系。

m = 7
s = get_full_residue_system(m)
add_table = [[(i+j)%m for j in s] for i in s]
print(add_table)

六、模7完全剩餘系怎麼求

模7的剩餘類共有7種，分別是{0,1,2,3,4,5,6}。其完全剩餘係為{0,1,2,3,4,5,6}。

m = 7
s = get_full_residue_system(m)
print(s)

七、完全剩餘系的定義

完全剩餘系是指模m的一個剩餘系中不重不漏地包含了所有的模m下的剩餘類。

特別地，在模質數p下，完全剩餘系可以通過對1~p-1進行約旦定理的運算來得到。

def jordan_totient(n):
    res = 1
    for i in range(2, n):
        if n % i == 0:
            res *= i-1
            n //= i
            while n % i == 0:
                res *= i
                n //= i
    if n > 1:
        res *= n-1
    return res


def get_full_residue_system_prime(p):
    s = set()
    for i in range(1, p):
        if math.gcd(i, p) == 1:
            s.add(i)
    return s


p = 7
s = get_full_residue_system_prime(p)
print(s)

八、完全剩餘系和簡化剩餘系

在模m的剩餘系中，完全剩餘系和簡化剩餘系都是對剩餘系的一個劃分。兩者不同之處在於，簡化剩餘系只包含了剩餘系中的一個最小非負剩餘，而完全剩餘系包含了剩餘系中的所有剩餘類。

舉個例子，模7的剩餘系包含的元素為{0,1,2,3,4,5,6}，則從剩餘系中選取一個最小非負剩餘，有以下可能：

1. 取0: 此時簡化剩餘係為{0}，完全剩餘係為{0,1,2,3,4,5,6}；

2. 取1: 此時簡化剩餘係為{1}，完全剩餘係為{1,2,3,4,5,6,0}；

3. 取2: 此時簡化剩餘係為{2}，完全剩餘係為{2,3,4,5,6,0,1}；

4. 取3: 此時簡化剩餘係為{3}，完全剩餘係為{3,4,5,6,0,1,2}；

5. 取4: 此時簡化剩餘係為{4}，完全剩餘係為{4,5,6,0,1,2,3}；

6. 取5: 此時簡化剩餘係為{5}，完全剩餘係為{5,6,0,1,2,3,4}；

7. 取6: 此時簡化剩餘係為{6}，完全剩餘係為{6,0,1,2,3,4,5}。