剩余类与完全剩余系

剩余类

定义：

\(C_r\):形如\(qm+r\)的所有整数组成的集合
\(C_0,C_1,...,C_(m-1)\):模数\(m\)的剩余类

完全剩余系

定义：

1.从剩余类的每类中各取一个数，组成的\(m\)个数称为模数\(m\)的一组完全剩余系。
证明……是一组完全剩余系/通过完全剩余系：两两对m不同余
2.\(0,1,...,m-1\):非负最小完全剩余系（最常用）

定理：

证明均用反证法
1.\((k,m)=1\)，则完全剩余系\(a_1,...,a_m\) \(\Rightarrow\)完全剩余系\(ka_1,...,ka_m\)
2.\((m_1,m_2)=1\)，则\(m_1\)的完全剩余系\(x_1\),\(m_2\)的完全剩余系\(x_2\) \(\Rightarrow\) \(m_1m_2\)的完全剩余系\(x_1x_2\)

缩系

定义：

从与m互质的剩余类的每类中各取一个数，组成的\(\varphi(m)\)个数成为模数\(m\)的一组缩系。
证明……是一组缩系/通过缩系：
1.每个元素与m互质
2.两两对m不同余

定理：

证明均先证明每个元素与模数互质，然后用反证法证明两两不同余

1.\((k,m)=1\)，则缩系\(a_1,...,a_{\varphi(m)}\) \(\Rightarrow\)缩系\(ka_1,...,ka_{\varphi(m)}\)

应用：证明欧拉定理/费马小定理
设\(r_1,...,r_{\varphi(m)}\)为一组缩系，\((a,m)=1\),则：
由此定理，\(ar_1,...,ar_{\varphi(m)}\)也为一组缩系
把两组缩系分别相乘起来，它们模m同余，而\(r_1...r_{\varphi(m)}\)与m互质，于是就可以得到\(a^{\varphi(m)} \equiv 1 (\mod m)\)

2.\((m_1,m_2)=1\)，则\(m_1\)的缩系\(x_1\),\(m_2\)的缩系\(x_2\) \(\Rightarrow\) \(m_1m_2\)的缩系\(x_1x_2\)

此处证明两两不同余，可以先利用完全剩余系对应的定理，得出：\(任意a,存在a\equiv m_2x_1+m_1x_2(\mod m_1m_2)\)，然后只需证明\((a,m_1m_2)=1\Rightarrow (x_1,m_1)=(x_2,m_2)=1\)

应用：计算\(\varphi(n)\)
由此定理，\((m_1,m_2)=1\)时，\(\varphi(m_1m_2)=\varphi(m_1)\varphi(m_2)\)
然后把n唯一分解之后，就可以算出。