【数论】整除
C4LLM3GUA
·
2025-01-30 15:40:55
·
学习·文化课
整除
整除的定义
若 a,b \in \mathbb{Z}，如果存在 q \in \mathbb{Z}，且 a=qb，则称 b 整除 a，记作 b \mid a；反之，若不存在 q，则称 b 不整除 a，记作 b \nmid a。
整除的性质
若 a \mid b，b \mid c，则 a \mid c；
若 a \mid b 且 a \mid c，则 a \mid bx+cy；
若 2 \mid a，则 a 为偶数；反之则 a 为奇数;
若 (a,b)=1 且 a \mid bc，则 a \mid c；
若 (a,b)=1 且 a \mid c,b \mid c，则 ab \mid c；
带余除法定理
若存在 a,b \in \mathbb{Z} 且 b>0，则存在唯一的 q,r \in \mathbb{Z}，使得 a=qb+r。
其中，a 为被除数，b 为除数，q 为商，r 为余数，且 0 \le r < b。
等式两边同时除以 b 可得 \dfrac{a}{b}=q+\dfrac{r}{b}，可得 q=\dfrac{a-r}{b}=\lfloor\dfrac{a}{b}\rfloor。
由此，不难发现 \dfrac{a-(b-1)}{b}\le q \le \dfrac{a}{b}。
EG1.若 n 为正整数,令 \text{r(n)} 表示 n 除以 1,2,\cdots,n 的余数和，试证明有无穷多正整数 n 使得 \text{r(n)}=\text{r(n-1)}。
证明：对每个 k=1,2,\cdots,n，利用带余除法定理，可得：
\begin{align*}
n=q_k \cdot k+r_k \space (0 \le r_k < k)
\end{align*}
因此，q_k=\lfloor \dfrac{n}{k} \rfloor，就有 r_k=n-\lfloor \dfrac{n}{k} \rfloor \cdot k。
所以有：
\begin{equation*}
\begin{align*}
r(n)&=r_1+r_2+\cdots+r_n\\
&=\sum\limits_{k=1}^{n}r_k\\
&=\sum\limits_{k=1}^{n}(n-\lfloor \dfrac{n}{k}\rfloor\cdot k)
\end{align*}
\end{equation*}
想证有无穷多正整数 n，使得 r(n)=r(n-1)，可以考虑：
\begin{equation*}
\begin{align*}
r(n)-r(n-1)&=\sum\limits_{k=1}^{n}(n-\lfloor\dfrac{n}{k}\rfloor\cdot k)-\sum\limits_{k=1}^{n-1}(n-1-\lfloor\dfrac{n-1}{k}\rfloor\cdot k)\\
&=2n-1-\sum\limits_{k=1}^{n}(\lfloor\dfrac{n}{k}\rfloor-\lfloor\dfrac{n-1}{k}\rfloor)\cdot k
\end{align*}
\end{equation*}
不难发现，当 k \mid n 时，\lfloor \dfrac{n}{k}\rfloor-\lfloor\dfrac{n-1}{k}\rfloor=1；当 k \nmid n 时，上式值为 0。
因此，r(n)-r(n-1)=2n-1-\sum\limits_{1 \le k \le n 且 k \mid n}1\cdot k，也就是要证存在无穷多正整数 n 使得 2n-1=\sum\limits_{1 \le k \le n 且 k \mid n}k。当 n 取 2^p，其中 p \in \mathbb{N} 时，上式成立。#
公因子与最大公因子
若 b \mid a，则称 a 是 b 的倍数，b 是 a 的因子。特别地，若 b \mid a，则 \pm b \mid \pm a，并且 |b|\mid |a|。
若 a,b \in \mathbb{N^+} 且 b \mid a，则有 1 \le b \le a。
若 a,b \in \mathbb{Z} 且 d \mid a 且 d \mid b，则 d 是 a,b 的一个公因子。特别地，-d 也是 a,b 的一个公因子。
若 a,b \in \mathbb{Z} 且 a,b \neq 0,如果 d 是 a,b 的一个公因子且是最大的，则 d 是 a,b 的最大公因子，记为 d=(a,b)。
最大公因数的性质
当 a,b \in \mathbb{Z} 时：
若 a,b \neq 0 且 d \mid a 且 d \mid b，则 d \mid (a,b)。
当 (a,b)=1 时，a,b 互素。
若 (a,b)=1，则 (a,bc)=(a,c)。
若 (a,b)=1，则 (ab,c)=(a,c)(b,c)。
裴蜀定理
若 a,b \in \mathbb{Z} 且 a,b \neq 0，那么一定存在 s,t \in \mathbb{Z}，使得：
\begin{align*}
as+bt=(a,b)
\end{align*}
Euler定理的简化版本
结论：设 m 为大于 1 的正整数，令 a \in \mathbb{Z}，且 (a,m)=1，那么存在 t \in \mathbb{N^+}，使得 m \mid a^t-1,其中 1 \le t < m。
证明：令集合 P=\{a^1,a^2,\cdots,a^m\}。
因为 (a,m)=1，所以 (a^i,m)=1，其中 i=1,2,\cdots,m。
又因为 a^i 与 m 互素，所以 a^i 除以 m 的余数在 1,2,\cdots,m-1 中。利用抽屉原理，可得存在 1 \le i < j \le m，使得 a^i 与 a^j 除以 m 的余数相同。因此，有：
\begin{align*}
m \mid a^j-a^i=a^i(a^{j-i}-1)
\end{align*}
由于 (a^i,m)=1，有 m \mid a^{j-i}-1。令 t=j-i，可得 m \mid a^t-1。因为 1 \le i < j \le m，所以 1 \le t \le m-1。 #
素数与合数
素数与合数的定义
令 \tau (n) 为 n 的所有不同的正因子的个数：
当 \tau (n)=2 时，称 n 为素数；
当 \tau (n) \ge 3 时，称 n 为合数；
当 \tau (n)=1 时，则 n=1。
Euclid 定理
#### 素数的性质
- 若 $n$ 是大于 $2$ 的正整数，则 $n$ 一定有一个正因子是素数；
- 若 $p$ 为素数，$n \in \mathbb{Z}$，则 $p \mid n$ 或 $(p,n)=1$；
- 若 $p$ 为素数且 $p \mid ab$，则 $p \mid a$ 或 $p \mid b$。
#### 算数基本定理
如果 $n$ 是一个大于 $1$ 的正整数，那么 $n$ 一定可以拆分为有限个素数之积。
如果不考虑这种拆分的顺序，那么这种拆分方案就是唯一的。因此，我们令：
$$
\begin{align*}
n=p_1^{a_1} \cdot p_2^{a_2} \cdots p_t^{a_t}
\end{align*}
$$
上式为 $n$ 的标准分解式。
其中，$p_1 < p_2 < \cdots < p_t$ 为素数，$a_i$ 为大于 $1$ 的正整数， $i=1,2,\cdots,t$。
**注：**
- $p_1$ 为 $n$ 的最小素因子，$p_t$ 为 $n$ 的最大素因子；
- 引理：若 $n \in \mathbb{N^+}$，则 $n=2^a \cdot b$，其中 $2 \nmid b,b \ge 1,a \ge 0$；
- 引理：若 $n \in \mathbb{N^+}$，则 $n=a^2\cdot b$，其中 $a,b \in \mathbb{N^+}$ 且 $b$ 不能被任意一个大于 $1$ 的数的平方整除（无平方因子）。