一、质数与合数

1. 质数与合数的定义与充要条件

• **【质数和合数的定义】**对于整数 $p \in \Z$ 且 $p > 1$：若 ${\rm Div}_+ \, p = \{ 1, p \}$，那么称 $p$ 为质数（素数）；否则称 $p$ 为合数。

  • 负数，零和一既不是质数也不是合数。

• **【合数的充要条件】**对于整数 $p \in \Z$ 且 $p > 1$：$p$ 是合数当且仅当存在整数 $p_1, p_2 \in (1, p) \cap \Z$ 使得 $p = p_1 p_2$。

  证：

  • $\Leftarrow$：说明 $p_1, p_2 \mid p$，因而 $p_1, p_2 \in {\rm Div}_+ \, p$。显然 $p_1, p_2 \notin \{ 1, p \}$，因而 $p$ 为合数。
  • $\Rightarrow$：因为 $p> 1$，根据恒成立式 $1 \mid p$ 和 $p \mid p$ 我们知道 $1, p \in {\rm Div}+ \, p$ 一定成立，又 $p \neq 1$ 故 $\{ 1, p \} \subseteq {\rm Div}+ \, p$ 恒成立。当 $p$ 为合数，这说明还存在某个数同时满足 $p_1 > 0$、$p_1 \neq 1$ 和 $p_1 \neq p$ 还使得 $p_1 \mid p$。此整除关系有 $p_1 \le |p| = p$，整合各不等式得到 $p_1 \in (1, p) \cap \Z$。此整除关系还导出存在 $p_2 \in \Z$ 使得 $p = p_1p_2$ 。可知 $p_2 > 0$（否则导出 $p\le 0$ 发生矛盾），$p_2 \neq 1$（否则导出 $p_1=p$ 发生矛盾），$p_2 < p$（否则导出 $p_1p_2 \ge p_1p$ 即 $p \ge p_1p$ 即 $p_1 \le 1$ 发生矛盾）。因而 $p_2 \in (1, p) \cap \Z$。

2. 质数筛

• **【埃拉托色尼质数筛法】**作为拓展阅读，通过这样的算法能找到任意指定 $N$ 以内的所有质数。

3. 质数与合数相关的定理

• **【最小的非 1 正因数定理】**设 $a \in \Z$ 且 $a > 1$，那么 $a$ 的最小的非 1 正因数 $p$ 一定是质数，并且当 $a$ 为合数时，有 $p \le \sqrt a \Leftrightarrow p^2 \le a$。

  证：

  • 先证明 $p$ 一定是质数。反证法，如果是合数，那么存在整数 $p_1, p_2 \in (1, p) \cap \Z$ 使得 $p = p_1 p_2$，因为 $p \mid a$，存在 $q \in \Z$ 使得 $a = pq = p_1p_2q$，因而 $p_1, p_2$ 都是比 $p$ 更小的非 1 正因数，与题设矛盾。
  • 其次证明当 $a$ 为合数时，一定有 $p \le \sqrt a$。由于 $p \mid a$，存在 $q \in \Z$ 使得 $a = pq$。
    • 可以证明 $q \ge 0$（否则导出 $a < 0$ 发生矛盾）和 $q \neq 1$（否则导出 $a = p$，有 $a$ 是一个质数，发生矛盾），因而说 $q > 1$。
    • 根据 $a = pq$，可见 $q$ 也是 $a$ 的一个非 1 正因数。根据 $p$ 是 $a$ 的最小的非 1 正因数，有 $p \le q$。得到 $p^2 \le pq = a$，因而 $p^2 \le a$ 即 $p \le \sqrt a$。

• **【质数与整除的关系】**设 $a \in \Z$，$p$ 是一个质数，那么下面两个条件有且仅有一个成立：① $p \mid a$；② $p \perp a$。

  证：

  • 因为 $p$ 是质数，有 ${\rm Div}+ \, p = \{ 1, p \}$，因而 ${\rm CD}+(p, a) = {\rm Div}+ \, p \cap {\rm Div}+ \, a \subseteq \{ 1, p \}$，因而 ${\rm GCD}(p, a)$ 存在且只有可能是 $1$ 或者 $p$。
    • 当 ${\rm GCD}(p, a) = 1$，那么 $p \perp a$。
    • 当 ${\rm GCD}(p, a) = p$，那么 $p \mid a$。
  • 因为 $p \neq 1$，不可能同时有 ${\rm GCD}(p, a) = 1 = p$，因而两个条件有且仅有一个成立。

• **【引理：两个质数间的关系】**设 $p, q$ 是质数，那么下面两个条件有且仅有一个成立：① $p =q$；② $p \perp q$。

  证：

  1. 当 $p=q$，有 $p \mid q$，故 ${\rm GCD} (p, q) = |p| = p >1$ 故 ② 不成立。
  2. 当 $p \neq q$，反证法，设 $p \not\perp q$，根据上述定理有 $p \mid q$，即 $p > 1$ 且 $p \neq q$ 且 $p \in {\rm Div} \, q$，根据合数定义说明 $q$ 是合数，与 $q$ 是质数矛盾，故 ② 成立。

• **【引理（用来证算术基本定理）】**如果 $a_1, a_2, \cdots, a_n \in \Z$，还有一个质数 $p$，如果 $p \mid (a_1a_2 \cdots a_n)$，那么 $\exists \, i \in [1, n] \cap \Z$ 使得 $p \mid a_i$ 。

  **证：**反证法。假设 $\forall \, i \in [1, n] \cap \Z$ 都有 $p \nmid a_i$，那么 $\forall i, \, p \perp a_i$。根据互质与整除的关系，可以陆续推出：$p \perp a_1$，$p \perp a_1a_2$，…，$p \perp a_1a_2 \cdots a_n$。因而 $p \nmid a_1a_2 \cdots a_n$ 与题设条件矛盾。

二、算术基本定理与相对质因分解式

1. 算术基本定理与相对质因分解式

• **【算术基本定理】**任何大于一的整数都能唯一地表示为若干个质数的乘积。具体而言：

  1. 对于 $a \in \Z$、$a > 1$，存在有限个质数 $\{ p_i \}{i=1}^n$（$n \ge 1$），使得 $a = \prod{i=1}^{n} p_i$。
  2. 对于 $a \in \Z$、$a > 1$，如果存在 $\{ p_i \}{i=1}^n$（$p_1 \le p_2 \le \cdots \le p_n$）和 $\{ q_j \}{j=1}^m$（$q_1 \le q_2 \le \cdots \le q_m$）使得 $a = \prod_{i=1}^{n} p_i = \prod_{j=1}^{m} q_j$，那么有：① $n=m$；② $\forall i \in [1, n], \, p_i = q_i$。

  证：

  1. （存在性）使用第二类数学归纳法。
     • 当 $a = 2$ 时存在质数 $p_1 = 2$ 使得 $a = p_1$，因而原命题对 $a=2$ 时成立。
     • 假设原命题对 $2\le a \le b$ 都成立，那么在 $a = b+1$ 时：
       1. 如果 $a$ 是质数，那么存在质数 $p_1 = a$ 使得 $a = p_1$，原命题成立；
       2. 如果 $a$ 是合数，那么存在整数 $k, l \in (1, a) \cap \Z$ 使得 $a = k l$。而 $k$ 和 $l$ 都能表示为若干个（至少一个）质数的乘积，因而 $a$ 也可以分解为至少两个质数的乘积，而且只要 $a$ 是有限的，这些质数的数目就是有限的。
  2. （唯一性）
     • 不妨设 $n \ge m$，那么有 $p_1p_2 \cdots p_n = q_1 q_2 \cdots a_m$，可知 $q_1 \mid p_1 p_2 \cdots p_n$。那么根据上面的引理，$\exists i$ 使得 $q_1 \mid p_i$。又 $p_{i}$ 是质数，有 $q_1 \in {\rm Div}+ \, p{i} = \{ 1, p_{i} \}$，可推出 $q_1 = p_{i}$（因为 $q_1$ 也是质数，不可能有 $q_1 = 1$）。同理 $\exists j$ 使得 $p_1 = q_j$。有：$p_1=q_{j}$、$q_1 = p_{i}$，因为排好序的关系还有 $p_1 \le p_{i}$ 和 $q_1 \le q_{j}$，因而有 $q_{j} \le p_{i}$ 和 $p_{i} \le q_{j}$ 即 $p_{i} = q_{j}$ 即 $p_1 = q_1$。
     • 得到 $p_2 p_3 \cdots p_n = q_2 q_3 \cdots q_m$，可进行同样的推理得到 $p_2 = q_2$，得到 $p_3 p_4 \cdots p_n = q_3 q_4 \cdots q_m$ 进行同样的推理得到 $p_3 = q_3$……
       • 这里能反证 $n=m$。如果 $n \neq m$ 即 $n > m$，推到某步会存在 $p_{i}p_{i+1} \cdots p_n = 1$，与 $p_i, p_{i+1}, \cdots, p_n > 1$ 矛盾。
       • 既然 $n=m$，推理 $n$ 步就得到 $\forall i \in [1, n], \, p_i = q_i$。

• **【相对质因分解式】**对于 $a \in \Z$、$a > 1$，能唯一地写为一组互不相同的质数的组合：

  $$ a = \prod_{i=1}^n p_i^{\alpha_i} $$

  • 这里 $n \ge 1$，$p_1<p_2<\cdots < p_n$ 都是质数，$\alpha_i > 0$ 为对应质数的数目。

2. 从相对质因分解式看因数和倍数

• **【质因数的充要条件】**对于非一正整数 $a$，相对质因分解式记为 $a = \prod_{i=1}^n p_i^{\alpha_i}$（$\alpha_i > 0$），对于任意质数 $p$，$p \mid a$ $\Leftrightarrow$ $p \in \{ p_1, p_2, \cdots, p_n \}$。

  证：

  • $\Leftarrow$：存在 $k \in [1, n] \cap \Z$ 使得 $p = p_k$。根据 $a = \prod_{i=1}^n p_i^{\alpha_i}$，易得 $p_k \mid a$ 即 $p\mid a$。
  • $\Rightarrow$：根据 $a = \prod_{i=1}^n p_i^{\alpha_i}$ 又 $p \mid a$ 得到 $p \mid \left( \prod_{i=1}^n p_i^{\alpha_i} \right)$，根据上面用来证算术基本定理的引理，可以知道存在 $k \in [1, n] \cap \Z$ 使得 $p \mid p_k$，因而 ${\rm GCD}(p, p_k) = p \neq 1$，故 $p \not\perp p_k$。又 $p$ 和 $p_k$ 都是质数，根据两个质数间的关系，$p = p_k$，因而说 $p \in \{ p_1, p_2, \cdots, p_n \}$。

• **【相对质因分解式与因数的关系】**对于非一正整数 $a$，相对质因分解式记为 $a = \prod_{i=1}^n p_i^{\alpha_i}$（$\alpha_i > 0$），还有一个非一正整数 $d$，$d \in {\rm Div}+ \, a$ 当且仅当 $d$ 可以表示为 $d = \prod{i=1}^n p_i^{\beta_i}$（$\forall i, \, \beta_i \in \Z, \, 0 \le \beta_i \le \alpha_i$）。

  • 也就是 ${\rm Div}+ \, a = \left\{ \prod{i=1}^n p_i^{\beta_i} \, \left| \, \forall i, \, \beta_i \in \Z, \, 0 \le \beta_i \le \alpha_i \right.\right\}$。

  证：

  • $\Rightarrow$：
    • 暂且记录相对质因分解式 $d = \prod_{j=1}^m q_j^{\phi_j}$（$\phi_i > 0$），因为 $d \mid a$ 也就是 $(\prod_{j=1}^m q_j^{\phi_j}) \mid a$，根据因数可拆的性质有 $\forall j, \, q_j \mid a$，根据质因数的充要条件知道 $\forall j, \, q_j \in \{ p_1, p_2, \cdots, p_n \}$，即 $\{ q_1, q_2, \cdots, q_m \} \subseteq \{ p_1, p_2, \cdots, p_n \}$。
    • 因而可以写作 $d = \prod_{i=1}^n p_i^{\beta_i}$（对于所有 $i \in [1, n] \cap \Z$，如果 $p_i \notin \{ q_1, q_2, \cdots, q_m \}$ 取 $\beta_i = 0$，否则存在 $j$ 使得 $p_i = q_j$ 取 $\beta_i = \phi_j$）。下面证明对各 $i$ 都有 $\beta_i \le \alpha_i$。由于 $d \mid a$，我们知道 $\exists \, q \in \Z$，$a = qd$。根据 $a, d > 0$ 知道 $q > 0$，分类讨论 $q$ 的大小：
      • 如果 $q = 1$，这时 $a=d$ 根据质因分解式唯一性知道 $\forall i, \, \beta_i = \alpha_i$ 成立。
      • 如果 $q > 1$，这时可以和上面一样，暂且记录分解式，再根据 $q \mid a$，得到也有这样的分解式成立：$q = \prod_{i=1}^n p_i^{\lambda_i}$（同理有 $\lambda_i \ge 0$）。这时 $a = qd$ 写作：$\prod_{i=1}^n p_i^{\alpha_i} = \left ( \prod_{i=1}^n p_i^{\beta_i} \right ) \left ( \prod_{i=1}^n p_i^{\lambda_i} \right ) = \prod_{i=1}^n p_i^{\beta_i + \lambda_i}$，因而 $\forall i$ 有 $\alpha_i = \beta_i + \lambda_i$，又因 $\lambda_i \ge 0$ 得 $\beta_i = \alpha_i - \lambda_i \le \alpha_i$ 成立。
  • $\Leftarrow$：根据 $a$ 与 $d$ 的形式，马上得到 $a = qd$，$q = \prod_{i=1}^n p_i^{\alpha_i - \beta_i}$，因而 $d \mid a$ 成立。

• **【推论】**对于非一正整数 $a$，相对质因分解式记为 $a = \prod_{i=1}^n p_i^{\alpha_i}$（$\alpha_i > 0$），对于任意 $i$ 和任意幂指数 $k \ge 0$，有：$p_i^k \mid a$ $\Leftrightarrow$ $k \le \alpha_i$。

  证：

  • 如果 $k = 0$，$1 \mid a$ 和 $0 \le \alpha_i$ 都是永真式。
  • 如果 $k > 0$，那么 $p_i^k \ge p_i > 1$，我们知道 $p_i^k$ 的分解式就是它自身，那么根据上面定理可以知道 $p_i^k \mid a$ $\Leftrightarrow$ $k \le \alpha_i$。

• **【互不相同的正因数数目】**对于非一正整数 $a$，相对质因分解式记为 $a = \prod_{i=1}^n p_i^{\alpha_i}$（$\alpha_i > 0$），则 $a$ 的互不相同的正因数的个数有且仅有 $\prod_{i=1}^n(\alpha_i + 1)$ 个。

  说明：

  • 根据计数原理可以知道。首先第一步从 $\alpha_1$ 个 $p_1$ 中可以挑选 $0, 1, \cdots, \alpha_i$ 个 $p_i$，一共 $(\alpha_1 + 1)$ 种可能，下一步是挑选 $p_2$……得到总的数目。