数论学习笔记（一）：同余相关

orange_new · 2024-07-25 09:07:39 · 算法·理论

一、最大公约数

定义

不全为 0 的整数 a, b 的最大公约数是指能够同时整除 a 和 b 的最大整数。

欧几里得算法(gcd)

gcd是用来求解两个整数的最大公约数

定理1.2.1

对于整数 a, b, m, n，若 c \mid a，c \mid b，则 c \mid (ma + nb)

证：\because c \mid a，c \mid b

设 a = ce，b = cf

定理1.2.2

若 a, b, c 是整数，则 \gcd(a + cb, b) = \gcd(a, b)

证：设 \gcd(a, b) = d，根据定理1.2.1，d \mid (a + cb)

反过来，设 \gcd(a + cb, b) = e，根据定理1.2.1，e \mid [(a + cb) - cb] = a

解法

令整数 r_0 = a，r_1 = b 满足 a \geq b > 0，如果连续做带余除法得到 r_j = r_{j + 1}q_{j + 1} + r_{j + 2}，且 r_{j + 2} = 0，那么 \gcd(a, b) = r_{j + 1}

正确性证明：通过连续的带余除法可以得到：

根据定理1.2.2，\gcd(a, b) = \gcd(r_0, r_1) = \gcd(r_1, r_2) = \dots = (r_{n - 1}, r_n) = (r_n, 0)，因此 \gcd(a, b) = r_n

裴蜀定理

定理1.3.1

对于两个不全为 0 的整数，\gcd(a, b) 是 a, b 的线性组合中最小的一个。

证：设 d 为 a, b 的线性组合中最小的一个，设 d = ma + nb，a = dq + r(0 \leq r < d)

假设 a, b 还有公因数 c

设 c = de，那么 c = de = (as + bt)e = a(se) + b(te)

扩展欧几里得算法(exgcd)

求 ax + by = gcd(a, b) 的特解关键在于递归的思想

现在已知 \gcd(a, b) = \gcd(b, a \bmod b)

因此 ax + by = bx' + (a \bmod b)y' = bx' + (a - b \times \lfloor\frac{a}{b}\rfloor)y' = ay' + b(x' - \lfloor\frac{a}{b}\rfloor y')

先一层层递归，回溯时求解原方程的解。

exgcd代码：

int extend_gcd(int a, int b, int &x, int &y){
    if(b == 0){
        x = 1;
        y = 0;//递归边界
        return 0;
    }
    int d = extend_gcd(b, a % b, y, x);//递归
    y -= a / b * x;//回溯
    return d;
}

二、素数

定义

素数是大于 1 的正整数，并且除了 1 和它本身外不能被其他正整数所整除，素数又被称作质数。

大于 1 的不是素数的正整数称为合数。

筛法求素数

下面给出两种可以在线性时间内筛出 1 到 n 之间的素数的方法。

埃拉托色尼斯筛法

首先，一个正整数的倍数一定是合数。

如果一个数是合数，那他一定能表示成比他小的数的倍数。

我们考虑用已经筛出的素数的倍数表示合数。

从 2 开始，如果这个数没有被标记过，那么将这个数标记为素数，他的倍数都标记为合数。

这个方法被称作埃拉托色尼斯筛法，简称埃氏筛，复杂度 O(n \log \log n)

复杂度证明：设 \pi(n) 表示小于等于 n 的素数个数，p_k 表示这 \pi(n) 个数中第 k 小的数。

在 1 到 n 的数中，一个素数最多会筛出 \displaystyle\frac{n}{p_k} 个合数，因此总复杂度为 O(\displaystyle\sum_{k=1}^{\pi(n)}\frac{n}{p_k}) = O(n \sum_{k=1}^{\pi(n)}\frac{1}{p_k})

设 n 的唯一分解是 \displaystyle\prod_{i=1}^m p_i^{c_i}

记 \omega(n) 表示 n 本质不同的质因子个数，即 \displaystyle\sum_{p \in \mathbb{P}, p \leq n} [p \mid n]

记 d(n) 表示 n 的因数个数，即 \displaystyle\sum_{d \leq n} [d \mid n]，从唯一分解的角度考虑，枚举每个素数的个数，那么有 d(n) = \displaystyle\prod_{i=1}^m(c_i + 1)

中置知识：下凸函数

如果一个函数 f(x) 的一阶导单调递增，二阶导单调不下降，那么这个函数就是一个下凸函数，可以看作 f(x) 在增加，他的斜率也在增加，如图：

![]()

就是一个下凸函数。

设 f(x) = n^x(n ＞ 1)

不等式成立。

完整代码：P3383 【模板】线性筛素数

#include<bits/stdc++.h>
using namespace std;
const int PP = 1e8 + 9;
int prime[PP], p_cnt;
bool isPrime[PP];
void getPrime(int n){
    for(int i = 2; i < n; ++i)
        isPrime[i] = true;
    for(int i = 2; i < n; ++i){
        if(isPrime[i]){//一个数没被标记过
            prime[++p_cnt] = i;//记录素数
            if(1ll * i * i < n)//防止越界
                for(int j = i * i; j <= n; j += i)//根据合数i的最小质因子小于等于sqrt(i)，可以从i*i开始筛，优化常数
                    isPrime[j] = false;//他的倍数标记为合数
        }   
    }
}
signed main(){
    int n, q;
    scanf("%d%d", &n, &q);
    getPrime(n);
    while(q--){
        int x;
        scanf("%d", &x);
        printf("%d\n", prime[x]);
    }
    return 0;
}

欧拉筛法

埃氏筛十分优秀，但每个数会被它的所有质因子都筛一遍，而使用欧拉筛可以使每个数只被它的最小质因子筛一遍，时间复杂度可以达到 O(n)

每找到一个没被标记的数，就将它记为素数，无论他是不是素数，都将它与已求出的素数相乘并将他标记为合数。

当遇到一个素数能整除当前的数，证明当前的数已经被这个素数标记过了，他乘其它质数也已经被这个质数标记了，就可以退出循环了。

完整代码：P3383 【模板】线性筛素数

#include<bits/stdc++.h>
using namespace std;
const int PP = 1e8 + 9;
int prime[PP], p_cnt;
bool isPrime[PP];
void getPrime(int n){
    for(int i = 2; i < n; ++i)
        isPrime[i] = true;
    for(int i = 2; i < n; ++i){
        if(isPrime[i])
            prime[++p_cnt] = i;
        for(int j = 1; j <= p_cnt && i * prime[j] < n; ++j){
            isPrime[i * prime[j]] = false;//将prime[j]的第i倍标记为合数
            if(i % prime[j] == 0)//因为prime数组从小到大排列，因此prime[j]一定是i的最小质因子，i乘其它质数一定会被prime[j]先筛掉，因此不用往后再筛了
                break;
        }
    }
}
signed main(){
    int n, q;
    scanf("%d%d", &n, &q);
    getPrime(n);
    while(q--){
        int x;
        scanf("%d", &x);
        printf("%d\n", prime[x]);
    }
    return 0;
}

欧拉函数

有数学的地方就有欧拉——《公式之美》

前置知识：积性函数

若对于任意正整数 a, b，\gcd(a, b) = 1，都有 f(ab) = f(a)f(b)，则称 f 为积性函数。

若对于任意正整数 a, b，都有 f(ab) = f(a)f(b)，则称 f 为完全积性函数。

定义

欧拉函数 \varphi(n) 表示不超过 n 且与 n 互质的数的个数，这 \varphi(n) 个数组成的集合也构成了 n 的既约剩余系。

欧拉函数的性质

1.若 p 是素数，则 \varphi(p) = p - 1；反过来，若 \varphi(p) = p - 1，则 p 是素数。

证：若 p 是素数，那么任意小于 p 的素数都与 p 互质。因为有 p - 1 个这样的正整数，所以 \varphi(p) = p - 1

反过来，如果 p 不是素数，那么 p = 1 或 p 是合数。若 p = 1，那么 \varphi(1) = 1 \neq 0。若 p 是合数，那么一定存在正整数 d 使得 1 < d < p 且 d \mid p，显然 p 和 d 不互质，这说明 1 到 p - 1 至少有一个数与 p 不互质，则 \varphi(p) \leq n - 2。因此，如果 \varphi(p) = p - 1，那么 p 是素数。

2.对于素数 p，正整数 a，\varphi(p^a) = p^a - p^{a - 1}

证：不超过 p^a 且与 p^a 不互质的数就是那些不超过 p^a 且能被 p 整除的数：p, 2p, 3p, \dots, (p - 1)p, p^2, 2p^2, 3p^3 \dots (p - 1)p^{a - 1}, p^a，一共有 p^{a - 1} 个，所以有 p^a - p^{a - 1} 个不超过 p 数与 p 互质，因此 \varphi(p^a) = p^a - p^{a - 1}

3.(积性函数) 对于任意正整数 a, b，若 \gcd(a, b) = 1，那么 \varphi(ab) = \varphi(a)\varphi(b)

证：用下列方式列出不超过 ab 的正整数：

假设 r 是不超过 m 的正整数且 \gcd(r, m) = d \neq 1，那么第 r 行的数都可以写成 km + r 形式

4.(通项公式) 设 n 的唯一分解是 \displaystyle\prod_{i=1}^m p_i^{c_i}，那么 \varphi(n) = n\displaystyle\prod_{i=1}^m(1 - \frac{1}{p_i})

证：根据性质3，\varphi 是积性函数。

根据性质2，\varphi(p_i^{c_i}) = p_i^{c_i} - p_i^{c_i - 1} = p_i^{c_i}(1 - \displaystyle\frac{1}{p_i})

5.(欧拉反演) 若 n 为正整数，则 \displaystyle\sum_{d \mid n}\varphi(d) = n

证：将 1 到 n 的整数构成的集合进行分类，如果整数 m 与 n 的最大公因数为 d，那么 m 属于 C_d 集合。

现在我们将 1 到 n 之间的整数划分成了若干个不相交的集合，且每个数只存在在一个集合中所以这些不同的集合所含整数的个数和就是 n

因为 d 遍历了所有 n 的因子，n / d 也便利了所有 n 的因子。

6.若 a \mid b，则 \varphi(ab) = a \times \varphi(b)

证：\because a \mid b

线性筛欧拉函数

首先，对于一个素数 p，\varphi(p) = p - 1

利用欧拉筛

• 如果 prime[j] \mid i，根据性质6，有 \varphi(i \times prime[j]) = \varphi(i) \times prime[j]

• 如果 prime[j] \nmid i，因为 \prime[j] 为素数，因此 gcd(prime[j], i) = 1，根据性质3，有 \varphi(i \times prime[j]) = \varphi(i) \times \varphi(prime[j])

线筛代码：

const int N = 4e6 + 9;
int vis[N], prime[N], phi[N], sum[N], n;
void get_phi(){
    phi[1] = 1;
    int cnt = 0;
    for(int i = 2; i < N; i++){
        if(!vis[i]){
            vis[i] = i;
            prime[cnt++] = i;
            phi[i] = i - 1;//素数
        }
        for(int j = 0; j < cnt; j++){
            if(i * prime[j] > N)
                break;
            vis[i * prime[j]] = prime[j];
            if(i % prime[j] == 0){
                phi[i * prime[j]] = phi[i] * prime[j];//非素数情况1
                break;
            }
            phi[i * prime[j]] = phi[i] * phi[prime[j]];//非素数情况2
        }
    }
}

三、同余

定义

对于整数 a, b，正整数 m，若 m \mid (a - b)，则称 a 和 b 模 m 同余，正整数 m 成为同余的模，记作 a \equiv b \pmod m

同余的性质

1.自反性： a \equiv a \pmod m

证：\because m \mid (a - a) = 0

证：\because a \equiv b \pmod m

设 km = a - b

证：\because a \equiv b \pmod m，b \equiv c \pmod m

设 km = a - b，lm = b - c

设 km = a - b，lm = c - d

证：\because a \equiv b \pmod m，c \equiv d \pmod m

设 km = a - b，lm = c - d

可除性前置一：若 a, b, m, n 为整数，且 c \mid a，c\mid b，则 c \mid (ma + nb)

证：\because c \mid a，c\mid b

设 a = ce, b = cf(c, e \in Z)

可除性前置二：若 a, b, c 为正整数，且 \gcd(a, b) = 1，a \mid bc，则a \mid c

证：\because \gcd(a, b) = 1

根据可除性前置一，a \mid acx + bcy

证：\because ac \equiv bc \pmod m

设 km = c(a - b)，两边同时除以 \gcd(m, c)，得：(c / \gcd(m, c))(a - b) = k(m / \gcd(m, c))

可除性推论：若 a,b,c 是整数，m 是正整数，\gcd(c, m) = 1，ac \equiv bc \pmod m，则 a \equiv b \pmod m

费马小定理

内容

对于质数 p，正整数 a，若 \gcd(a, p) = 1，则 a^{p - 1} \equiv 1 \pmod p

费马小定理也通常被写作 a^p \equiv a \pmod p (可乘性)

证明

证明：考虑数学归纳法

首先 1^{p - 1} \equiv 1 \pmod p (显然成立)

假设对于正整数 x 满足 \gcd(x, p) = 1，有x^{p - 1} \equiv 1 \pmod p

设 (-k)p = ax - 1

移项得：ax + kp = 1

模板：

#include <bits/stdc++.h>
using namespace std;
int extend_gcd(int a, int b, int &x, int &y){
    if(b == 0){
        x = 1;
        y = 0;
        return 0;
    }
    int d = extend_gcd(b, a % b, y, x);
    y -= a / b * x;
    return d;
}
int mod_inverse(int a, int m){
    int x, y;
    extend_gcd(a, m, x, y);
    return (x % m + m) % m;
}
int n, p;
int main(){
    scanf("%d%d", &n, &p);
    printf("%d", mod_inverse(n, p));
    return 0;
} 

递推求逆元

当我们要求 [1 \dots n] 之间所有数在模 p 意义下的逆元，此时可以用递推求出。

首先，1 在模 p 意义下的逆元还是 1

对于 a \neq 1 的情况，设 k = \lfloor\displaystyle\frac pi \rfloor，j = p \bmod i (i, j, k \in N^+)

两边同乘 i^{-1} \times j^{-1} (x^{-1} 表式 x 在模意义下的逆元)，得：

把每个数乘 a 再对 p 取模，得 ax_1 \bmod p, ax_2 \bmod p, \dots , ax_{\varphi(p)} \bmod p

假设 ax_1 \bmod p = ax_2 \bmod p，即 ax_1 = ax_2 \pmod p

定理3.5.1

对于整数 a, b，正整数 m，设 \gcd(a, m) = d，若 d \nmid b，则 ax \equiv b \pmod m 无解，若 d \mid b，则 ax \equiv b \pmod m 恰好有 d 个模 m 不同余的解。

证：\because ax \equiv b \pmod m

设 my = ax - b

移项得：ax - my = b

整数 x 是 ax \equiv b \pmod m 的解当且仅当存在 y 使得 ax - my = b，由裴蜀定理可得，若 d \nmid b，则无解，而 d \mid b 时，ax - my = b 有无穷多解:x = x_0 + (m / d)t，y = y_0 + (a / d) t

其中 x = x_0 和 y = y_0 是方程的特解，上述 x 的值是 ax \equiv b \pmod m 的解，有无穷多这样的解。

设两个解 x_1 = x0 + (m / d)t_1，x_2 = x_0 + (m / d)t_2，假设这两个解在模 m 意义下同余，则：x_0 + (m / d)t_1 \equiv x_0 + (m / d)t_2 \pmod m

证：若 a \equiv 1 \pmod p 或 a \equiv 1 \pmod p，则 a^2 \equiv 1 \pmod p，所以 a 是其自身在模 p 意义下的逆元。

反过来，若 a 是其自身在模 p 意义下的逆元，则 a ^ 2 \equiv 1 \pmod p

当 p \geq 3 时，根据定理3.5.1推论可得，对于 a(a \in [1,p) 且 a \in Z)，存在 a^{-1}(a^{-1} \in [1,p) 且 a^{-1} \in Z)，使得 a^{-1}a \equiv 1 \pmod p

根据定理3.5.2可得，在小于 p 的正整数中，在模 p 意义下的逆元是其本身的数只有 1 和 p - 1

将同余式两边同乘 1 和 p - 1，得：(p - 1)! = 1 \times 2 \times 3 \times \dots \times (p - 3) \times (p - 2) \times (p - 1) \equiv -1 \pmod p

威尔逊定理逆定理

内容

对于正整数 n，n \geq 2，若 (n - 1)! \equiv -1 \pmod n，则 n 是素数。

定理3.5.3

对于整数 a, b, c，若 a \mid b，b \mid c，则 a \mid c

证：\because a \mid b，b \mid c

设 b = ae，c = bf

证明

假设 n 是一个合数，且 (n - 1)! \equiv -1 \pmod n

假设 n = ab(a, b \in Z 且 a, b \in (1, n))

证：

解法

解：令 M = p_1 \times p_2 \times \dots \times p_n，M_i = \displaystyle\frac{M}{m_i}

通解 x = \displaystyle\sum_{i=1}^na_iM_iM_i^{-1} + kM(k \in Z)

四、原根

前置知识：阶

定义

对于整数 a(a \neq 0)，正整数 n，\gcd(a, n) = 1，使得 a^x \equiv 1 \pmod n 成立的最小正整数 x 称为 a 模 n 的阶，记为 \operatorname{ind}_na

阶的性质

1.对于整数 a(a \neq 0)，正整数 n，\gcd(a, n) = 1，那么正整数 x 是同余方程 a^x \equiv 1 \pmod n 的一个解当且仅当 \operatorname{ind}_na \mid x

证：若 \operatorname{ind}_na \mid x，则 x = k\operatorname{ind}_na \mid x(k \in N^+)

反过来，若 a^x \equiv 1 \pmod n，设 x = q\operatorname{ind}_na + r(0 \leq r < \operatorname{ind}_na)

2.对于整数 a(a \neq 0)，正整数 n，\gcd(a, n) = 1，那么 a^i \equiv a^j \pmod n(i, j \in N) 当且仅当 i \equiv j \pmod{\operatorname{ind}_na}

证：若 i \equiv j \pmod{\operatorname{ind}_na} 且 0 \leq j \leq i，设 i = j + k\operatorname{ind}_na(k \in N^+)

反过来，若 a^i \equiv a^j \pmod n 且 i \geq j

原根

定义

对于整数 a(a \neq 0)，正整数 n，\gcd(a, n) = 1，当 \operatorname{ind}_na = \phi(n) 时，称 a 是模 n 的原根或者 n 的原根，并且我们称 n 有一原根。

定理4.2.1

对于整数 a, b，正整数 k, m，若 a \equiv b \pmod m，则 a^k \equiv b^k \pmod m

证：\because a \equiv b \pmod m

原根的存在性

1.设 p 是一个素数且 d 是 p - 1 的一个正因子，那么模 p 的阶为 d 且不同余的整数的个数为 \varphi(d)

证：设 F(d) 表示小于 p 且模 p 的阶为 d 的正整数的个数。

原根的存在性1推论：每个素数都有原根

2(扩展).如果正整数 n 不是一个素数的幂或者不是一个素数的幂的两倍(幂可以为 0)，那么 n 不存在原根。

证：设 n 的唯一分解是 \displaystyle\prod_{i=1}^m p_i^{c_i}，假设 n 有一个原根 r，即存在一个正整数 r 使得 \gcd(r, n) = 1 且 \operatorname{ind}_nr = \varphi(n)

设 U = \operatorname{lcm}(\varphi(p_1^{c_1}), \varphi(p_2^{c_2}), \dots, \varphi(p_m^{c_m}))

证：设 s = \operatorname{ind}_n(a^u), v = \gcd(t, u), t = t_1v, u = u_1v

定理4.2.2推论：若 r 是 n(n > 1) 的原根，则 r^u 是 n 的原根当且仅当 \gcd(u, \varphi(n)) = 1

定理4.2.3

对于正整数 r, n，\gcd(n, r) = 1，若 r 是 n 的一个原根，则 r, r^2, \dots, r^{\varphi(n)} 构成了模 n 的既约剩余系。

证：\because \gcd(r, n) = 1

设 k 是一个整数且 1 \leq k \leq n