整除性

定义1（整除）

定理1（整除的传递性）

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

定理3（带余除法定理）

最大公因子及其性质

定义2（最大公因子）

定义3（互素）

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

推论1（最简分数）

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

定义4（线性组合）

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

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

引理1（递归法则）

扩展欧几里得算法（ExGCD）

• 步骤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;
}

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

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

推论2（互素的定义）

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

二元一次不定方程

引理2：

定理8：

1. 如果 $d \nmid c$，方程 $ax + by = c$ 没有整数解：
   根据定理7，方程 $ax + by$ 的结果是 $d$ 的倍数。
   因此，如果 $d \nmid c$，则方程 $ax + by = c$ 没有整数解。
2. 如果 $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$ 的一个特解。
3. 证明无穷多个解的存在：
   设 $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$ 是整数。