唯一分解定理简要教程

20 Dec 2021

摆一摆唯一分解定理，并给出一些习题。（不定期更新！）

唯一分解定理

所有正整数 $n$ 都能被分解为若干个质数的整数幂次之积。

\[\forall n \in \mathbb{Z^+} : n = \prod_{i=1}^{k}p_i^{a_i}, p_i \in \mathbb{P}, a_i \in \mathbb{Z^+}.\]

推论

$n$ 的正因数个数为

\[\sigma = \prod_{i=1}^{k}\left( a_i+1 \right).\]

$n$ 的全体正因数之和为

\[\prod_{i=1}^{k}\left( \sum_{j=0}^{a_i}p_i^j \right).\]

习题

奇因数

题目大意：判断一个数的全体因数中有么有奇数。

思路：如果 $n$ 没有奇因数，则 $n$ 只有 $2$ 这个因数，即

\[n = \prod_{i=1}^{k}p_i^{a_i} = 2^{a_1}\]

所以如果能找到 $x \in \mathbb{Z}$ 使 $n=2^x$，那么 $n$ 就没有奇因数。

事实上，只要判断

\[n=2^{\lfloor \log_2 n \rfloor}\]

是否成立。

三除数

题目大意：判断一个数是否刚好有 $3$ 个因数。

思路：因为 $\sigma=3$，而 $3 \in \mathbb{P}$，所以 $\sigma$ 最多分解为 $k=1$ 个乘积，即

\[\sigma = \prod_{i=1}^{k}\left( a_i+1 \right) = a_1+1 = 3\]

解得 $a_1=2$，所以 $n=p_1^2$，不难得到 $\sqrt{n} \in \mathbb{P}$.

所以只要判断 $\sqrt{n} \in \mathbb{P}$ 是否成立。