完全剩余系
| 完全剩余系 | |
|---|---|
| 术语名称 | 完全剩余系 |
| 英语名称 | complete residue system |
| 别名 | 完系 |
完全剩余系(complete residue system)，简称完系，指在某模数下从全部剩余类各取一个代表元。
定义
对正整数 [math]\displaystyle{ n }[/math] ，有恰好 [math]\displaystyle{ n }[/math] 个模 [math]\displaystyle{ n }[/math] 剩余类，从中各取一个 [math]\displaystyle{ c_i }[/math] ，则得到的一组元素 [math]\displaystyle{ c_1, c_2, \dots, c_n }[/math] 中模 [math]\displaystyle{ n }[/math] 两两不同余，称这组元素 [math]\displaystyle{ c_1, c_2, \dots, c_n }[/math] 为模 [math]\displaystyle{ n }[/math] 的一个完全剩余系(complete residue system modulo [math]\displaystyle{ n }[/math]) 。有时简称为一个完系。
| 最小非负完全剩余系 | |
|---|---|
| 术语名称 | 最小非负完全剩余系 |
| 英语名称 | least residue system |
对正整数 [math]\displaystyle{ n }[/math] ， [math]\displaystyle{ 0,1,2,\dots,n-1 }[/math] 是一个模 [math]\displaystyle{ n }[/math] 完全剩余系，称为模 [math]\displaystyle{ n }[/math] 的最小非负完全剩余系(least residue system modulo [math]\displaystyle{ n }[/math]) 。有人记作 [math]\displaystyle{ \underline{n} }[/math] 。类似地，可以定义：
- 最小正完全剩余系 [math]\displaystyle{ \{1，2，\dots, n\} }[/math] ，
- 最大非正完全剩余系 [math]\displaystyle{ \{-n+1, -n+2, \dots, 0\} }[/math] ，
- 最大负完全剩余系 [math]\displaystyle{ \{-n, -n+1, -n+2, \dots, 1\} }[/math] ，
- 绝对值最小完全剩余系，
- 对奇数为 [math]\displaystyle{ \left\{-\frac{n-1}{2}, \dots, -1, 0, 1, \dots, \frac{n-1}{2}\right\} }[/math] ，
- 对偶数可以取 [math]\displaystyle{ \left\{-\frac{n}{2}, \dots, -1, 0, 1, \dots, \frac{n}{2}-1\right\} }[/math] 或 [math]\displaystyle{ \left\{-\frac{n}{2}+1, \dots, -1, 0, 1, \dots, \frac{n}{2}\right\} }[/math] 。
性质
模 [math]\displaystyle{ n }[/math] 完全剩余系中元素个数，即模 [math]\displaystyle{ n }[/math] 剩余类个数，一定有恰好 [math]\displaystyle{ n }[/math] 个。换句话说，如果找到 [math]\displaystyle{ n }[/math] 个两两模 [math]\displaystyle{ n }[/math] 不同余，则一定构成一个模 [math]\displaystyle{ n }[/math] 的完全剩余系。
任意完全剩余系 [math]\displaystyle{ x_1,x_2,\dots,x_n }[/math] ，对应的剩余类 [math]\displaystyle{ [x_1],[x_2],\dots,[x_n] }[/math] 划分整数集。
- 对正整数 [math]\displaystyle{ m }[/math] ，整数 [math]\displaystyle{ a }[/math] 满足 [math]\displaystyle{ \operatorname{gcd}(a, m)=1 }[/math] ，整数 [math]\displaystyle{ b }[/math] 任意，则若 [math]\displaystyle{ x }[/math] 取遍模 [math]\displaystyle{ m }[/math] 的一个完全剩余系，则 [math]\displaystyle{ ax+b }[/math] 也取遍模 [math]\displaystyle{ m }[/math] 的一个完全剩余系。
- 对正整数 [math]\displaystyle{ m_1, m_2 }[/math] ，若 [math]\displaystyle{ x }[/math] 取遍模 [math]\displaystyle{ m_1 }[/math] 的一个完全剩余系，且 [math]\displaystyle{ y }[/math] 取遍模 [math]\displaystyle{ m_2 }[/math] 的一个完全剩余系，则 [math]\displaystyle{ x + m_1 y }[/math] 取遍模 [math]\displaystyle{ m_1 m_2 }[/math] 的一个完全剩余系。
- 一般地，对正整数 [math]\displaystyle{ m_1, m_2, \dots, m_n }[/math] ，若 [math]\displaystyle{ x_1 }[/math] 取遍模 [math]\displaystyle{ m_1 }[/math] 的一个完全剩余系， [math]\displaystyle{ x_2 }[/math] 取遍模 [math]\displaystyle{ m_2 }[/math] 的一个完全剩余系，……， [math]\displaystyle{ x_n }[/math] 取遍模 [math]\displaystyle{ m_n }[/math] 的一个完全剩余系，则 [math]\displaystyle{ 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]\displaystyle{ m_1 m_2 \dots m_n }[/math] 的一个完全剩余系。
- 这可以看做某种混合进制的后 [math]\displaystyle{ n }[/math] 位。
- 特别地，如果取 [math]\displaystyle{ m_1=m_2=\dots=m_n=k }[/math] 就是 [math]\displaystyle{ k }[/math] 进制的后 [math]\displaystyle{ n }[/math] 位。
- 一般地，对正整数 [math]\displaystyle{ m_1, m_2, \dots, m_n }[/math] ，若 [math]\displaystyle{ x_1 }[/math] 取遍模 [math]\displaystyle{ m_1 }[/math] 的一个完全剩余系， [math]\displaystyle{ x_2 }[/math] 取遍模 [math]\displaystyle{ m_2 }[/math] 的一个完全剩余系，……， [math]\displaystyle{ x_n }[/math] 取遍模 [math]\displaystyle{ m_n }[/math] 的一个完全剩余系，则 [math]\displaystyle{ 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]\displaystyle{ m_1 m_2 \dots m_n }[/math] 的一个完全剩余系。
- 对正整数 [math]\displaystyle{ m_1, m_2 }[/math] ，满足 [math]\displaystyle{ \operatorname{gcd}(m_1, m_2)=1 }[/math] ，若 [math]\displaystyle{ x }[/math] 取遍模 [math]\displaystyle{ m_1 }[/math] 的一个完全剩余系，且 [math]\displaystyle{ y }[/math] 取遍模 [math]\displaystyle{ m_2 }[/math] 的一个完全剩余系，则 [math]\displaystyle{ m_2 x + m_1 y }[/math] 取遍模 [math]\displaystyle{ m_1 m_2 }[/math] 的一个完全剩余系。反过来也成立。
- 一般地，对正整数 [math]\displaystyle{ m_1, m_2, \dots, m_n }[/math] ，满足 [math]\displaystyle{ (\forall i, j)(\operatorname{gcd}(m_i, m_j)=1) }[/math] ，记 [math]\displaystyle{ M = m_1 m_2 \dots m_n }[/math] 且 [math]\displaystyle{ (\forall j) (m = m_j M_j) }[/math] ，若 [math]\displaystyle{ x_1 }[/math] 取遍模 [math]\displaystyle{ m_1 }[/math] 的一个完全剩余系， [math]\displaystyle{ x_2 }[/math] 取遍模 [math]\displaystyle{ m_2 }[/math] 的一个完全剩余系，……， [math]\displaystyle{ x_n }[/math] 取遍模 [math]\displaystyle{ m_n }[/math] 的一个完全剩余系，则 [math]\displaystyle{ M_1 x_1 + M_2 x_2 + M_3 x_3 + \dots + M_n x_n }[/math] 取遍模 [math]\displaystyle{ m_1 m_2 \dots m_n }[/math] 的一个完全剩余系。
- 进一步地，若 [math]\displaystyle{ (\forall j)(\operatorname{gcd}(a_j, m_j) = 1) }[/math] ，则 [math]\displaystyle{ 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]\displaystyle{ m_1 m_2 \dots m_n }[/math] 的一个完全剩余系。
- 对正整数 [math]\displaystyle{ m_1, m_2, \dots, m_n }[/math] ，满足 [math]\displaystyle{ (\forall i, j)(\operatorname{gcd}(m_i, m_j)=1) }[/math] ，记 [math]\displaystyle{ M = m_1 m_2 \dots m_n }[/math] 且 [math]\displaystyle{ (\forall j) (m = m_j M_j) }[/math] ，若 [math]\displaystyle{ x_1 }[/math] 取遍模 [math]\displaystyle{ m_1 }[/math] 的一个完全剩余系， [math]\displaystyle{ x_2 }[/math] 取遍模 [math]\displaystyle{ m_2 }[/math] 的一个完全剩余系，……， [math]\displaystyle{ x_n }[/math] 取遍模 [math]\displaystyle{ m_n }[/math] 的一个完全剩余系，则 [math]\displaystyle{ 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]\displaystyle{ (\forall j) (x \equiv (a_j M_j)^n x_j \pmod{m_j}) }[/math] ，则 [math]\displaystyle{ x }[/math] 取遍模 [math]\displaystyle{ m_1 m_2 \dots m_n }[/math] 的一个完全剩余系。
- 一般地，对正整数 [math]\displaystyle{ m_1, m_2, \dots, m_n }[/math] ，满足 [math]\displaystyle{ (\forall i, j)(\operatorname{gcd}(m_i, m_j)=1) }[/math] ，记 [math]\displaystyle{ M = m_1 m_2 \dots m_n }[/math] 且 [math]\displaystyle{ (\forall j) (m = m_j M_j) }[/math] ，若 [math]\displaystyle{ x_1 }[/math] 取遍模 [math]\displaystyle{ m_1 }[/math] 的一个完全剩余系， [math]\displaystyle{ x_2 }[/math] 取遍模 [math]\displaystyle{ m_2 }[/math] 的一个完全剩余系，……， [math]\displaystyle{ x_n }[/math] 取遍模 [math]\displaystyle{ m_n }[/math] 的一个完全剩余系，则 [math]\displaystyle{ M_1 x_1 + M_2 x_2 + M_3 x_3 + \dots + M_n x_n }[/math] 取遍模 [math]\displaystyle{ m_1 m_2 \dots m_n }[/math] 的一个完全剩余系。