查看“︁完全剩余系”︁的源代码

[[分类:同余理论]]
{{InfoBox
|name=完全剩余系
|eng_name=complete residue system
|aliases=完系
}}
'''完全剩余系'''('''complete residue system''')，简称'''完系'''，指在某模数下从全部[[剩余类]]各取一个代表元。

== 定义 ==

对正整数 <math>n</math> ，有恰好 <math>n</math> 个模 <math>n</math> 剩余类，从中各取一个 <math>c_i</math> ，则得到的一组元素 <math>c_1, c_2, \dots, c_n</math> 中模 <math>n</math> 两两不同余，称这组元素 <math>c_1, c_2, \dots, c_n</math> 为'''模 <math>n</math> 的'''一个'''完全剩余系'''('''complete residue system modulo <math>n</math>''') 。有时简称为一个'''完系'''。

{{InfoBox
|name=最小非负完全剩余系
|eng_name=least residue system
}}
对正整数 <math>n</math> ， <math>0,1,2,\dots,n-1</math> 是一个模 <math>n</math> 完全剩余系，称为'''模 <math>n</math>''' 的'''最小非负完全剩余系'''('''least residue system modulo <math>n</math>''') 。有人记作 <math>\underline{n}</math> 。类似地，可以定义：
* '''最小正完全剩余系''' <math>\{1，2，\dots, n\}</math> ，
* '''最大非正完全剩余系''' <math>\{-n+1, -n+2, \dots, 0\}</math> ，
* '''最大负完全剩余系''' <math>\{-n, -n+1, -n+2, \dots, 1\}</math> ，
* '''绝对值最小完全剩余系'''，
** 对奇数为 <math>\left\{-\frac{n-1}{2}, \dots, -1, 0, 1, \dots, \frac{n-1}{2}\right\}</math> ，
** 对偶数可以取 <math>\left\{-\frac{n}{2}, \dots, -1, 0, 1, \dots, \frac{n}{2}-1\right\}</math> 或 <math>\left\{-\frac{n}{2}+1, \dots, -1, 0, 1, \dots, \frac{n}{2}\right\}</math> 。

== 性质 ==

模 <math>n</math> 完全剩余系中元素个数，即模 <math>n</math> 剩余类个数，一定有恰好 <math>n</math> 个。换句话说，如果找到 <math>n</math> 个两两模 <math>n</math> 不同余，则一定构成一个模 <math>n</math> 的完全剩余系。

任意完全剩余系 <math>x_1,x_2,\dots,x_n</math> ，对应的剩余类 <math>[x_1],[x_2],\dots,[x_n]</math> [[划分]]整数集。

* 对正整数 <math>m</math> ，整数 <math>a</math> 满足 <math>\operatorname{gcd}(a, m)=1</math> ，整数 <math>b</math> 任意，则若 <math>x</math> 取遍模 <math>m</math> 的一个完全剩余系，则 <math>ax+b</math> 也取遍模 <math>m</math> 的一个完全剩余系。

* 对正整数 <math>m_1, m_2</math> ，若 <math>x</math> 取遍模 <math>m_1</math> 的一个完全剩余系，且 <math>y</math> 取遍模 <math>m_2</math> 的一个完全剩余系，则 <math>x + m_1 y</math> 取遍模 <math>m_1 m_2</math> 的一个完全剩余系。
** 一般地，对正整数 <math>m_1, m_2, \dots, m_n</math> ，若 <math>x_1</math> 取遍模 <math>m_1</math> 的一个完全剩余系， <math>x_2</math> 取遍模 <math>m_2</math> 的一个完全剩余系，……， <math>x_n</math> 取遍模 <math>m_n</math> 的一个完全剩余系，则 <math>x_1 + m_1 x_2 + m_1 m_2 x_3 + \dots + m_1 m_2 \dots m_{n-1} x_n</math> 取遍模 <math>m_1 m_2 \dots m_n</math> 的一个完全剩余系。
*** 这可以看做某种混合进制的后 <math>n</math> 位。
*** 特别地，如果取 <math>m_1=m_2=\dots=m_n=k</math> 就是 <math>k</math> 进制的后 <math>n</math> 位。

* 对正整数 <math>m_1, m_2</math> ，满足 <math>\operatorname{gcd}(m_1, m_2)=1</math> ，若 <math>x</math> 取遍模 <math>m_1</math> 的一个完全剩余系，且 <math>y</math> 取遍模 <math>m_2</math> 的一个完全剩余系，则 <math>m_2 x + m_1 y</math> 取遍模 <math>m_1 m_2</math> 的一个完全剩余系。反过来也成立。
** 一般地，对正整数 <math>m_1, m_2, \dots, m_n</math> ，满足 <math>(\forall i, j)(\operatorname{gcd}(m_i, m_j)=1)</math> ，记 <math>M = m_1 m_2 \dots m_n</math> 且 <math>(\forall j) (m = m_j M_j)</math> ，若 <math>x_1</math> 取遍模 <math>m_1</math> 的一个完全剩余系， <math>x_2</math> 取遍模 <math>m_2</math> 的一个完全剩余系，……， <math>x_n</math> 取遍模 <math>m_n</math> 的一个完全剩余系，则 <math>M_1 x_1 + M_2 x_2 + M_3 x_3 + \dots + M_n x_n</math> 取遍模 <math>m_1 m_2 \dots m_n</math> 的一个完全剩余系。
*** 进一步地，若 <math>(\forall j)(\operatorname{gcd}(a_j, m_j) = 1)</math> ，则 <math>a_1 M_1 x_1 + a_2 M_2 x_2 + a_3 M_3 x_3 + \dots + a_n M_n m_n</math> 也取遍模 <math>m_1 m_2 \dots m_n</math> 的一个完全剩余系。
** 对正整数 <math>m_1, m_2, \dots, m_n</math> ，满足 <math>(\forall i, j)(\operatorname{gcd}(m_i, m_j)=1)</math> ，记 <math>M = m_1 m_2 \dots m_n</math> 且 <math>(\forall j) (m = m_j M_j)</math> ，若 <math>x_1</math> 取遍模 <math>m_1</math> 的一个完全剩余系， <math>x_2</math> 取遍模 <math>m_2</math> 的一个完全剩余系，……， <math>x_n</math> 取遍模 <math>m_n</math> 的一个完全剩余系，则 <math>x = (a_1 M_1 x_1 + a_2 M_2 + a_3 M_3 + \dots + a_n M_n)(a_1 M_1 + a_2 M_2 x_2 + a_3 M_3 + \dots + a_n M_n)\dots(a_1 M_1 + a_2 M_2 + a_3 M_3 + \dots + a_n M_n x_n</math> ，其中有 <math>(\forall j) (x \equiv (a_j M_j)^n x_j \pmod{m_j})</math> ，则 <math>x</math> 取遍模 <math>m_1 m_2 \dots m_n</math> 的一个完全剩余系。


{{同余理论}}