简单数论

VelvetChords · 2025-02-09 14:36:30 · 算法·理论

整除性

定义1（整除）

如果整数 a 和 b 满足 a \neq 0，我们说 a 整除 b（记作 a \mid b），是指存在一个整数 c ，使得 b = ac 。
如果 a 整除 b，我们称 a 为 b 的因子，且称 b 为 a 的倍数。
如果 a 不整除 b，则记作 a \nmid b。

定理1（整除的传递性）

如果 a, b, c 为整数，且 a \mid b且 b \mid c，则有 a \mid c。

证明
假设 a \mid b，即存在整数 k，使得 b = ak。
又假设 b \mid c，即存在整数 m，使得 c = bm = akm。
因此 a \mid c，因为 c = a(km)，其中 km 是整数。

定理2（线性组合的整除性）

如果 a, b, m, n 为整数，且 c \mid a 且 c \mid b，则有 c \mid (ma + nb)。

证明
由假设 c \mid a和 c \mid b，存在整数 p 和 q，使得 a = cp 和 b = cq。

因此 ma + nb = m(cp) + n(cq) = c(mp + nq)

其中mp + nq是整数，所以 c \mid (ma + nb)。

定理3（带余除法定理）

如果 a和 b 是整数且 b > 0，则存在唯一的整数 q 和 r，使得 a = bq + r，且 0 \leq r < b。
在该公式中，q 称为商，r 称为余数，a 称为被除数，b 称为除数。

证明
考虑整数 a 和正整数 b，我们可以通过“除法”得到商 q 和余数 r，使得 a = bq + r。
余数 r 必须满足 0 \leq r < b。
如果 r \geq b，可以通过增加商 q的值来调整，使得余数 r 落在范围 0 \leq r < b内。
由于商和余数是唯一确定的，因此该结果唯一。

最大公因子及其性质

定义2（最大公因子）

对于不全为零的整数 a 和 b，它们的最大公因子是指能够同时整除 a 和 b的最大整数。记作 (a, b)。

定义3（互素）

设 a和 b为非零整数，如果 (a, b) = 1，则称 a 和 b互素。

注意，由于-a和 a的因子相同，所以有 (a, b) = (|a|, |b|)。

其中 |a|表示 a的绝对值。因此，我们只关注正整数对的最大公因子。

定理4（约简后的最大公因子）

如果 a, b是整数，且(a, b) = d，则有

\left(\frac{a}{d}, \frac{b}{d}\right) = 1

即 \frac{a}{d}和 \frac{b}{d}互素。

证明

由假设 (a, b) = d，则 a = dx 和 b = dy，其中 x 和 y 满足 (x, y) = 1。

因此 \left(\frac{a}{d}, \frac{b}{d}\right) = (x, y) = 1。

所以 \frac{a}{d}和 \frac{b}{d}互素。

推论1（最简分数）

如果 a, b 为整数，且 b \neq 0，则 \frac{a}{b} = \frac{p}{q}，其中 p 和 q为整数，且 (p, q) = 1，且 q \neq 0。

证明
假设 (a, b) = d，则可以表示为 a = dp 和 b = dq，其中 p 和 q 互素。
因此，分数 \frac{a}{b} = \frac{dp}{dq} = \frac{p}{q}，且(p, q) = 1，即该分数是最简分数。

定理5（线性组合的最大公因子）

设 a, b, c为整数，那么 (a + cb, b) = (a, b)。

证明
显然， a + cb 和 b 都被 a 和 b 的最大公因子整除，因为 (a, b) 是它们的最大公因子。所以，(a + cb, b) = (a, b)。

定义4（线性组合）

如果 a 和 b 是整数，那么它们的线性组合具有形式 ma + nb，其中 m 和 n 都是整数。

定理6（线性组合与最大公因子）

两个不全为零的整数 a 和 b 的最大公因子是它们的线性组合中最小的正整数。

证明
设d = (a, b)，那么 d 可以表示为 d = ma + nb，其中 m 和 n 为整数。
由于 d 是 a 和 b的最大公因子，它是所有能表示为 ma + nb 的正整数中的最小值。

定义5（多个整数的最大公因子）

令 a_1, a_2, \dots, a_n 为不全为零的整数，这些整数的公因子中最大的整数称为它们的最大公因子。
记作 (a_1, a_2, \dots, a_n)。

引理1（递归法则）

如果 a_1, A_2, \dots, A_n是不全为零的整数，则有 (A_1, A_2, \dots, A_{n-1}, A_n) = (A_1, A_2, \dots, A_{n-2}, (A_{n-1}, A_n))

证明
根据最大公因子的性质，(A_1, A_2, \dots, A_n) 由逐步计算两两最大公因子得到，因此可以通过递归的方式计算最大公因子。

扩展欧几里得算法（ExGCD）

扩展欧几里得算法（ExGCD）是一种利用递归方法求解方程 ax + by = \text{gcd}(a, b) 的方法，通常用于求解整数解 x 和 y，即通过此方法得到线性组合的具体值。

假设已知 a = 99 ， b = 78 ，我们希望找到满足 99x + 78y = 3 的整数解。可以通过扩展欧几里得算法来求解。

首先，我们利用欧几里得算法求得 \text{gcd}(99, 78) = 3 。接着，使用扩展欧几里得算法，从后往前推导出 x 和 y 的值。

以下是详细步骤：

步骤1：计算 99 与 78 的最大公因数。
99 = 78 \times 1 + 21 78 = 21 \times 3 + 15 21 = 15 \times 1 + 6 15 = 6 \times 2 + 3 6 = 3 \times 2 + 0
所以 \text{gcd}(99, 78) = 3 。
步骤2：从后往前推导解。

由于 3 = 15 - 2 \times 6 ，将 6 替换为 21 - 1 \times 15 ，得到：
3 = 15 - 2 \times (21 - 1 \times 15) = 3 \times 15 - 2 \times 21
然后继续替换 15 和 21 ：
3 = 3 \times (78 - 3 \times 21) - 2 \times 21 = 3 \times 78 - 11 \times 21
再替换 21 为 99 - 1 \times 78 ：
3 = 3 \times 78 - 11 \times (99 - 1 \times 78) = -11 \times 99 + 14 \times 78
所以，得到特解 x = -11 和 y = 14 。

ExGCD 的实现

扩展欧几里得算法的具体代码如下：

void exgcd(int a,int b,int &d,int &x,int &y)
{
    if(b==0)
    {
        d=a;
        x=1;
        y=0;
        return;
    }
    exgcd(b,a%b,d,x,y);
    int tmp=x;
    x=y;
    y=tmp-(a/b)*y;
}

该算法通过递归实现，首先递归到 b = 0 时停止，然后从后往前计算每一层的 x 和 y 值。

定理7（整数线性组合与最大公因数的关系）

若 a 和 b 是正整数，则所有 a 和 b 的线性组合构成的集合与所有 \text{gcd}(a, b) 的倍数组成的集合相同。

证明：

首先证明每个 a 和 b 的线性组合是 d = \text{gcd}(a, b) 的倍数。由于 d 是 a 和 b 的最大公因数，因此 d 可以表示为 d=ma+nb，其中 m 和 n 是整数。因此，任何形式为 ma+nb 的线性组合必然是 d 的倍数。
现在证明每个 d 的倍数也是 a 和 b 的线性组合。由于定理6，存在整数 r 和 s 使得 d=ra+sb 。对于任何整数 j ， jd=j(ra+sb)=(jr)a+(js)b ，因此 jd 是 a 和 b 的线性组合。

从而，得出结论：a 和 b 的所有线性组合与 \text{gcd}(a,b) 的所有倍数构成的集合是相同的。

推论2（互素的定义）

整数 a 和 b 互素当且仅当存在整数 m 和 n 使得：

ma + nb = 1

证明：

如果 a 和 b 互素，即 \text{gcd}(a, b) = 1 ，根据定理 6，存在整数 m 和 n 使得：
ma + nb = 1
反之，如果存在整数 m 和 n 使得 ma+nb = 1 ，则根据定理 6，得出 \text{gcd}(a, b) = 1 。

因此，得出结论：整数 a 和 b 互素当且仅当存在整数 m 和 n 使得 ma + nb = 1 。

二元一次不定方程

引理2：

如果 a、b 和 c 是正整数，且满足 \gcd(a, b) = 1 且 a \mid bc ，则 a \mid c 。

证明：
由于 \gcd(a, b) = 1 ，根据贝祖定理，存在整数 x 和 y 使得：

ax + by = 1

将等式两边同时乘以 c，得到：

acx + bcy = c

这表明 acx + bcy = c ，这是 a 和 bc 的线性组合，而因为 a \mid bc，所以 a 可以整除这个线性组合 acx + bcy，

因此：

a \mid c

由此证明了引理2。

定理8：

设 a、b 是整数，且 d = \gcd(a, b)。如果 d \nmid c，则方程 ax + by = c 没有整数解；如果 d \mid c，则存在无穷多个整数解。
此外，如果 x_0, y_0 是方程的一个特解，那么所有解可以表示为：

x = x_0 + \frac{b}{d}n, \quad y = y_0 - \frac{a}{d}n

其中 n 是整数。

证明：

如果 d \nmid c，方程 ax + by = c 没有整数解：
根据定理7，方程 ax + by 的结果是 d 的倍数。

因此，如果 d \nmid c，则方程 ax + by = c 没有整数解。
如果 d \mid c，存在整数解：
根据定理7，方程 ax + by = c 有解的充要条件是 d \mid c。

因为 d = \gcd(a, b)，根据贝祖定理，存在整数 s 和 t 使得：
as + bt = d
由于 d \mid c，存在整数 e 使得：
de = c
则有：
c = de = (as + bt)e = a(se) + b(te)
这样，x_0 = se 和 y_0 = te 是方程 ax + by = c 的一个特解。
证明无穷多个解的存在：

设 x = x_0 + \frac{b}{d}n 和 y = y_0 - \frac{a}{d}n，其中 n 是整数，来证明这些解的存在性。

(1) 证明任意一对 (x_0 + \frac{b}{d}n, y_0 - \frac{a}{d}n) 是方程的解：

代入 x = x_0 + \frac{b}{d}n 和 y = y_0 - \frac{a}{d}n 到方程 ax + by = c 中：
a\left(x_0 + \frac{b}{d}n\right) + b\left(y_0 - \frac{a}{d}n\right) = ax_0 + by_0 + \frac{ab}{d}n - \frac{ab}{d}n = ax_0 + by_0
由于 ax_0 + by_0 = c，所以：
a\left(x_0 + \frac{b}{d}n\right) + b\left(y_0 - \frac{a}{d}n\right) = c
因此，(x_0 + \frac{b}{d}n, y_0 - \frac{a}{d}n) 是方程的解。

(2) 证明方程的任意解都可以表示为 (x_0 + \frac{b}{d}n, y_0 - \frac{a}{d}n)：

假设 (x, y) 是方程的一个解，即：
ax + by = c
又因为 ax_0 + by_0 = c，两式相减得到：
a(x - x_0) + b(y - y_0) = 0
即：
a(x - x_0) = -b(y - y_0)
两边同时除以 d 得到：
\frac{a}{d}(x - x_0) = \frac{b}{d}(y_0 - y)
由于 \frac{a}{d} 和 \frac{b}{d} 互质，根据引理2， \frac{a}{d} \mid (y_0 - y) ，因此存在整数 n 使得：
\frac{a}{d}n = y_0 - y
由此得出：
y = y_0 - \frac{a}{d}n
同理， \frac{b}{d} \mid (x - x_0) ，因此存在整数 n 使得：
\frac{b}{d}n = x - x_0
从而得出：
x = x_0 + \frac{b}{d}n
因此，方程的任意解都可以表示为：
x = x_0 + \frac{b}{d}n, \quad y = y_0 - \frac{a}{d}n
其中 n 是整数。