查看“︁简化剩余系”︁的源代码

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

== 定义 ==

对正整数 <math>n</math> ，模 <math>n</math> 剩余类中，要么所有的元素都和 <math>n</math> 互质，要么都不互质，从这些互质的等价类中各取一个 <math>a_i</math> ，则得到的一组元素 <math>a_1, a_2, \dots, a_{\varphi(n)}</math> 中模 <math>n</math> 两两不同余且均与 <math>n</math> 互质，称为'''模 <math>n</math> 的'''一个'''简化剩余系'''('''reduced residue system modulo <math>n</math>''') 。有时简称为一个'''缩系'''。

== 性质 ==

模 <math>n</math> 完全剩余系中元素个数，即与 <math>n</math> 互质的模 <math>n</math> 剩余类个数，与所有小于 <math>n</math> 且互质的正整数的数目相等，相当于[[欧拉函数]] <math>\varphi(n)</math> 。

* 对正整数 <math>m</math> ，整数 <math>a</math> 满足 <math>\operatorname{gcd}(a, n)=1</math> ，则若 <math>x</math> 取遍模 <math>m</math> 的一个简化剩余系，则 <math>ax</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>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> 的一个简化剩余系。


{{同余理论}}