标准质因数分解

来自GSXAB的知识库
（重定向自标准质因子分解）
标准分解式
术语名称 标准分解式
英语名称 canonical representation
别名 标准分解, 标准质因数分解式, 标准素因数分解式, standard form

根据算术基本定理，整数可以被不计顺序唯一地表示为其质因数乘积。 规定好从小到大的顺序后，就称为其标准分解(canonical representation)。

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

定义

标准分解式

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

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

其中 [math]\displaystyle{ p_1 \lt p_2 \lt \dots \lt p_k }[/math] 是按顺序排列的质数， [math]\displaystyle{ n_1, n_2 ,\dots n_k }[/math] 是正整数，则式

[math]\displaystyle{ p_1^{n_1} p_2^{n_2} \dots p_k^{n_k} }[/math]

称为整数 [math]\displaystyle{ n }[/math] 的标准分解式(canonical presentation)，或简称标准分解，也叫标准质因数分解/标准素因数分解。

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

性质

对整数 [math]\displaystyle{ a_1, a_2, \dots, a_n }[/math] ，记各自的标准质因数分解 [math]\displaystyle{ 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]\displaystyle{ n_{ij} }[/math] 取零，则：

  • 正整数的乘法是标准分解式指数对应相加：
[math]\displaystyle{ 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]\displaystyle{ \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]\displaystyle{ 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]\displaystyle{ 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]\displaystyle{ \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]\displaystyle{ \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]\displaystyle{ \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]\displaystyle{ \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]

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


整除理论
整除关系 整除、倍数、因数 带余除法
正整数的分类 1、质数、合数
质数测试 试除法、埃氏筛、线性筛
最大公约数理论 公倍数、最小公倍数 [math]\displaystyle{ \operatorname{lcm} }[/math]、公因数、最大公因数 [math]\displaystyle{ \operatorname{gcd} }[/math] 辗转相除法
互质
算术基本定理 算术基本定理 标准质因数分解
检索自“https://knowledge.gsxab.top/index.php?title=标准质因数分解&oldid=2210”