（一）定理和性质

一、裴蜀定理

如果 a,b∈N , (a,b)=d 那么一定存在 x,y 使得 d|(a∗x+b∗y)
证明：非常简单，鉴于可能有数论刚入门的OIer所以这里简单证明一下：
因为 (a,b)=d
所以我们就可以假设 a=p∗d , b=q∗d
那么 a∗x+b∗y=p∗d∗x+q∗d∗y=d∗(p∗x+q∗y) 得证

二、整除的性质

a | c, b | c, (a, b) = 1 \Rightarrow a b | c

a | b c, (a, b) = 1 \Rightarrow a | c

p | a b \Rightarrow p | a 或 p | b

正确性显然

三、同余

a \equiv b (m o d m) \Leftarrow \Rightarrow m | (a - b)

a \equiv b (m o d m), a \equiv b (m o d n) \Rightarrow a \equiv b (m o d [m, n])

(k, m) = d, k * a \equiv k * a' (m o d m) \Rightarrow a \equiv a' (m o d m d)

第二个式子证明：
(a−b)=x∗m=y∗n=k∗[m,n]

第三个式子证明：
k=q∗d,m=p∗d
k∗a−k∗a′=c∗m
a−a′=c∗mk=c∗mq∗d=cq∗md

四、逆元

如果 (b,m)=1 ,那么存在 b−1 使得 b∗b−1≡1(mod m)
P.S：这个-1次方只是表示逆元一个符号并不是真的-1次方但是可以把它当成-1次方在同余中进行运算

五、剩余系

任何m个分别属于m个剩余类的数组组成剩余系

六、φ

所有的n满足 0＜n≤m , (n,m)=1 构成了一个模m的简化剩余系，简称缩系
记录这样的n的个数为 φ(m)

七、关于缩系的一个定理

如果 (m,m′)=1 ,a取遍模m的缩系,a’取遍模m’的缩系,那么 a∗m′+a′∗m 取遍模 m∗m′ 的缩系
证明自己yy一下好啦

八、欧拉定理

如果 (a,m)=1 ,那么 aφ(m)≡1(mod m)
证明：
当x取遍模m的缩系时,ax也取遍模m的缩系（这个自己yy一下，具体证明不太会说qwq）
所以我们可以得出 ∏x≡∏a∗x(mod m)
∏a∗x≡aφ(m)∏x
用处：如果 (a,m)=1 , abmod m 可以转化成 ab mod φ(m)mod m
如果 (a,m)≠1 , ab≡amin(b mod φ(m)+φ(m),b) mod m

九、拉格朗日定理

对于一个次数为n的多项式F(x), F(x)≡0(mod p) 至多 min(n,p) 个解。

十、二次剩余

对于一个奇素数p,如果存在x使得 x2≡a(mod p) ,那么称a为p的二次剩余。
如果 ap−12≡1(mod p) ,那么a为p的二次剩余。
如果 ap−12≡−1(mod p) ,那么a为p的二次非剩余。

十一、威尔逊定理

(p−1)!≡−1(mod p)
证明：2到p-2这些数都存在逆元，可以两两匹配

十二、阶

如果 (a,m)=1 那么记x为最小的正整数使得 ax≡1(mod m)
结论： x|φ(m)
证明：反证法，设有一个最小的x , φ(m)=q∗x+r ,
则 aq∗x+r≡1(mod m)
ax≡1(mod m) 推出 ar≡1(mod m)
因为x是最小的满足条件的正整数 , r<x ,所以 r=0

十三、原根

如果 g(mod m) 的阶为 φ(m) 那么g为m的原根
g0,g1,…,gφ(m)−1 构成了模m的缩系。
只有 1,2,4,pa,2pa 存在原根。

十四、其他

φ(p∗e)=(p−1)∗p∗e−1
φ(m)=m∗∏p|m(1−1/p) (容斥原理求φ)

（二）算法

一、辗转相除法

直接贴代码吧，证明网上有详解，这里不再赘述

int gcd(int a,int b)
{
    if (b==0) return a;
    else return gcd(b,a%b); 
}

二、扩展欧几里得算法

用处：求解形如 a∗x+b∗y=gcd(a,b) 的二元方程和线性同余方程
( a∗x≡b(mod m) 等价于 a∗x+m∗y=b )
推导：假设解出一组解 (p,q)
p∗a+q∗b=gcd(a,b)
= gcd(b,a mod b)=p∗b+q∗(a mod b)=p∗b+q∗(a−(ab)∗b)
= p∗b+q∗a−q∗(ab)∗b=(p−q∗(ab))∗b+q∗a
代码

int extended_gcd(int a,int b,int &x,int &y)
{
    int ret,tmp;
    if (!b)
    {
        x=1;y=0;return a;
    }
    ret=extended_gcd(b,a%b,x,y);
    tmp=x;
    x=y;
    y=tmp-a/b*y;
    return ret;
}

一个神奇的小结论：
对方程 a∗x+b∗y=c ，一组整数解为 (x0,y0) ，
则它的任意整数解可以写成 (x0+k∗b′,y0−k∗a′) ,其中 a′=agcd(a,b) ， b′=bgcd(a,b)
证明：
如果我们现在有解 (x1,y1) ，任取另外一组解 (x2,y2) ，则
a∗x1+b∗y1=a∗x2+b∗y2=gcd(a,b)
变形可以得到 a∗(x1–x2)=b∗(y2–y1)
两边同时除以 gcd(a,b)
得到 a′∗(x1–x2)=b′∗(y2–y1)
因为 (a′,b′)=1 ，所以 (x1−x2) 一定是b’的倍数
取 x1−x2=k∗b′ ,得 y2−y1=k∗a′

三、求逆元

由于 aφ(m)≡1(mod m) 那么 a−1≡aφ(m)−1(mod m)
如果m为素数，那么答案为 am−2
否则解线性同余方程

四、线性求1到n的逆元

设 f(i)=i! mod p,g(i)=i!−1 mod p
g(i)=g(i+1)∗(i+1)
i−1=f(i−1)∗g(i)
算出 fn 然后求出 fn 的逆元 gn ，递推即可。

五、线性同余方程组（CRT）

形如 x≡ai(modmi)
解法：增量法
假设一开始的方程 x≡a1(mod p1),x≡a2(mod p2)
那么有 p1t+a1≡a2(mod p2)
p1t≡a2−a1(mod p2)
p1t+p2y=a2−a1
可以通过扩欧解出一个解 t0
t≡t0(mod p2gcd(p2,p1)) (通过扩欧的小结论得出)
x0=p1t0+a1
x≡x0(mod lcm(p1,p2)) 满足左边等式的x都是这两个方程符合条件的解
然后加入下一个方程

六、求n!中p的指数

∑i≥1⌊npi⌋
还有一个O(1)求的公式（可以用于一些奇怪的数位dp）
n−f(n)p−1
f(n) 表示 n在p进制下的数位和
然而公式怎么推的并不会。。。

七、组合数

n,m较小的话 C(n,m)=C(n−1,m)+C(n−1,m−1) 递推即可（NOIP2017提高组DAY2T1！！！当时就因为不知道递推式吃了亏）
n,m较大的话暴力用 f(n)∗g(m)∗g(n−m) 求就可以（f,g定义参考线性求1到n逆元里的定义）
还有一种更快的方式求组合数想学习一下的人百度Lucas定理
这里给出公式：
C(n,m)%p=C(n%p,m%p)∗C(np,mp)%p

八、求阶

暴力枚举1到φ(m)判断即可

九、求原根

从小到大枚举g然后暴力判断即可

十、指数方程

① ax≡b(mod m)
如果m为素数：
使用BSGS（baby-step giant-step）解决
令 x=qt−r ( t一般取根号下m上取整)
则 aqt≡b∗ar(mod m)
从0-m 枚举r 算出 b∗ar 的值填入一个哈希表中
从1-m 枚举q 算出 aqt 的值，在哈希表中检索
如果m不是素数：
提取公因数直到 gcd(a,m)=1
可能大家不理解
举个栗子：
假设我们要解一个方程 8x≡16(mod 24)
8和24不互质
所以我们先提取一个8
变成 8∗8x−1≡16(mod 24)
然后约一下变成 8x−1≡2(mod 3)
最后用BSGS求解得x=2
如果 (a,m)≠(a,m,b) 的话无解
② xa≡b(mod m)
如果m为素数：
如果 gcd(a,φ(m))=1 ,那么求出a模φ(m)的逆元 a−1
xa∗a−1≡x≡ba−1(mod m)
直接解x即可
否则：
先求出m的原根g
解出一个s符合 gs≡b(mod m)
假设 x=gt
那么 gat≡gs(mod m)
由原根的性质得到： at≡s(mod φ(m))
解出t即可
如果m不为素数：
分解m然后用CRT合并
当出现2^n时，因为它没有原根，所以说枚举答案即可

十一、二次剩余

形如 x2≡b(mod p)
判断一个数是不是另一个数的二次剩余，只需要计算 bp−12%p 是否等于1即可
复杂度O(p)
还有一种O(log n)的算法叫做cipolla’s algorithm，然而我并不会这种算法，而且这种算法貌似非常冷门，只有维基百科上才能查到…
至于二次剩余的用处嘛…据说可以用来卡常数

十二、Miller-rabin

一个判断一个数是不是素数的算法
并不会写…直接背代码就好2333

十三、Pollard-rho

分解质因数
也不会写…也可以直接背代码QwQ

（三）数论函数

一、积性函数

对于 gcd(a,b)=1 ,如果 f(a∗b)=f(a)∗f(b) 那么f(x) 为积性函数
常见的积性函数 d(x),σ(x),id(x),e(x),l(x),μ(x)
d(x)=∑a|x1
σ(x)=∑a|xa
id(x)=x
l(x)=1
e(x)=1(x=1)
e(x)=0(x≠1)

二、狄利克雷卷积

两个数论函数 f(x),g(x) ,令 h=f∗g
则 h(x)=∑a|xf(a)g(xa)
几条性质：
①卷积满***换律，结合律。
②两个积性函数的卷积还是积性函数
③ f∗e=f

三、莫比乌斯函数

μ(n)=−1k (k为n分解质因数后不同质因数的个数)
如果n有平方因子那么 μ(n)=0
如何 n=1 那么 μ(n)=1
μ∗l=e
即 ∑d|nμ(d)=e(n) （这个结论大家自己想一下，可以借助杨辉三角辅助理解）

四、莫比乌斯反演

1.如果 F(n)=∑d|nf(d) 那么 f(n)=∑d|nμ(d)∗F(nd)
推导：
F=f∗l
F∗μ=f∗l∗μ=f∗e=f
2.如果 F(n)=∑n|df(d) 那么 f(n)=∑n|dμ(dn)∗F(d)

五、线性筛素数

思想：每个合数只被它最小的素因子访问到
代码：

void get_prim(int n)
{
    vis[1]=1;
    for (int i=2;i<=n;i++)
    {
        if (!vis[i])
        {
            cnt++;prim[cnt]=i;
        }
        for (int j=1;j<=cnt&&i*prim[j]<=n;j++)
        {
            vis[i*prim[j]]=1;
            if (i%prim[j]==0) break;  //看不懂这一步的去重新理解思想
        }
    }
}

扩展：通过线性筛可以线性求出一个积性函数的值。

欢迎各位神犇前来交流qwq

基础数论入门