初等数论入门

By Zirnc

May 05, 2023

16 minutes

我也不知道这是从哪本书上抠来的？

整除

定义 1：如果 $a$ 和 $b$ 为整数且 $a \ne 0$，我们说 $a$ 整除 $b$ 是指存在整数 $c$ 使得 $b=ac$。如果 $a$ 整除 $b$，我们还称 $a$ 是 $b$ 的一个因子，且称 $b$ 是 $a$ 的倍数。

如果 $a$ 整除 $b$，则将其记为 $a \mid b$，如果 $a$ 不能整除 $b$，则记其为 $a \nmid b$。

定理 1：如果 $a, b$ 和 $c$ 是整数，且 $a \mid b, b \mid c$，则 $a \mid c$。

定理 2：如果 $a, b, m$ 和 $n$ 为整数，且 $c \mid a, c \mid b$，则 $c \mid (ma+nb)$。

定理 3：带余除法 如果 $a$ 和 $b$ 是整数且 $b \gt 0$，则存在唯一的整数 $q$ 和 $r$，使得$a = bq + r, 0 ≤ r < b$。

最大公因子及其性质

定义 2：不全为零的整数 $a$ 和 $b$ 的最大公因子是指能够同时整除 $a$ 和 $b$ 的最大整数。

定义 3：设 $a,b$ 均为非零整数，如果 $a$ 和 $b$ 最大公因子 $(a,b)=1$，则称 $a$ 与 $b$ 互素。

定理 4：$a，b$ 是整数，且 $(a, b)=d$，那么 $(a/d, b/d)=1$。（换言之，$a/d$ 与 $b/d$ 互素）

推论 1：如果 $a, b$ 为整数，且 $b\ne 0$，则 $a/b=p/q$，其中 $p, q$ 为整数，且 $(p,q)=1, q≠0$。

定理 5：令 $a, b, c$ 是整数，那么 $(a+cb, b) = (a, b)$

证明：令 $a, b, c$ 是整数，证明 $a, b$ 的公因子与 $a+cb, b$ 的公因子相同，即证明 $(a+cb, b)=(a, b)$。

令 $e$ 是 $a, b$ 的公因子，由定理 2 可知 $e \mid (a+cb)$，所以 $e$ 是 $a+cb$ 和 $b$ 的公因子。

如果 $f$ 是 $a+cb$ 和 $b$ 的公因子，由定理 2 可知 $f$ 整除 $(a+cb)-cb=a$，所以 $f$ 是 $a, b$ 的公因子，因此 $(a+cb, b)=(a,b)$。

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

定理 6：两个不全为零的整数 $a, b$ 的最大公因子是 $a, b$ 的线性组合中最小的正整数。

证明：令 $d$ 是 $a,b$ 的线性组合中最小的正整数，$d = ma + nb$，其中 $m,n$ 是整数，我们将证明 $d\mid a, d\mid b$。

由带余除法，得到 $a=dq+r, 0\le r\lt d$。

由 $a=dq+r $和 $d=ma+nb$，得到 $r=a-dq=a-q(ma+nb)=(1-qm)a-qnb$。

这就证明了整数 $r$ 是 $a,b$ 的线性组合。因为 $0 \le r \lt d$，而 $d$ 是 $a,b$ 的线性组合中最小的正整数，

于是我们得到 $r=0$（如果 $r$ 不是等于 $0$，那意味着 $r$ 才是所有线性组合中最小的正整数，这与 $d$ 是所有线性组合中最小的正整数矛盾），因此 $d\mid a$，同理可得，$d\mid b$。

我们证明了 $a,b$ 的线性组合中最小的正整数 $d$ 是 $a,b$ 的公因子，剩下要证的是它是 $a,b$ 的最大公因子，为此只需证明 $a,b$ 所有的公因子都能整除 $d$。

由于 $d = ma + nb$，因此如果 $c \mid a$ 且 $c \mid b$，那么由定理 2 有 $c \mid d$，因此 $d \gt c$，这就完成了证明。

定义 5：令 $a_1,a_2,…,a_n$ 是不全为零的整数，这些整数的公因子中最大的整数就是最大公因子。$a_1,a_2,…,a_n$ 的最大公因子记为 $(a_1, a_2, …, a_n)$。

引理 1：如果 $a_1,a_2,…,a_n$ 是不全为零的整数，那么 $(a_1, a_2, …, a_{n-1}, a_n) = (a_1, a_2, …, (a_{n-1}, a_n))$。

欧几里得算法

辗转相除法求 gcd，即 $\gcd(a, b) = \gcd(b, a\bmod b)$。

证明 1：由定理 3 带余除法，存在整数 $q, r$ 使得 $a = bq + r, 0 \le r \lt b$, 得到 $r = a - bq$。由定理 5 得，$\gcd(a,b) = \gcd(a-bq,b) = \gcd(r,b) = \gcd(a%b,b) = \gcd(b,a%b)$。

证明 2：令 $d=(a,b)$，证明 $d \mid (b,a\bmod b)$，再反证 $(b,a\bmod b) \gt d$ 是不可能的。

时间复杂度的证明：

假设 $a\gt b$，分两种情况：

$b \lt a/2$，经过一次辗转得到 $(b,a\bmod b)$，$\max(a,b)$ 至少缩小一半。
$b \ge a/2$，经过两次辗转得到彼时的 $\max(a,b)$ 至少缩小一半。

综上所述，最多 $2\log(n)$ 次辗转算法结束。

裴蜀定理

如果 $a$ 与 $b$ 均为整数，则存在整数 $x$ 和 $y$ 满足 $ax + by = (a,b)$。

由定理 6 容易证明正确性。

下面用扩展欧几里得算法（exgcd）求出满足 $ax + by = (a,b)$ 的一个特解。

例如：$a = 99, b = 78$，令 $d =(a,b) = (99,78) = 3$，求 $99x + 78y = 3$ 的一个特解。

在调用 exgcd 的时候，从后往前依次构造出相应的解。

$a$	$b$	$d$	$x$	$y$	备注
$99$	$78$	$3$	$-11$	$14$	怎样由 $78x + 21y = 3$的一个特解 $x=3, y=-11$，构造出 $99x + 78y = 3$ 的一个特解？
$78$	$21$	$3$	$3$	$-11$	$78x + 21y = 3$ 的一个特解 $x=3, y=-11$
$21$	$15$	$3$	$-2$	$3$	$21x + 15y = 3$ 的一个特解 $x=-2, y=3$
$15$	$6$	$3$	$1$	$-2$	$15x + 6y = 3$ 的一个特解 $x=1, y=-2$
$6$	$3$	$3$	$0$	$1$	$6x + 3y = 3$ 的一个特解是 $x=0, y=1$
$3$	$0$	$3$	$1$	$0$	$3x + 0y = 3$ 的一个特解是 $x=1, y=0$

在用欧几里得算法求 $(99,78)$ 的时候，是要先求 $(78,21)$。

假如已经求出 $78x + 21y = 3$ 的一个解 ${x_0,y_0} = {3,-11}$，即 $78x_0 + 21y_0 = 3$。

那么可以由 $78x_0 + 21y_0 = 3$，构造出 $99x + 78y = 3$ 的一个特解。

因 $a=99, b=78, a\bmod b=21$, 因此 $78x_0 + 21y_0 = 3$，可以写成：$bx_0 + (a\bmod b)y_0 = 3$，即 $bx_0+(a-\frac{a}{b}b)y_0=3$，即 $ay_0+b(x_0-\frac{a}{b}y_0)=3$，即 $99y_0+78(x_0-\frac{99}{78}y_0)=3$。

那么只需要令 $x = y_0 = -11, y = x_0 - \frac{99}{78}y_0=14$，就可以得到 $99x + 78y = 3$ 的一个特解，即 ${-11, 14}$ 是 $99x+78y=3$ 的一个特解。

也就是说，在用欧几里得算法求 $(78,21)$ 的时候，若能返回 ${x_0,y_0}$ 使得满足 $78x_0 + 21y_0 = 3$，那么就能构造出一个特解 ${x,y}$ 满足 $99x + 78y = 3$ 的一个特解。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
void exgcd(int a, int b, int &d, int &x, int &y) {
  if (!b) {
    d = a;
    x = 1;
    y = 0;
    return;
  }
  exgcd(b, a % b, d, x, y);
  int t = x;
  x = y;
  y = t - (a / b) * y;
  return;
}

注意：若 $a\lt 0$ 且 $b\ge 0$ 那么在求 $ax+by=(a,b)$ 的时候，可以先求出 $|a|x+by=(|a|,b)$ 的一组解 ${x_0,y_0}$，然后 ${-x_0,y_0}$ 就是原方程的一个解。

若 $a\ge 0$ 且 $b\lt 0$ 的同理。若 $a \lt 0$ 且 $b \lt 0$ 的也同理。

定理 7：如果 $a,b$ 是正整数，那么所有 $a,b$ 的线性组合构成的集合与所有 $(a,b)$ 的倍数构成的集合相同。

证明：假设 $d = (a,b)$。

首先证明每个 $a,b$ 的线性组合是 $d$ 的倍数。首先注意到由最大公因子的定义，有 $d\mid a$ 且 $d\mid b$，每个 $a,b$ 的线性组合具有形式 $ma+nb$，其中 $m,n$ 是整数。

由定理 2，只要 $m,n$ 是整数，$d$ 就整除 $ma+nb$，因此，$ma+nb$ 是 $d$ 的倍数。

现在证明每一个 $d$ 的倍数也是 $(a，b)$ 的线性组合。

由定理 6，存在整数 $r,s$ 使得 $(a,b) = ra + sb$。而 $d$ 的倍数具有形式 $jd$，其中 $j$ 是整数。

在方程 $d = ra + sb$ 的两边同时乘以 $j$，我们得到 $jd = (jr)a + (js)b$。

因此，每个 $d$ 的倍数是 $(a,b)$ 的线性组合。

推论 2：整数 $a$ 与 $b$ 互素当且仅当存在整数 $m$ 和 $n$ 使得 $ma + nb = 1$。

证明：如果 $a，b$ 互素，那么 $(a,b)=1$，由定理 6 可知，$1$ 是 $a$ 和 $b$ 的线性组合的最小正整数，于是存在整数 $m,n$ 使得 $ma + nb = 1$。

反之，如果有整数 $m$ 和 $n$ 使得 $ma + nb = 1$，则由定理 6 可得 $(a,b)=1$，这是由于 $a,b$ 不同为 $0$ 且 $1$ 显然是 $a,b$ 的线性组合中的最小正整数。

二元一次不定方程

引理 2：如果 $a, b, c$ 是正整数，满足 $(a, b) = 1, a \mid bc$，则 $a \mid c$。

证明：由于 $(a, b)=1$，存在整数 $x$ 和 $y$ 使得 $ax+by=1$。等式两边同时乘以$c$，得 $acx+bcy=c$。

根据定理 2，$a$ 整除 $(cx)a + y(bc)$，这是因为这是 $a$ 和 $bc$ 的线性组合，而它们都可以被 $a$ 整除。因此，$a \mid c$。

定理 8：设 $a,b$ 是整数且 $d=(a,b)$。如果 $d \nmid c$，那么方程 $ax+by=c$ 没有整数解，如果 $d \mid c$，那么存在无穷多个整数解。

另外，如果 $x = x_0, y = y_0$ 是方程的一个特解，那么所有的解可以表示为：$x = x_0 + (b/d)n， y = y_0 - (a/d)n$，其中 $n$ 是整数。

证明：由定理 7 可知，$ax+by$ 的结果是 $d$ 的倍数，因此如果 $d \nmid c$，那么方程 $ax+by=c$ 没有整数解。

如果 $d\mid c$，存在整数 $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 + (b/d)n, y = y_0 - (a/d)n$，其中 $n$ 是整数。

证明任何一对整数 $(x_0+(b/d)n, y_0 - (a/d)n)$ 它是方程的解。

因为 $a(x_0+(b/d)n) + b(y_0 - (a/d)n) = ax_0 + by_0 + a(b/d)n - b(a/d)n = ax_0 + by_0$，而 $ax_0+by_0$ 是方程 $ax+by=c$ 的解，所以 $(x_0+(b/d)n, y_0 -(a/d)n)$ 就是方程的解。

证明方程的任何一个解都具有 $(x_0 + (b/d)n, y_0 - (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_0-y)$，等式两边同时除以 $d$ 得到 $(a/d)(x-x_0) = (b/d)(y_0-y)$，根据定理 4，$a/d$ 与 $b/d$ 互质，再根据引理 2，$(a/d) \mid (y_0-y)$，因此存在整数 $n$ 使得 $(a/d)n = y_0 - y$，于是得到 $y=y_0-(a/d)n$。

同理可得，$(b/d) \mid (x-x_0)$，因此存在整数 $n$ 使得 $(b/d)n = x - x_0$，于是得到 $x=x_0+(b/d)n$。

习题

Luogu-P5656 【模板】二元一次不定方程 (exgcd) Orz 离散小波变换°

下面设 $p = b/d, q = a/d$。

有正整数解：

解的个数：不断地将 $y_0$ 减去 $q$，$x_0$ 加上 $p$ 就可以找到所有可行解，个数为 $\lfloor (y-1)/q\rfloor + 1$
$x$ 的最小正整数值：exgcd 得到的 $x_0$
$y$ 的最小正整数值：不断地将 $y_0$ 减去 $q$（因为 $x_0$ 最小时，$y_0$ 一定最大），答案为 $(y-1)\bmod q+1$（特别注意 $0$ 的情况）
$x$ 的最大正整数值：不断将 $x_0$ 加上 $p$，答案为 $x+\lfloor (y-1)/q\rfloor * p$
$y$ 的最大正整数值：$x_0$ 为最小正整数时，$y_0$ 就是最大值

无正整数解：

$x$ 的最小正整数值：exgcd 得到的 $x_0$
$y$ 的最小正整数值：当前的 $y_0 \le 0$，需要执行构造 $x_0$ 的方法，即 $y_0 + q * \lceil (1.0-y)/q \rceil$

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include <bits/stdc++.h>
using namespace std;
#define LL long long 
void exgcd(LL a, LL b, LL &d, LL &x, LL &y) {
  if (b == 0) {
    d = a;
    x = 1;
    y = 0;
    return; 
  }
  exgcd(b, a%b, d, x, y);
  LL t = x;
  x = y;
  y = t-(a/b)*y;
}
int main()
{
  int t;
  cin >> t;
  while (t--) {
    LL a, b, c, x, y, d;
    cin >> a >> b >> c;
    exgcd(a, b, d, x, y);
    if (c%d != 0) {
      puts("-1");
    } else {
      x *= c/d;
      y *= c/d;
      LL p = b/d, q = a/d, k;
      if (x < 0) { k = ceil((1.0-x)/p); x += p*k; y -= q*k; }
      if (x >= 0) { k = (x-1)/p; x -= p*k; y += q*k; }
      if (y > 0) {
        cout << (y-1)/q+1 << " " << x << " " << (y-1)%q+1 << " " << x+(y-1)/q*p << " " << y << endl;
      } else {
        cout << x << " " << y+q*(LL)ceil((1.0-y)/q) << endl; 
      }
    }
  }
  return 0; 
} 

多元一次不定方程的一组解：求 $a_1x_1 + a_2x_2 + a_3x_3 + … + a_nx_n = c$ 的一组整数解，如无整数解输出 $-1$。

先考虑三元一次不定方程 $a_1x_1 + a_2x_2 + a_3+x_3 = c$。可以用 exgcd 解二元一次方程 $a_1x_1 + a_2x_2 = (a_1, a_2)$，设 $d = (a_1, a_2)$，由定理 8 知道 $d$ 乘任何整数时该方程都有整数解，就可以把 $d$ 当做原方程的一个系数，转而求解 $dt+a_3x_3 = c$。上一步的方程变为 $t(a_1x_1 + a_2x_2) = td$，于是将 $t$ 乘上前面的 $x_1, x_2$ 就得到最终答案。

多元同理。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
int main()
{
  exgcd(a[1], a[2], ta[2], ans[1], ans[2]);
  int tm = 1;
  for (int i = 3; i <= n; i++) {
    LL tmp;
    exgcd(ta[i-1], a[i], ta[i], tmp, ans[i]);
    if (i == n && c%ta[i]) { cout << -1 << endl; return 0; }
    for (int j = 1; j < i; j++) ans[j] *= tmp;  
  }
  tm = c/ta[n];
  for (int i = 1; i <= n; i++) {
    cout << ans[i]*tm <<" ";
  }
  return 0;
} 

Luogu-P3986 斐波那契数列：求 $f(i)x+f(i+1)y=k$ 的正整数解个数（$f$ 表示斐波那契数列）

显然 $f(i)+f(i+1)\gt k$ 时就不用继续下去了，因此方程的个数是有限的，可以枚举。

然后题目就变成了求 $f_ia+f_{i+1}b=k$ 的正整数解的个数。

另外，有没有可能同样的 $(a, b)$ 出现了两次呢？不可能。否则就需要满足 $af_i+bf_{i+1}=af_j+bf_{j+1}, i \ne j$，然而斐波那契数列任两项不相等，以上式子不成立。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
int main()
{
  LL n;
  cin >> n;
  fib[0] = fib[1] = 1;
  for (int i = 2; i <= 50; i++) fib[i] = fib[i-1]+fib[i-2];
  LL ans = 0;
  for (int i = 1; fib[i] < n; i++) {
    LL d, x, y, k;
    exgcd(fib[i-1], fib[i], d, x, y);
    LL p = fib[i]/d, q = fib[i-1]/d;
    x = x*(n/d), y = y*(n/d);
    if (x <= 0) {
      k = ceil((1.0-x)/p);
      x += k*p;
      y -= k*q;
    }
    if (x >= 0) {
      k = (x-1)/p;
      x -= k*p;
      y += k*q;
    }
    if (x <= 0 || y <= 0) continue;
    ans = ((y-1)/q+1+ans)%MOD;
  }
  cout << ans << endl;
  return 0;
} 

同余

同余概述

定义 6：设 $m$ 是正整数，若 $a$ 和 $b$ 是整数，且 $m\mid (a-b)$，则称 $a$ 和 $b$ 模 $m$ 同余。

若 $a$ 和 $b$ 模 $m$ 同余，则记 $a\equiv b(mod\ m)$。

若 $m \nmid (a-b)$，则记 $a\not\equiv b (mod\ m)$，并称 $a$ 模 $m$ 不同余于 $b$。

整数 $m$ 称为同余的模。

定理 9：若 $a$ 和 $b$ 是整数，则 $a\equiv b(mod\ m)$ 当且仅当存在整数 $k$，使得 $a=b+km$。

证明：若 $a\equiv b(mod\ m)$，则 $m\mid (a-b)$，这说明存在整数 $k$，使得 $km=a-b$，所以 $a=b+km$。

反过来，若存在整数 $k$ 使得 $a=b+km$，则 $km=a-b$。于是，$m\mid (a-b)$，因而 $a\equiv b(mod\ m)$。

例：$19\equiv -2(mod\ 7)$ 和 $19=-2+3·7$。

定理 10：设 $m$ 是正整数，模 $m$ 的同余满足下面的性质:

自反性。若 $a$ 是整数，则 $a\equiv a(mod\ m)$。
对称性。若 $a$ 和 $b$ 是整数，且 $a\equiv b(mod\ m)$，则 $b\equiv a(mod\ m)$。
传递性。若 $a,b,c$ 是整数，且 $a\equiv b(mod\ m)$ 和 $b\equiv c(mod\ m)$，则 $a\equiv c(mod\ m)$。

证明：

因为 $m\mid(a-a)=0$，所以 $a=a(mod\ m)$。
若 $a\equiv b(mod\ m)$，则 $m\mid(a-b)$。从而存在整数 $k$，使得 $km=a-b$。这说明 $(-k)m=b-a$，即 $m\mid (b-a)$。因此，$b\equiv a(mod\ m)$。
若 $a\equiv b(mod\ m)$，且 $b\equiv c(mod\ m)$，则有 $m\mid (a-b)$ 和 $m\mid (b-c)$。从而存在整数 $k$ 和 $l$，使得 $km=a-b,lm=b-c$。于是，$a-c=(a-b)+(b-c)=km+lm=(k+l)m$。因此，$m\mid(a-c), a\equiv c(mod\ m)$。

由定理 10 可见，整数的集合被分成 $m$ 个不同的集合，这些集合称为模 $m$ 剩余类（同余类），每个同余类中的任意两个整数都是模 $m$ 同余的。

注意，当 $m=2$ 时，正好整数分成奇、偶两类.

如果你对集合上的关系比较熟悉，那么定理 10 表明对正整数 $m$ 的模 $m$ 同余是一种等价关系，并且每一个模 $m$ 同余类即是由此种等价关系所定义的等价类。

例模 $4$ 的四个同余类是：

$$ …\equiv 8\equiv -4\equiv 0\equiv 4\equiv 8\equiv …(mod\ 4) \\ …\equiv -7\equiv -3\equiv 1\equiv 5\equiv 9\equiv …(mod\ 4) \\ …\equiv -6\equiv -2\equiv 2\equiv 6\equiv 10\equiv …(mod\ 4) \\ …\equiv -5\equiv -1\equiv 3\equiv 7\equiv 11\equiv …(mod\ 4) \\ $$

设 $m$ 是正整数，给定整数 $a$，由带余除法有 $a = bm + r$，其中 $0\le r \lt m-1$，称 $r$ 为 $a$ 的模 $m$ 最小非负剩余，是 $a$ 模 $m$ 的结果，类似地，当 $m$ 不整除 $a$ 时，称 $r$ 为 $a$ 的模 $m$ 最小正剩余。

$mod\ m$ 实际上是从整数集到集合 ${0,1,2,…,m-1}$ 的函数。

定理 11：若 $a$ 与 $b$ 为整数，$m$ 为正整数，则 $a\equiv b(mod\ m)$ 当且仅当 $a \bmod m = b \bmod m$。

证明：

若 $a\equiv b(mod\ m)$ 则 $a\bmod m = b \bmod m$。

由带余除法 $a=pm+ra , b=qm+rb$，因 $a\equiv b(mod\ m)$，则 $m\mid a-b$，则 $m\mid (p-q)m+(ra-rb)$，则存在整数 $x$，满足 $xm = (p-q)m+(ra-rb)$，则 $ra-rb = (x-p+q)m$，则 $ra-rb\mid m$。

因 $0\le ra\lt m, 0\le rb\lt m$, 故 $-(m-1) \le ra-rb \lt m$，故 $ra-rb$ 只能是 $0$ 才能满足 $ra-rb\mid m$。

则 $ra = rb$，则 $ra=a \bmod m, rb=b \bmod m$，则 $a \bmod m = b \bmod m$。

若 $a \bmod m = b \bmod m$ 则 $a\equiv b(mod\ m)$。

由带余除法 $a=pm+ra , b=qm+rb$，若 $a \bmod m = b \bmod m$，则 $ra=rb$。

因此 $a-b = (pm+ra)-(qm+rb)=(p-q)m + (ra-rb) = (p-q)m$。因此 $m\mid a-b$，故 $a\equiv b(mod\ m)$。

因此，每个整数都和 $0,1,…,m-1$（也就是 $a$ 被 $m$ 除所得的余数）中的一个模 $m$ 同余。因为 $0,1,…,m-1$ 中的任何两个都不是模 $m$ 同余的，所以有 $m$ 个整数使得每个整数都恰与这 $m$ 个整数中的一个同余。

定理 12：若 $a,b,c,m$ 是整数，$m\gt 0$，且 $a\equiv b(mod\ m)$，则

$a+c\equiv b+c(mod\ m)$
$a-c\equiv b-c(mod\ m)$
$ac\equiv bc(mod\ m)$

定理 13：若 $a,b,c,m$ 是整数，$m\gt 0, d=(c,m)$，且有 $ac\equiv bc(mod\ m)$，则 $a\equiv b(mod\ m/d)$。

证明：若 $ac\equiv bc(mod\ m)$，所以存在整数 $k$ 满足 $c(a-b)=km$，两边同时除以 $d$，得到：$(c/d)(a-b)=k(m/d)$，因为 $(m/d,c/d)=1$，根据引理 2，$m/d\mid a-b$，因此 $a\equiv b(mod\ m/d)$。

下面的推论是定理 13 的特殊情形，经常用到，它使得我们能够在模 $m$ 同余式中消去与模 $m$ 互素的数。

推论 3：若 $a,b,c,m$ 是整数，$m\gt 0,(c，m)=1$，且有 $ac\equiv bc(mod\ m)$，则 $a\equiv b(mod\ m)$。

定理 14 ：若 $a,b,c,m$ 是整数，$m\gt 0,a\equiv b(mod\ m)$，且 $c\equiv d(mod\ m)$，则:

$a+c\equiv b+d(mod\ m)$
$a-c\equiv b-d(mod\ m)$
$ac\equiv bd(mod\ m)$

证明：

因为 $a\equiv b(mod\ m)$ 且 $c\equiv d(mod\ m)$，我们有 $m\mid (a-b)$ 与 $m\mid (c-d)$。因此，存在整数 $k$ 与 $l$ 使得 $km=a-b,lm=c-d$。

为证 1，注意到 $(a+c)-(b+d)=(a-b)+(c-d)=km+lm=(k+l)m$.因此 $m\mid (a+c)-(b+d)$，即 $a+c\equiv b+d(mod\ m)$。

为证 2，注意到 $(a-c)-(b-d)=(a-b)-(c-d)=km-lm=(k-1)m$，因此 $m\mid (a-c)-(b-d)$，即 $a-c\equiv b-d(mod\ m)$.

为证 3，注意到 $ac-bd=ac-bd+bc-bd=c(a-b)+b(c-d)=ckm+blm=m(ck+ bl)$。因此，$m\mid ac-bd$，即 $ac\equiv bd(mod\ m)$。

定义 7：一个模 $m$ 完全剩余系是一个整数的集合，使得每个整数恰和此集合中的一个元素模 $m$ 同余。

例如：整数 $0,1,…,m-1$ 的集合是模 $m$ 完全剩余系，称为模 $m$ 最小非负剩余的集合。

下面的引理帮助我们判定一个 $m$ 元集合是否为模 $m$ 的完全剩余系.

引理 3：$m$ 个模 $m$ 不同余的整数的集合构成一个模 $m$ 的完全剩余系。

证明：

假设 $m$ 个模 $m$ 不同余的整数集合不是模 $m$ 完全剩余系，这说明，至少有一个整数 $a$ 不同余于此集合中的任一整数。

所以此集合中的整数都模 $m$ 不同余于 $a$ 被 $m$ 除所得的余数，从而，整数被 $m$ 除得的不同剩余至多有 $m-1$ 个。

由鸽笼原理，此集合中至少有两个整数有相同的模 $m$ 剩余。

这不可能，因为这些整数均模 $m$ 不同余，因此，$m$ 个模 $m$ 不同余的整数的集合构成一个模 $m$ 的完全剩余系。

定理 15：若 $r_1,r_2,…,r_m$ 是一个模 $m$ 的完全剩余系，且正整数 $a$ 满足 $(a,m)=1$，则对任何整数 $b$，$ar_1+b, ar_2+b,…,ar_m+b$ 都是模 $m$ 的完全剩余系。

证明：首先来证整数 $ar_1+b, ar_2+b,…,ar_m+b$ 中的任何两个都模 $m$ 不同余。

反证，若存在 $1\le j,k\le m$ 且 $j\ne k$ 且 $ar_j+b \equiv ar_k+b(mod\ m)$，则由定理 12.2 可知：$ar_j \equiv ar_k(mod\ m)$。因为 $(a，m)=1$，推论 3 表明 $r_j\equiv r_k(mod\ m)$，这与 $r_1,r_2,…,r_m$ 是一个模 $m$ 的完全剩余系相矛盾。

故 $ar_1+b, ar_2+b,…,ar_m+b$ 是 $m$ 个模 $m$ 不同余的整数，由引理 3，命题得证。

定理 16：若 $a,b,k,m$ 是整数，$k\gt 0,m\gt 0$，且 $a\equiv b(mod\ m)$，则 $a^k\equiv b^k(mod\ m)$。

证明：因为 $a\equiv b(mod\ m)$，所以 $m\mid a-b$。

因为 $a^k-b^k =(a-b)(a^{k-1}+a^{k-2}b+…ab^{k-2}+b^{k-1})$ （可以参考资料：详聊如何理解a^n-b^n因式分解）

所以 $a-b \mid a^k-b^k$，根据定理 1，$m \mid a^k-b^k$，即 $a^k\equiv b^k(mod\ m)$。

线性同余方程

设 $x$ 是未知整数，形如 $ax\equiv b(mod\ m)$ 的同余式称为一元线性同余方程。

首先注意到，若 $x=x_0$ 是同余方程 $ax\equiv b(mod\ m)$ 的一个解，且 $x_1\equiv x_0(mod\ m)$，则 $ax_1\equiv ax_0 \equiv b(mod\ m)$，所以 $x_1$ 也是一个解。

因此，若一个模 $m$ 同余类的某个元素是解，则此同余类的所有元素都是解。

于是，我们会问模 $m$ 的 $m$ 个同余类中有多少个是给出方程的解，这相当于问方程有多少个模 $m$ 不同余的解。

定理 17：设 $a,b,m$ 是整数，$m\gt 0,(a,m)=d$。

若 $d\nmid b$，则 $ax\equiv b(mod\ m)$ 无解。

若 $d\mid b$，则 $ax\equiv b(mod\ m)$ 恰有 $d$ 个模 $m$ 不同余的解。

证明：根据定理 9，线性同余方程 $ax\equiv b(mod\ m)$ 可以写成二元线性不定方程 $ax+my=b$。其中 $x, y$ 是未知数。整数 $x$ 是 $ax\equiv b(mod\ m)$ 的解当且仅当存在整数 $y$ 使得 $ax+my=b$。

由定理 8 可知，若 $d\nmid b$，则无解，而 $d\mid b$ 时，$ax-my=b$ 有无穷多解：$x = x_0 + (m/d)t, y = y - (a/d)t$，

其中 $x=x_0$ 和 $y=y_0$ 是方程的特解，上述 $x$ 的值 $x=x_0+(m/d)t$ 是线性同余方程的解，有无穷多这样的解。

为确定有多少不同余的解，我们来找两个解 $x_1=x_0+(m/d)t1$ 和 $x_2=x_0+(m/d)t2$ 模 $m$ 同余的条件，若这两个解同余，则 $(x0+(m/d)t1)\equiv (x0+(m/d)t2) (mod\ m)$。

根据定理 12，两边减去 $x_0$，有 $(m/d)t1\equiv (m/d)t2(mod\ m)$。

因为 $(m/d)\mid m$，所以 $(m,m/d)=m/d$，再由定理 13 得，$t1\equiv t2 (mod\ d)$。

这表明不同余的解的一个完全集合可以通过取 $x=x_0+(m/d)t$ 得到，其中 $t$ 取遍模 $d$ 的完全剩余系，一个这样的集合可由 $x=x_0+(m/d)t$ 给出，其中 $t=0,1,2,…,d-1$。

推论 4：若 $a$ 和 $m\gt 0$ 互素，且 $b$ 是整数，则线性同余方程 $ax\equiv b(mod\ m)$ 有模 $m$ 的唯一解。

证明：

因为 $(a,m)=1$，所以 $(a,m)\mid b$。因此，由定理 17，线性同余方程 $ax\equiv b(mod\ m)$ 恰有 $(a,m)=1$ 个模 $m$ 不同余的解。

例：为求出 $9x\equiv 12(mod\ 15)$ 的所有解，首先注意到因为 $(9,15)=3$ 且 $3\mid 12$，所以恰有三个不同余的解，我们可以通过先找到一个特解，再加上 $15/3=5$ 的适当倍数来求得所有的解。

为求特解，我们考虑二元线性不定方程 $9x-15y=12$。由扩展欧几里得算法得到：$9x-15y=12$ 的一个特解是 $x_0=8$ 和 $y_0=4$。

由定理 17 的证明可知，三个不同余的解由 $x= x_0\equiv 8(mod\ 15),x= x_0+5\equiv 13(mod\ 15)$ 和 $x= x_0+5*2\equiv 18\equiv 3(mod\ 15)$ 给出。

习题

Luogu-P1516 青蛙的约会 Orz 题解 P1516 【青蛙的约会】 - FlashHu

如果两蛙相遇，那么他们的初始坐标差 $x-y$ 和跳的距离 $(n-m)t$ 之差应该模纬度线总长 $l$ 同余，$(n-m)t\equiv x-y(mod\ l)$。转化成不定方程的形式：$(n-m)t+kl=x-y$，并求最小正整数解。设 $a=n-m,b=l,c=x-y$，可以写成 $ax+by = c$，通过 exgcd 可以求出 x 的一个特解。

细节问题，因为 gcd 只对非负整数有意义，如果 $a\lt 0$ 时等式两边要同时取负，$a,c$ 变成相反数（相当于把两个蛙交换了一下），$b$ 是正数所以不能变。

这里求最小正整数解时用了模的方法来处理，~~值得细品~~ (x0%p+p)%p。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
int main()
{
  cin >> x >> y >> m >> n >> l;
  LL a = n-m, b = l, c = x-y, d, x0, y0;
  if (a < 0) {
    a = -a;
    c = -c;
  }
  exgcd(a, b, d, x0, y0);
  if (c % d == 0) {
    x0 *= c/d;
    y0 *= c/d;
    LL p = b/d;
    cout << (x0%p+p)%p << endl;
  } else {
    cout << "Impossible\n";
  }
  return 0;
} 

POJ-2115 – C Looooops

可将题意转化为 $A+Ct\equiv B(mod\ 2^K)$，把它转化成方程：$A+Ct-B=2^Kz$，即 $Ct+2^Kz=B-A$，用 exgcd 解这个方程并求出 $t$ 的最小正整数解即为答案。

注意 1LL<<K，不开 long long 差点怀疑自己做错了。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
while (cin >> A >> B >> C >> K && !(A==0&&B==0&&C==0&&K==0)) {
  K = 1ll<<K;
  LL a = C, b = K, d, x, y;
  exgcd(a, b, d, x, y);   
  if (((B-A+K)%K)%d) {
    cout <<"FOREVER\n";
  } else {
    x *= ((B-A+K)%K)/d;
    LL p = b/d;
    x = (x%p+p)%p;
    cout << x << endl;
  }
}

模的逆

现在考虑特殊形式的同余方程 $ax\equiv 1(mod\ m)$。

由定理 17，此方程有解当且仅当 $(a,m)=1$，于是其所有的解都模 $m$ 同余。

定义 8：给定整数 $a$，且满足 $(a,m)=1$，称 $ax\equiv 1(mod\ m)$ 的一个解为 $a$ 模 $m$ 的逆。

例：因为 $7x\equiv 1(mod\ 31)$ 的解满足 $x\equiv 9(mod\ 31)$，所以 $9$ 和所有与 $9$ 模 $31$ 同余的整数都是 $7$ 模 $31$ 的逆。类似地，因为 $9·7\equiv 1(mod\ 31)$，所以 $7$ 是 $9$ 模 $31$ 的逆。

当我们有 $a$ 模 $m$ 的一个逆时，可以用它来解形如 $ax\equiv b(mod\ m)$ 的任何同余方程。

为看清这一点，令 $\bar{a}$ 是 $a$ 的模 $m$ 的一个逆，所以 $a\bar{a}\equiv 1(mod\ m)$。

于是，若 $ax\equiv b(mod\ m)$，则根据定理 12 将同余方程两边同时乘以 $\bar{a}$，得到 $\bar{a}(ax)\equiv \bar{a}b(mod\ m)$，所以 $x=\bar{a}b(mod\ m)$。

例为求出 $7x\equiv 22(mod\ 31)$ 的所有解，我们在此方程两边同时乘以 $9$（这是 $7$ 模 $31$ 的一个逆），得 $9·7x\equiv 9·22(mod\ 31)$。因此，$x\equiv 198=12(mod\ 31)$。

求逆的三种算法：

扩展欧几里得算法解同余方程，求单个逆。$ax\equiv 1(mod\ m)$ 等价于求二元线性不定方程的解：$ax+my=1$，其中 $(a,m)=1$ 是有逆的前提。只需要用扩展欧几里得算法求即可。
费马小定理，求单个逆

定理 18（费马小定理）：设 $p$ 是一个素数，$a$ 是一个正整数且 $p\nmid a$，则 $a^{p-1}\equiv 1(mod\ p)$。

证明：考虑 $p-1$ 个整数 $a,2a,…,(p-1)a$，它们都不能被 $p$ 整除。因为若 $p \mid ja$, 那么因 $p \nmid a$，则由引理 2 知 $p \mid j$，但 $1\le j\le p-1$，故这是不可能的。

现证明 $a,2a,…,(p-1)a$ 中任何两个整数模 $p$ 不同余。

为了证明这一点，设 $ja\equiv ka(mod\ p)$，其中 $1\le j\lt k\le p-1$。

那么根据推论 3，因 $(a,p)=1$，故 $j\equiv k(mod\ p)$，但这也是不可能的，因为 $j$ 和 $k$ 都是小于 $p-1$ 的正整数.

因为整数 $a,2a,…,(p-1)a$ 是 $p-1$ 个满足模 $p$ 均不同余于 $0$ 且任何两个都互不同余的整数组成的集合中的元素，故由引理 3 可知 $a,2a,…,(p-1)a$ 模 $p$ 的最小正剩按照一定的顺序必定是整数 $1,2,…,p-1$。

由同余性，整数 $a,2a,…,(p-1)a$ 的乘积模 $p$ 同余于前 $p-1$ 个正整数的乘积，即：

$a·2a·3a···(p-1)a \equiv 1·2·3···(p-1) (mod\ p)$

因此 $a^{p-1}(p-1)! \equiv (p-1)! (mod\ p)$，因 $(p,(p-1)!)=1$，根据推论 3，消去 $(p-1)!$，得到 $a^{p-1}\equiv 1(mod\ p)$，证毕。

利用费马小定理，$a^{p-1}\equiv 1(mod\ p)$，则 $a·a^{p-2} \equiv 1(mod\ p)$，即 $a^{p-2}$ 是 $a$ 模 $p$ 的一个逆。

注意前提：$p$ 是一个素数，$a$ 是一个正整数且 $p \nmid a$。

通常可以用快速幂求 $a^{p-2}$。

若 $p$ 是素数，$n\lt p$，线性递推求 $1$ 至 $n$ 在模 $p$ 意义下的乘法逆元

首先，$i=1$ 的逆是 $1$。下面求 $i\gt 1$ 的逆，用递推法。

用带余除法 $p = k·i + r$，其中 $0\le r \lt i$，故 $k·i + r \equiv 0 (mod\ p)$
在等式两边乘 $i^{-1}r^{-1}$，即 $(k·i + r)·i^{-1}r^{-1} \equiv 0 (mod\ p)$，即 $kr^{-1} + i^{-1} \equiv 0 (mod\ p)$
移项得 $i^{-1}\equiv -kr^{-1} (mod\ p)$，即 $i^{-1}\equiv (-p/i)r^{-1} (mod\ p)$。若要避免负数，因 $pr^{-1} \equiv 0 (mod\ p)$，由定理 12 得，$pr^{-1} + (-p/i)r^{-1} \equiv (-p/i)r^{-1} (mod\ p)$ ，即 $(p-p/i)r^{-1} \equiv (-p/i)r^{-1} (mod\ p) $。

则 $i^{-1}\equiv (p-p/i)r^{-1} (mod\ p)$。

代码：

1
2
3
4
void inverse(LL n, LL p) {
  inv[1] = 1;
  for (int i = 2; i <= n; i++) inv[i] = (p-p/i)*inv[p%i]%p;
}

逆与除法取模

逆的一个重要应用是求除法的模。求 $(a/b) \bmod m$，即 $a$ 除以 $b$，然后对 $m$ 取模。

这里 $a$ 和 $b$ 都是很大的数，如 $a=n!$，容易溢出，导致取模出错。

用逆可以避免除法计算，设 $b$ 的逆元是 $b^{-1}$，有 $(a/b) \bmod m = ((a/b) \bmod m) ((bb^{-1}) \bmod m) = (a/b×bb^{-1}) \bmod m = (ab^{-1}) \bmod m$

经过上述推导，除法的模运算转换为乘法模运算，即

$(a/b) \bmod m = (ab^{-1}) \bmod m = (a \bmod m) (b^{-1} \bmod m) \bmod m$

习题

HDU-1576 A/B 因为 $\gcd(B,9973)=1$，可以用 exgcd 求逆元。

1
2
3
4
5
6
7
8
9
while (t--) {
  LL n, B;
  cin >> n >> B;
  LL a, b, d, x, y;
  exgcd(B, 9973, d, x, y);
  LL p = 9973;
  x = (x%p+p)%p;
  cout << n*x%9973 << endl;
}

整除