简化剩余系
| 简化剩余系 | |
|---|---|
| 术语名称 | 简化剩余系 |
| 英语名称 | reduced residue system |
| 别名 | 既约剩余系, 缩系 |
简化剩余系/既约剩余系(reduced residue system)，简称缩系，指在某模数下从全部互质剩余类各取一个代表元。
定义
对正整数 [math]\displaystyle{ n }[/math] ，模 [math]\displaystyle{ n }[/math] 剩余类中，要么所有的元素都和 [math]\displaystyle{ n }[/math] 互质，要么都不互质，从这些互质的等价类中各取一个 [math]\displaystyle{ a_i }[/math] ，则得到的一组元素 [math]\displaystyle{ a_1, a_2, \dots, a_{\varphi(n)} }[/math] 中模 [math]\displaystyle{ n }[/math] 两两不同余且均与 [math]\displaystyle{ n }[/math] 互质，称为模 [math]\displaystyle{ n }[/math] 的一个简化剩余系(reduced residue system modulo [math]\displaystyle{ n }[/math]) 。有时简称为一个缩系。
性质
模 [math]\displaystyle{ n }[/math] 完全剩余系中元素个数，即与 [math]\displaystyle{ n }[/math] 互质的模 [math]\displaystyle{ n }[/math] 剩余类个数，与所有小于 [math]\displaystyle{ n }[/math] 且互质的正整数的数目相等，相当于欧拉函数 [math]\displaystyle{ \varphi(n) }[/math] 。
- 对正整数 [math]\displaystyle{ m }[/math] ，整数 [math]\displaystyle{ a }[/math] 满足 [math]\displaystyle{ \operatorname{gcd}(a, n)=1 }[/math] ，则若 [math]\displaystyle{ x }[/math] 取遍模 [math]\displaystyle{ m }[/math] 的一个简化剩余系，则 [math]\displaystyle{ ax }[/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{ 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] 的一个简化剩余系。