整除
定义
$a, b \in Z$ 且 $b \neq 0$ ，如果存在 $q \in Z$ 使得
$$
a=q \cdot b
$$
则称 $b$ 整除 $a$ 或者 $a$ 被 $b$ 整除，记作 $b | a$ ，$b$ 称为 $a$ 的因数，$a$ 称为 $b$ 的倍数
性质：
当 $b$ 遍历整数 $a$ 的所有因数时，$-b$ 和 $\frac{a}{b}$ 也遍历 $a$ 的因数
若 $a_1, …, a_n \in Z$ 都是 $c \in Z^*$ 的倍数，则他们的整系数线性组合也是 $c$ 的倍数，即 $\forall s_1, …, s_n \in Z$ 都有 $c | a_1s_1+…+a_ns_n$
若 $p$ 是素数，且 $p|a_1a_2 \cdots a_n$ ，则 $ \exists i, 1 \le i \le n$，$p|a_i$
素数
定义
$n \in Z^* $ 且 $n \neq \pm 1$ 且 $n$ 只有因数 $\pm1、\pm n$ ，则 $n$ 称之为素数，通常情况下约定素数为正整数，记作 $p$
性质：
- 合数的大于 $1$ 的最小正因数 $p$ 必然是素数，且 $p \le \sqrt{n}$
- 等差数列 $qn+l$ 在 $(q, l)=1$ 时有无穷多个素数，Dirichlet
Eratosthenes
依次删除 $\le \sqrt{N}$ 的所有素数的倍数，可求得所有不大于给定正整数 $N$ 的素数
def eratosthenes(n):
"""use eratosthenes sieve to count all prime number"""
if n <= 1:
return 0
sifter = np.ones(n+1, dtype=np.int8)
sifter[0:2] = 0
for i in range(2, int(np.ceil(np.sqrt(n)))+1):
if sifter[i]:
for j in range(2, n // i + 1):
sifter[i * j] = 0
return sifter.sum()欧几里得除法
定义
$a, b \in Z$ ，且 $b > 0$，则 $\forall c \in Z$ 存在唯一的整数 $q, r$ 使得 $a=q \cdot b + r$，$c \le r < c+b$
其中 $q$ 称为 $a$ 被 $b$ 除所得的不完全商，$r$ 叫做 $a$ 被 $b$ 除所得的余数
- $c=0$ 时称 $r$ 为最小非负余数
- $c=1$ 时称 $r$ 为最小正余数
- $c=-b+1$ 时称 $r$ 为最大非正余数
- $c=-b$ 时称 $r$ 为最大负余数
- 若 $c$ 满足 $-\frac{b}{2} \le r < \frac{b}{2} \; or \; -\frac{b}{2} < r \le \frac{b}{2}$ 时称 $r$ 为绝对值最小余数
整数的表示
$\forall b \in Z \; and \; b > 1$ ，每个正整数 $n$ 在 $b$ 进制下的表示存在且唯一，且 $n$ 的 $b$ 进制位数 $k=[\log_bn]+1$
最大公因数
$d=(a_1,…,a_n)$ 称为最大公因数，如果：
- $d|a_1, …, d|a_n$
- 若 $e|a_1, …, e|a_n$，则 $e|d$
广义欧几里得除法
性质
- $n \le 5logb$ ，运用数学归纳法可以证明 $b$ 不小于 $fibonacci$ 的第 $n+1$ 项
Bezout 等式
定义
$a, b \in Z^+$ ，存在整数 $s, t$ 使得 $sa+tb=(a,b)$
求整数 $s, t$ 的方法
方法一：首先根据广义欧几里得除法求出 $(a,b)=r_n$，带回并依次消去 $r_{n-1}, … ,r_1$
例如：$a=1859, b=1573$ ，求 $s, t$ 使得 $s \cdot a + t \cdot b=(a,b)$
根据欧几里得除法，我们有：
$$
\begin{align}& 1859 = 1573 \times 1 + 286 \\ & 1573 = 5 \times 286 + 143 \\ & 286 = 2 \times 143\end{align}
$$
得到 $(a,b)=143$ ，带回
$$
\begin{align}143 & = 1573 - 5 \times 286 \\ & = 1573 - 5 \times (1859-1573) \\ & = -5 \times 1859 + 6 \times 1573\end{align}
$$
于是 $s=-5, t=6$
方法二：列表法
依然使用方法一的例子
| $j$ | $s_j$ | $t_j$ | $q_{j+1}$ | $r_{j+1}$ |
|---|---|---|---|---|
| -3 | 1859 | |||
| -2 | 1 | 0 | 1573 | |
| -1 | 0 | 1 | 1 | 286 |
| 0 | $-s_{-1} \times q_0 + s_{-2} = 1$ | $-t_{-1} \times q_0 + t_{-2} = 1$ | 5 | 143 |
| 1 | $-s_{0} \times q_1 + s_{-1} = -5$ | $-t_{0} \times q_1 + t_{-1} = 6$ | 2 | 0 |
我们有 $s=s_1=-5, t=t_1=6, (a, b)=r_0=143$
根据列表法求 s，t和(a,b)
def extended_euclidean(a, b):
"""use extended euclidean algorithm to calculate s, t, k, s.t. sa + tb = k = (a, b)"""
quotients = []
q, r1 = divmod(a, b)
r2 = b
quotients.append(q)
while r1 > 0:
q, r = divmod(r2, r1)
r2 = r1
r1 = r
quotients.append(q)
s: list = [1, 0]
t: list = [0, 1]
for i in range(len(quotients) - 1):
s.append(quotients[i] * -s[i + 1] + s[i])
t.append(quotients[i] * -t[i + 1] + t[i])
return s[-1], t[-1], r2性质
- 若 $a, b \in Z$ 且 $a^2 + b^2 \neq 0$，则
- $\forall m \in Z^+$ ，$(a \cdot m, b \cdot m)=(a, b) \cdot m$
- 若 $d \in Z^*$，且 $d|a, d|b$ ，则 $(\frac{a}{d}, \frac{b}{d})=\frac{(a,b)}{|d|}$
- 特别的，若取 $d=(a,b)$，则我们可以构造两个互素的整数 $\frac{a}{d}, \frac{b}{d}$
- $a, b, c \in Z, \; b \ne 0, c \ne 0$ 且 $(a, c)=1$，则有 ：
$$
(ab, c)=(b,c)
$$
- $a_i, c \in Z$ 且 $(a_i, c)=1$ 则有：
$$
(\Pi_{i=1}^{n}a_i, c)=1
$$
- $a, b \in Z^+$，则 $(2^a-1, 2^b-1)=2^{(a,b)}-1$
注：
- Bezout 等式可扩展到 $n$ 维的情况
- 求 n 个数的最大公因数相当于递归的求两个数的最大公因数
整数分解
给定正合数 $n > 1$，若 $ \exists a,b$ ，满足：
$$
n|a^2-b^2 \\ n \nmid a+b \\ n \nmid a-b
$$
则 $(n, a-b)$，$(n,a+b)$ 都是 $n$ 的真因数
算术基本定理
任意整数 $n>1$ 可以唯一的表示成
$$
n = p_1^{\alpha_1} \cdots p_n^{\alpha_s}, \quad \alpha_i > 0,p_i<p_j(i<j)
$$
注：利用算术基本定理，很多结论几乎是显而易见的
性质
- $n$ 的因数个数 $d(n)=\Pi(1+\alpha_i)$
- $n$ 的所有因数的和：
$$
\Pi(1 + p_i + \cdots p_i^{\alpha_i})=\Pi(\frac{p_i^{\alpha_i+1}-1}{p_i-1})
$$
- $a,b$ 是两个正整数，则存在整数 $a’|a, b’|b$ ，使得：
$$
a’ \cdot b’=[a,b] \qquad (a’,b’)=1
$$
素数定理
设
$$
\pi(x) = \sum_{p \le x} 1
$$
则有：
$$
\frac{\ln 2}{3}\frac{x}{\ln x} < \pi(x) < 6 \ln 2 \frac{x}{\ln x}
$$
以及
$$
\lim_{x \rightarrow \infty} \cfrac{\pi(x)}{\cfrac{x}{\ln x}} = 1
$$
