查看“︁标准质因数分解”︁的源代码

[[分类:整除理论]]
{{InfoBox
|name=标准分解式
|eng_name=canonical representation
|aliases=标准分解,标准质因数分解式,标准素因数分解式,standard form
}}
根据[[算术基本定理]]，[[整数]]可以被不计顺序唯一地表示为其质[[因数]]乘积。
规定好从小到大的顺序后，就称为其'''标准分解'''('''canonical representation''')。

标准分解可用于[[乘法]]、[[除法]]、[[整除]]、[[最大公因数]]、[[最小公倍数]]等。
由于快速对合数进行质因数分解，特别是对大数的分解，仍然是一个理论上没有有效方法的问题。
这虽然不适合用于计算，但适合用于推断性质。

== 定义 ==

=== 标准分解式 ===

由于不计排列顺序时唯一，通常将质因数分解中相同的因数写成幂形式，并按从小到大的顺序排列。
对任意正整数 <math>n</math> ，记

<math>
n = \prod_{i=1}^k p_i^{n_i} = p_1^{n_1} p_2^{n_2} \dots p_k^{n_k}
</math>

其中 <math>p_1 < p_2 < \dots < p_k</math> 是按顺序排列的质数， <math>n_1, n_2 ,\dots n_k</math> 是正整数，则式

<math>
p_1^{n_1} p_2^{n_2} \dots p_k^{n_k}
</math>

称为整数 <math>n</math> 的'''标准分解式'''('''canonical presentation''')，或简称'''标准分解'''，也叫'''标准质因数分解'''/'''标准素因数分解'''。

注：对正整数 1 ， <math>k=0</math> ，换句话说此时等号右侧是 1 ，本质上因为其是 0 个因数的积（空积）。

== 性质 ==

对整数 <math>a_1, a_2, \dots, a_n</math> ，记各自的标准质因数分解 <math>a_i = \prod_{s=1}^r p_s n^s = p_1^{n_{i1}} p_2^{n_{i2}} \dots p_r^{n_{ir}}</math> ，其中允许指数 <math>n_{ij}</math> 取零，则：
* 正整数的[[乘法]]是标准分解式指数对应相加： 
: <math>a_i a_j = \prod_{s=1}^r p_s^{n_{is} + n_{js}} = p_1^{n_{i1} + n_{j1}} p_2^{n_{i2} + n_{j2}} \dots p_r^{n_{ir} + n_{jr}}</math>
: <math>\prod_i a_i = \prod_i \prod_{s=1}^r p_s^{n_{is}} = \prod_{s=1}^r p_s^{\sum\limits_i n_{is}} = p_1^{\sum\limits_i n_{i1}} p_2^{\sum\limits_i n_{i2}} \dots p_r^{\sum\limits_i n_{ir}}</math>
* 正整数的[[整除关系]]是标准分解式全部指数对应小于等于。
: <math>a_i \mid a_j \Leftrightarrow \bigwedge_{s=1}^r n_{is} \leq n_{js} = n_{i1} \leq n_{j1} \land n_{i2} \leq n_{j2} \land \dots \land n_{ir} \leq n_{jr}</math>
* 正整数的[[除法]]是标准分解式指数对应相减：
: <math>a_i / a_j = \prod_{s=1}^r p_s^{n_{is} - n_{js}} = p_1^{n_{i1} - n_{j1}} p_2^{n_{i2} - n_{j2}} \dots p_r^{n_{ir} - n_{jr}}</math>
* 正整数的[[最大公因数]]是标准分解式指数对应取最小值。
: <math>\operatorname{gcd}(a_i, a_j) = \prod_{s=1}^r p_s^{\min \{n_{is}, n_{js}\}} = p_1^{\min \{n_{i1}, n_{j1}\}} p_2^{\min \{n_{i2}, n_{j2}\}} \dots p_r^{\min \{n_{ir}, n_{jr}\}}</math>
: <math>\operatorname{gcd}\limits_i \{a_i\} = \prod_{s=1}^r p_s^{\min\limits_i \{n_{is}\}} = p_1^{\min\limits_i \{n_{i1}\}} p_2^{\min\limits_i \{n_{i2}\}} \dots p_r^{\min\limits_i \{n_{ir}\}}</math>
* 正整数的[[最小公倍数]]是标准分解式指数对应取最大值。
: <math>\operatorname{lcm}(a_i, a_j) = \prod_{s=1}^r p_s^{\max \{n_{is}, n_{js}\}} = p_1^{\max \{n_{i1}, n_{j1}\}} p_2^{\max \{n_{i2}, n_{j2}\}} \dots p_r^{\max \{n_{ir}, n_{jr}\}}</math>
: <math>\operatorname{lcm}\limits_i \{a_i\} = \prod_{s=1}^r p_s^{\max\limits_i \{n_{is}\}} = p_1^{\max\limits_i \{n_{i1}\}} p_2^{\max\limits_i \{n_{i2}\}} \dots p_r^{\max\limits_i \{n_{ir}\}}</math>

数论中的[[乘性函数]]都可以通过标准质因数分解处理成基于对质数和质数的幂的函数值求积。


{{整除与质数}}