打死没想到会在H老师处学懂数论

同余，整除
模运算
埃式筛法
欧拉筛法
最大公约数和最小公倍数
辗转相除法
更相减损术
裴蜀定理
威尔逊定理
费马定理
同余等价类、剩余系、缩系
欧拉函数
欧拉定理
扩展欧拉定理
区间逆元
扩展欧几里得
中国剩余定理
扩展中国剩余定理
利用以上所有知识进行证明

同余，整除

整除的性质：

传递性：若 $a ∣ b, b ∣ c$ ，则 $a ∣ c$

$a ∣ b, a ∣ c$ 等价于对于任意的整数 $x, y$ ，有 $a ∣ (b x + c y)$

设 $m \neq = 0$ ，则 $a ∣ b$ 等价于 $m a ∣ m b$

设整数 $x, y$ 满足 $a x + b y = 1, a ∣ n, b ∣, n$ ，则 $(a b) ∣ n$

若 $b = q * d + c$ ，则 $d ∣ b$ 的充要条件是 $d ∣ c$

同余的性质：

同加性：若 $a≡b(modp)a\equiv b(mod\ p)$ ，则 $a+c≡b+c(modp)a+c\equiv b+c(mod\ p)$

同减性：若 $a≡b(modp)a\equiv b(mod\ p)$ ，则 $a−c≡b−c(modp)a-c\equiv b-c(mod\ p)$

同乘性：若 $a≡b(modp)a\equiv b(mod\ p)$ ，则 $a×c≡b×c(modp)a\times c\equiv b\times c(mod\ p)$

同除性：若 $a≡b(modp),c∣a,c∣b,(c,p)=1a\equiv b(mod\ p),c|a,c|b,(c,p)=1$ ，则 $a/c≡b/c(modp)a/c\equiv b/c(mod\ p)$

同幂性：若 $a≡b(modp),c>0a\equiv b(mod\ p),c>0$ ，则 $ac≡bc(modp)a^c\equiv b^c(mod\ p)$

若 $a%p=x,a%q=x,(p,q)=1a\% p=x,a\% q=x,(p,q)=1$ ，则 $a%(p∗q)=xa\% (p*q)=x$

数论常识：

若2能整除a的最末位，则 $2 ∣ a$

若4能整除a的末两位，则 $4 ∣ a$

若8能整除a的末三位，则 $8 ∣ a$

若3能整除a的各位数字之和，则 $3 ∣ a$

若9能整除a的各位数字之和，则 $9 ∣ a$

若11能整除a的偶数位数字之和与奇数位数字之和的差，则 $11 ∣ a$

能被 $7, 11, 13$ 整除的数的特征是：这个数的末三位与末三位以前的数字所组成数之差能被 $7, 11, 13$ 整除

模运算

1.分配率

$(a+b)%c=(a%c+b%c)%c(a+b)\% c=(a\% c+b\% c)\% c$

$(a−b)%c=(a%c−b%c)%c(a-b)\% c=(a\% c-b\% c)\% c$

$(a×b)%c=(a%c×b%c)%c(a\times b)\% c=(a\% c\times b\% c)\% c$

$a^b)\% c=(a\% c)^b\% c$

2.放缩性

如果 $a%b=c,d≠0a\% b=c,d≠0$ ，则有 $(a×d)%(b×d)=c×d(a\times d)\%(b\times d)=c\times d$

如果 $a%b=c,d∣a,d∣ba\%b=c,d\bigg|a,d\bigg|b$ ，则 $(a/d)%(b/d)=(c/d)(a/d)\%(b/d)=(c/d)$

根据放缩性，则除法取余有式子 $a/b%c=a%(b×c)/ba/b\%c=a\%(b\times c)/b$

埃式筛法

先把 $n$ 以内的 $2$ 的倍数(不包含 $2$ )全部删除，再把 $n$ 以内的 $3$ 的倍数(不包含 $3$ )全部删除，…

这样做下去，最后剩下的以内的数全为质数

这里的删除其实不是真的删除，只是打上一个删除标记而已

每个数都会被它的质因子打一次标记，而一个数的不同的质因子个数不超过 $l o g N$

所以时间复杂度为 $O (N l o g N)$

void getprime( int n ) {for( int i = 2;i <= n;i ++ ) {if( flag[i] ) continue;prime[++ cnt] = i;for( int j = i;j <= n / i;j ++ )flag[j * i] = 1;}
}

欧拉筛法

在上述的埃氏筛法中，一个数可能被它的各个质因子都筛了一遍

而一个数的质因子种类数是不会超过 $l o g N$ 的,所以时间复杂度为 $O (N l o g N)$

而欧式筛法保证每个数只被它的最小质因子筛一遍，这样，时间复杂度便降成了 $O (N)$

有一个质数集合 $S$ ，一开始，质数集合为空

同时有一个 $b o o l$ 数组 $f l a g$ ，表示删除标记

有两层循环：

外层循环从 $2$ 开始枚举倍数，设当前枚举的量为 $a$

如果 $a$ 是质数，则将 $a$ 加入质数集合

内层循环枚举质数集合中的元素，将数组中它们的 $a$ 倍全部打上删除标记

显然，未打删除标记的数都是质数了（ $f l a g$ 数组中下标小于 $2$ 的元素是无效的，不用考虑）

但现在的时间复杂度仍然是 $O (N l o g N)$ 的，接下来，要用一个优化来完成 $O (N)$ 的蜕变

设当前倍数为 $a$ ，在内层循环中，设当前枚举到集合 $S$ 中的第 $i$ 个质数 $p_i$

先将 $i*p_i$ 打上标记

如发现 $i$ 是 $p_i$ 的倍数时

此时后续的质数就无需再枚举了，可以提前退出内层循环

外层循环处理下一轮，即 $a + +$

为什么满足这种条件就可以提前 $b r e a k$ 呢？

设后续的质数为 $p_i'$ ，而 $p_i'>p_i$

因为 $a$ 是 $p_i$ 的倍数，那么 $a×pi′a\times p_i'$ 也是 $p_i$ 的倍数

设 $a×pi′=b×pia\times p_i'=b\times p_i$

$p_i'>p_i$

$∴ b > a$

我们希望每个数被它的最小质因子给删掉

所以 $a×pi′a\times p_i'$ 应该被 $p_i$ 删掉（就要求 $a×pi′/pia\times p_i'/p_i$ 尽量大）

所以后续所有的质数就都留给倍数 $a$ 增长到 $b$ 再去处理了

void sieve( int n ) {for( int i = 2;i <= n;i ++ ) {if( ! flag[i] ) prime[++ cnt] = i;for( int j = 1;j <= cnt && i * prime[j] <= n;j ++ ) {flag[i * prime[j]] = 1;if( i % prime[j] == 0 ) break;}}
}

最大公约数和最小公倍数

$gcd(a,b)×lcm(a,b)=a∗bgcd(a,b)\times lcm(a,b)=a*b$

证明：
将 $a, b$ 进行质因子分解，设 $a, b$ 的质因子集合并集为 $p_1,p_2,p_3…p_k$
$设a=p1i1p2i2…pkik,(0≤i1,0≤i2…0≤ik)设a=p_1^{i_1}p_2^{i_2}…p_k^{i_k},(0≤i_1,0\le i_2…0\le i_k)$
$设b=p1j1p2j2…pkjk,(0≤j1,0≤j2…0≤jk)设b=p_1^{j_1}p_2^{j_2}…p_k^{j_k},(0\le j_1,0\le j_2…0\le j_k)$
$gcd(a,b)=p_1^{min(i_1,j_1)}p_2^{min(i_2,j_2)}…p_k^{min(i_k,j_k)}$
$lcm(a,b)=p_1^{max(i_1,j_1)}p_2^{max(i_2,j_2)}…p_k^{max(i_k,j_k)}$
$min(i_t,j_t)+max(i_t,j_t)=i_t+j_t$
$gcd(a,b)+lcm(a,b)=p_1^{i_1+j_1}p_2^{i_2+j_2}…p_k^{i_k+j_k}$

辗转相除法

$gcd(a,b)≡gcd(b,a%b)gcd(a,b)\equiv gcd(b,a\%b)$

证明：
设 $d = g c d (a, b), a = x * d, b = y * d$

根据模运算的放缩性有： $a%b=(x∗d)%(y∗d)=(x%y)∗da\%b=(x*d)\%(y*d)=(x\%y)*d$

$∵ (x, y) = 1$

$∴(y,x%y)=1∴(y,x\%y)=1$

int gcd( int x, int y ) {if( ! y ) return x;else return gcd( y, x % y );
}

时间复杂度 $O(log⁡)O(\log)$ ，最坏情况就是斐波拉契数列，相当于相邻两位一位一位移动（辗转相减）

辗转相减法：

$g c d (a, b) = g c d (b, a - b), a > b$

证明：

令 $a=Ad,b=Bd,(A,B)=1→(a,b)=da=Ad,b=Bd,(A,B)=1\rightarrow (a,b)=d$

则 $a - b = (A - B) d$

若 $gcd(b,a−b)=gcd(Bd,(A−B)d)≠dgcd(b,a-b)=gcd\bigg(Bd,(A-B)d\bigg)≠d$

说明 $g c d (B, A - B) > 1$

令 $g c d (B, A - B) = g, B = s g, A - B = t g$

则一定有 $g∣Ag\bigg|A$

与 $(A, B) = 1$ 矛盾，所以 $g c d (B, A - B) = 1$

更相减损术

若约分 $ab\frac{a}{b}$
如 $a, b$ 均为偶，可先将 $a, b$ 折半，即 $/ 2$
否则，将 $a, b$ 交替的减去对方
直到最后两数相等，此时的数乘上先前除掉的 $2$ 即为原来 $a, b$ 的最大公约数

裴蜀定理

如果 $a, b$ 的最大公约数为 $d$ ，且 $d∣cd\bigg|c$ ，则存在整数 $x, y$ ，使得 $a x + b y = c$

证明：

转化证明存在 $x, y$ 使得 $a x + b y = d$

假设存在这样一对 $x, y$ ，那么只需将其进行倍数放缩即可

$∵ (a, b) = d$

$∴$ 设 $a^{'} = a / d, b^{'} = b / d$

则有 $a^{'} x + b^{'} y = 1, (a^{'}, b^{'}) = 1$

证明转化为求一对 $x, y$ ，使得 $a^{'} x + b^{'} y = 1$ ，且满足 $(a^{'}, b^{'}) = 1$

即求证 $a′x%b′=1a'x\%b'=1$ （感性理解：若干倍的 $a^{'}$ 减去若干倍的 $b^{'}$ 等于 $1$ ）

引理一

如果 $a, b$ 为正整数，且 $a, b$ 互质，则不存在小于 $b$ 的正整数 $k$ ，使得 $0≡k∗a(modb)0\equiv k*a(mod\ b)$

证明：

用反证法即可，假设存在这样的一个 $k$ 使得该式成立

则需满足 $k$ 或者 $a$ 能整除 $b$

$∵ (a, b) = 1$

$∴ a$ 不可能整除 $b$

$∵ 0 < k < b$

$∴ k$ 亦不可能整除 $b$

推论

如果 $a, b$ 为正整数，且 $a, b$ 互质，则 $0, a, a * 2, a * 3 . . . (b - 1) * a$ 这些数取模 $b$ ，余数互不相等

证明：

反证法

设存在 $0 < i < j < b$ ，使得 $a∗i≡a∗j(modb)a*i\equiv a*j(mod\ b)$

则有 $(i−j)∗a≡0(modb)(i-j)*a\equiv 0(mod\ b)$

同理引理一， $i - j, a$ 都不可能整除 $b$ ，故与假设矛盾，不成立

引理二

如果 $(a, b) = 1$ ，则必存在一个整数 $k$ ，满足 $k∗a%b=1k*a\% b=1$

证明：

根据上面推论易知，这些数取模 $b$ 的值只会在区间 $[0, b - 1]$ （ $k = 0$ 时取模余数为 $0$ ）

而且各不相同，其中一定存在取模后的余数为 $1$ 的值

根据引理二可知，如果 $(a, b) = 1$ ，则必存在一个整数 $k$ ，满足 $k∗a%b=1k*a\% b=1$

即 $k * a - p * b = 1$ ，裴蜀定理得证

威尔逊定理

$(p−1)!≡−1(modp)(p-1)!\equiv -1(mod\ p)$ ，当且仅当 $p$ 为质数

证明：

先证充分性 $→p\rightarrow p$ 为质数，有 $(p−1)!≡p−1(modp)(p-1)!\equiv p-1(mod\ p)$

假设 $0 < i < p$ ，根据上面的裴蜀定理，可得 $(i, p) = 1$ ，且必存在一个整数 $j (0 < j < p)$

使得 $i×j%p=1i\times j\%p=1$ ，即 $j$ 是 $i$ 的逆元，由此可见逆元具有唯一性，相互性

所以在 $[1, p - 1]$ 中逆元是一对一对的

然而……也有可能存在 $i$ 的逆元是本身的，那么此时的 $i$ 就要满足以下条件

$i2%p=1⇒(i+1)(i−1)%p=0i^2\%p=1\Rightarrow (i+1)(i-1)\%p=0$

$∴ i + 1 = 0$ 或 $p$ ， $i - 1 = 0$ 或 $p$

$∵ 0 < i < p$

$∴ i + 1 = p, i - 1 = 0$

即 $i = p - 1, 1$

每一对逆元取模 $p$ 都为 $1$ ，需要证明的原式变成 $1∗p−1≡p−1(modp)1*p-1\equiv p-1(mod\ p)$

显然成立，证毕

再证必要性 $→(p−1)!≡p−1(modp)\rightarrow (p-1)!\equiv p-1(mod\ p)$ ，当该式成立时， $p$ 一定为质数

反证法，即证明 $p$ 不为质数时，该式不成立

如 $p$ 不为质数，则 $[2, p - 1]$ 中一定有 $p$ 的因子，设为 $i$ ，则 $i, p / i$ 均为 $p$ 的因子

若 $i \neq = p / i$ ，则 $1×2×3×…×(p−1)1\times 2\times 3\times …\times (p-1)$ 一定是 $p$ 的倍数，取模 $p$ 为 $0$
若 $i = p / i$ ，则 $1×2×3×…×(p−1)1\times 2\times 3\times …\times (p-1)$ 一定是 $i$ 的倍数，模 $p$ 必为 $i$ 的倍数

又因为 $p$ 是 $i$ 的倍数，且 $i > 1$ ，所以 $p - 1$ 不可能是 $i$ 的倍数，所以 $(p−1)!≡−1(modp)(p-1)!\equiv-1(mod\ p)$

费马定理

如果 $p$ 为质数，且 $a%p≠0a\%p≠0$ ，则有 $a^{p-1}\%p=1$

证明：
$a*1)* (a* 2)* …*(a* (p-1))=a^{p-1}*(p-1)!\ \ (mod\ p)$
$∵ (a, p) = 1$
${(a* 1)\% p,(a*2)\% p,…,(a*(p-1))\%p\}=\{1,p-1\}$
即取模后的值互不相等，且 $\in [1, p - 1]$
$∴(a∗1)%p,(a∗2)%p,…,(a∗(p−1))%p=(p−1)!(modp)∴(a*1)\% p,(a*2)\% p,…,(a*(p-1))\%p=(p-1)!\ \ (mod\ p)$
$p-1)!=a^{p-1}(p-1)!\ \ (mod\ p)$
$a^{p-1}=1\ \ (mod\ p)$

同余等价类、剩余系、缩系

对于一个正整数 $p$ ，所有非负整数模 $p$ 的结果，只有 $p$ 种可能，即 ${0,1,2,…,p-1\}$
模 $p$ 的剩余系指的是 ${0,1,2,…,p-1\}$ ，即小于 $p$ 的所有非负整数，这个集合中包含了所有模 $p$ 的余数
模 $p$ 的剩余系记为 $Z_p$

剩余系中，每一个元素代表的是一类数
比如在剩余系 $Z_p$ 中

$0$ 表示的是所有模 $p$ 为 $0$ 的数，即 ${0,p,2p,3p…\}$

$1$ 表示的是所有模 $p$ 为 $1$ 的数，即 ${1,p+1,2p+1,3p+1…\}$

这些模 $p$ 余数相同的数，称为同余等价类
可以发现，在模意义下，所有的非负整数可以被分为若干同余等价类

如果我们只考虑剩余系中与模数p互质的数，便得到一个子集，称为模p的缩系，记为 $Z_p^*$
如 $p$ 为 $6$ ，则 $Z_p^*=\{1,5\}$
缩系又称为简化剩余系

欧拉函数

欧拉函数即为缩系的大小

$ϕ(1)=1\phi(1)=1$

如果 $n$ 为质数，则 $ϕ(n)=n−1\phi(n)=n-1$

如果 $n=a^p$ ，且 $a$ 为质数，则 $ϕ(n)=ap−ap−1=ap(1−1a)\phi(n)=a^p-a^{p-1}=a^p(1-\frac{1}{a})$

令 $n=a_1^{p_1}a_2^{p_2}…a_k^{p_k}$ ，根据积性函数性质
$ϕ(n)=ϕ(a1p1)ϕ(a2p2)…ϕ(akpk)=a1p1(1−1a1)∗a2p2(1−1a2)…akpk(1−1ak)\phi(n)=\phi(a_1^{p_1})\phi(a_2^{p_2})…\phi(a_k^{p_k})=a_1^{p_1}(1-\frac{1}{a_1})*a_2^{p_2}(1-\frac{1}{a_2})…a_k^{p_k}(1-\frac{1}{a_k})$
$=n∗(1−1a1)∗(1−1a2)∗…∗(1−1ak)=n*(1-\frac{1}{a_1})*(1-\frac{1}{a_2})*…*(1-\frac{1}{a_k})$

$∑d∣nϕ(d)=n\sum_{d\big|n}\phi(d)=n$

考虑用分数形式证明

$n$ 个真分数： $1n,2n,…,n−1n,nn\frac{1}{n},\frac{2}{n},…,\frac{n-1}{n},\frac{n}{n}$

然后进行分数化简，按分母不同分类

分母一定是 $n$ 的因数，且分母分子互质，并且真分数形式的分子小于分母

那么该类分数个数就是分母的 $ϕ\phi$ ，得证

小于 $n$ 且与 $n$ 互质的所有正整数之和为 $nϕ(n)2\frac{n\phi(n)}{2}$

证明：
设 $s=\{a_1,a_2,…,a_k\}$ 是在模 $n$ 意义下的缩系，根据缩系定义，个数就是 $ϕ(n)\phi(n)$

则 $t=\{n-a_1,n-a_2,…,n-a_k\}$ 也是模 $n$ 意义下的缩系（详见辗转相除法的辗转相减）

两个集合相加，证毕

//求单个phi(n)
int getphi( int x ) {int ans = x;for( int i = 2;i * i <= x;i ++ ) {if( x % i == 0 ) {ans = ans / i * ( i - 1 );while( x % i == 0 ) x /= i;}}if( x > 1 ) ans = ans / x * ( x - 1 );return ans;
}

//求多个phi(n)
void getphi( int n ) {for( int i = 2;i <= n;i ++ ) {if( ! phi[i] ) {phi[i] = i - 1;for( int j = i << 1;j <= n;j += i ) {if( ! phi[j] ) phi[j] = j;phi[j] = phi[j] / i * ( i - 1 );}}}
}

欧拉定理

如果 $(a, p) = 1$ ，则 $aϕ(p)≡1(modp)a^{\phi(p)}\equiv1(mod\ p)$

证明：

设 $p$ 的简化剩余系为 ${p_1,p_2,p_3,…,p_k\}$

$∵ (a, p) = 1$

${a*p_1,a*p_2,…,a*p_k\}$ 也构成了 $p$ 的简化剩余系

（证明可参考裴蜀定理中的推论反证法）

$∴(a∗p1)∗(a∗p2)∗…∗(a∗pk)≡p1∗p2∗…∗pk(modp)∴(a*p_1)*(a*p_2)*…*(a*p_k)\equiv p_1*p_2*…*p_k(mod\ p)$

$∴aϕ(p)≡1(modp)∴a^{\phi(p)}\equiv 1(mod\ p)$

扩展欧拉定理

若 $a, m$ 为正整数，当 $r>ϕ(m)r>\phi(m)$ 时，有 $ar≡ar%ϕ(m)+ϕ(m)a^r\equiv a^{r\%\phi(m)+\phi(m)}$

证明：

分类讨论

.如果 $(a, m) = 1$ ，则显然成立

因为由欧拉定理得 $aϕ(m)≡1(modm)a^{\phi(m)}\equiv1\pmod m$
若 $(a, m) > 1$

引理一：

如果满足
${x≡y(modm)x≡y(modn)\begin{cases}x\equiv y\ (mod\ m)\\x\equiv y\ (mod\ n)\end{cases}$
则有
$x≡y(modlcm(n,m))x\equiv y\ (mod\ \ lcm(n,m))$

证明：
显然 $(x - y)$ 既是 $m$ 的倍数，又是 $n$ 的倍数，则其必然为 $l c m (n, m)$ 的倍数

引理二：

如果 $p$ 为质数， $ϕ(pq)≥q\phi(p^q)\ge q$

证明：

给两种证明方法

法一：

以每 $p$ 个为一个周期划分

显然 $p,p-1)=1,(p^2,p^2-1)=1,…,(p^q,p^q-1)=1$

此时光考虑一部分就已经满足 $ϕ(pq)=q\phi(p^q)=q$ ，故引理显然成立

法二：

$ϕ(pq)=pq−1∗(p−1)\phi(p^q)=p^{q-1}*(p-1)$

根据数学归纳法

考虑 $q=1,ϕ(p)>=1q=1,\phi(p)>=1$ 显然成立

设 $q = k$ 时成立，即 $p^{k-1}*(p-1)>=k$

$∵ k > 1$

$∴$ 显然 $p^k*(p-1)>=k+1$

即当 $q = k + 1$ 时，也成立

接下来继续证明扩展欧拉定理

若 $m=p^k$ ，即 $m$ 为质数的幂时

$∵ (a, m) > 1$

$∴p∣a∴p\bigg|a$

由引理二可得 $ϕ(pk)≥k\phi(p^k)\ge k$ ，即 $ϕ(m)≥k\phi(m)\ge k$

$\phi(m)\ge k$

$∴ar=x∗pr=y∗pϕ(m)=z∗pk∴a^r=x*p^r=y*p^{\phi(m)}=z*p^k$ （从 $p$ 的指数上抽一些下来使 $x→y→zx\rightarrow y\rightarrow z$ ）

即 $m∣ar,m∣pϕ(m)m\bigg|a^r,m\bigg|p^{\phi(m)}$

$∴ar≡ar%ϕ(m)+ϕ(m)≡0(modm)∴a^r\equiv a^{r\%\phi(m)+\phi(m)}\equiv 0(mod\ \ m)$
若 $m=p_1^{k_1}p_2^{k_2}…p_{n}^{k_n}$

设 $m_1=p_1^{k_1}$ ，则 $ar≡ar%ϕ(m1)+ϕ(m1)(modm1)a^r\equiv a^{r\%\phi(m_1)+\phi(m_1)}\ \ (mod\ \ m_1)$

设 $m_2=p_2^{k_2}$ ，则 $ar≡ar%ϕ(m2)+ϕ(m2)(modm2)a^r\equiv a^{r\%\phi(m_2)+\phi(m_2)}\ \ (mod\ \ m_2)$

$. . . . . .$

设 $m_n=p_n^{k_n}$ ，则 $ar≡ar%ϕ(mn)+ϕ(mn)(modmn)a^r\equiv a^{r\%\phi(m_n)+\phi(m_n)}\ \ (mod\ \ m_n)$

$m_1,m_2,…,m_n$ 不同的质数的幂，两两互质

$ϕ(m)=ϕ(m1)∗ϕ(m2)∗…∗ϕ(mn)\phi(m)=\phi(m_1)*\phi(m_2)*…*\phi(m_n)$

又根据引理一，则得到：

$ar≡ar%ϕ(m)+ϕ(m)(modm)a^r\equiv a^{r\%\phi(m)+\phi(m)}\pmod m$

区间逆元

如果整数 $a, b$ 满足 $a∗b%p=1a*b\%p=1$ ，则称 $a, b$ 在模 $p$ 的意义下互为逆元
只有 $(a, p) = 1$ ，在模 $p$ 的意义下 $a$ 才有逆元， $a$ 的逆元记作 $a^{-1}$

证明：

若 $(a, p) > 1$ ，则令 $d = g c d (a, p), d ∣ a, d ∣ p$

$∴d∣a%p∴d|a\%p$ （感性理解为：x倍 $d$ 减去y倍 $p$ 直到 $x < y$ ，其差一定也为 $d$ 的倍数）

$∴a≡(x%y)d(modp)∴a\equiv (x\%y)d\ (mod\ \ p)$

$∵ d > 1$

$∴(x%y)d≠1∴(x\%y)d≠1$

逆元的性质：若 $(b, p) = 1$ ，则 $a/b\%p=a*b^{-1}\%p$

有一种求区间逆元的方式，时间复杂度为 $O (n)$
设模数为 $m, f [n]$ 表示 $n$ 的逆元，其中 $[1, n)$ 的逆元已经求出，则
$f[n]=(−f[m%n]∗(m/n)%m+m)%mf[n]=(-f[m\%n]*(m/n)\%m+m)\%m$

证明：

公式一：

$f [i] = - f [m - i]$

证明：

$f[i]∗i≡1(modm)f[i]*i\equiv1\ \ \ (mod\ m)$

$f[i]∗(m−i)≡−1(modm)f[i]*(m-i)\equiv-1\ \ \ (mod\ m)$

$f[m−i]∗(m−i)≡1(modm)f[m-i]*(m-i)\equiv1\ \ \ (mod\ m)$

$f [i] = - f [m - i]$

公式二：

$f [i] = k * f [k * i]$

证明：

$f[i∗k]∗(i∗k)≡1(modm)f[i*k]*(i*k)\equiv 1\ \ \ (mod\ m)$

$(f[i∗k]∗k)∗i≡1(modm)(f[i*k]*k)*i\equiv 1\ \ \ (mod\ m)$

$f[i]∗i≡1(modm)f[i]*i\equiv 1\ \ \ (mod\ m)$

$f [i * k] * k = f [i]$

$f[n]=k∗f[k∗n]=m/n×f[m−m%n]f[n]=k*f[k*n]=m/n\times f[m-m\%n]$

$f[m−m%n]=−f[m%n]f[m-m\%n]=-f[m\%n]$

$f[n]=m/n×(−f[m%n])f[n]=m/n\times (-f[m\% n])$

inv[1] = 1;
for( int i = 2;i <= n;i ++ )inv[i] = ( mod - mod / i ) * inv[mod % i] % mod;

扩展欧几里得

扩展欧几里得是用来求不定方程： $a x + b y = c$ ，且已知整数 $a, b, c$
要求 $g c d (a, b) ∣ c$ ，才能保证有解

算法思想：递归求解

先求方程 $a x + b y = g c d (a, b)$ ，求出该方程的解，乘上系数 $c / g c d (a, b)$ 即为原方程的解
$ax+by=gcd(a,b)=gcd(b,a%b)=bx′+(a%b)y′=bx′+(a−a/b∗b)y′ax+by=gcd(a,b)=gcd(b,a\%b)=bx'+(a\%b)y'=bx'+(a-a/b*b)y'$
将 $a, b$ 看做变量，移项合并同类项
$a x + b y = b x^{'} + (a - a / b * b) y^{'}$
$a x + b y - b x^{'} - a y^{'} + a / b * b y^{'} = 0$
$x a - y^{'} a + y b - x^{'} b + a / b * y^{'} b = 0$
$(x - y^{'}) a + (y - x^{'} + a / b * y^{'}) b = 0$
$∵ a * b \neq = 0$
$∴ x - y^{'} = 0, y - x^{'} + a / b * y^{'} = 0$
$∴{x=y′y=x′−y′∗(a/b)∴\begin{cases}x=y'\\y=x'-y'*(a/b)\end{cases}$
只需要求出 $x^{'}, y^{'}$ 就可以求出 $x, y$

而求 $x^{'}, y^{'}$ 可以继续递归下去

$g c d (a, b)$ 中的参数 $b$ 最终会变为 $0$ ，此时 $g c d (a, 0) = a$

于是有 $a x + b y = g c d (a, 0) = a$ ，可以求出 $x = 1, y = 0$

这是最底层的 $x, y$ ，然后一层层返回，就可以求出最原始的 $x, y$ 了

注意， $e x g c d$ 求出来的 $x, y$ 满足的方程组是 $a x + b x = g c d (a, b)$

将这一对 $x, y$ 乘上 $cgcd(a,b)\frac{c}{gcd(a,b)}$ ，才是原方程的一组解

而且，这一组解只是一组特解，并不一定是最小的，可以通过通解公式去找到最小解 $x$

$a x + b y = c$
$a(x−k)+b(y+akb)=ca(x-k)+b(y+\frac{ak}{b})=c$
因为 $a$ 缩小若干倍，为了保证方程的正确性， $b$ 就应该放大若干倍，所以需满足 $b∣akb\bigg|ak$
$∴bgcd(a,b)∣agcd(a,b)k∴\frac{b}{gcd(a,b)}\bigg|\frac{a}{gcd(a,b)}k$
$∵(bgcd(a,b),agcd(a,b))=1∵(\frac{b}{gcd(a,b)},\frac{a}{gcd(a,b)})=1$
$∴bgcd(a,b)∣k∴\frac{b}{gcd(a,b)}|k$
所以原方程的 $a$ 可以无限缩小 $bgcd(a,b)\frac{b}{gcd(a,b)}$ 倍，直到 $a<bgcd(a,b)a<\frac{b}{gcd(a,b)}$

同理，通解也可以被表示出来 $X=x+t×bgcd(a,b),Y=y−t×agcd(a,b)X=x+t\times \frac{b}{gcd(a,b)},Y=y-t\times \frac{a}{gcd(a,b)}$

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

//求x的最小解
x = ( x * ( c / d ) % ( b / d ) + ( b / d ) ) % ( b / d )

中国剩余定理

求一个模线性方程组 $x$
${x≡a1(modr1)x≡a2(modr2)…x≡ak(modrk)\begin{cases}x\equiv a_1\ \ (mod\ \ r_1)\\x\equiv a_2\ \ (mod\ \ r_2)\\…\\x\equiv a_k\ \ (mod\ \ r_k)\end{cases}$
其中 $r_1,r_2,…,r_k$ 互质

对于 $r_i$ ，设 $Ai=∏j≠irjA_i=\prod_{j≠i}r_j$

$r_1,r_2,…,r_k)=1$

$A_i,r_i)=1$

则一定存在一个整数 $c_i$ 满足 $c_i*A_i\% r_i=1$

设 $x_i=a_i*c_i*A_i$ ，则 $x_i\%r_i=a_i$

因为 $A_i$ 是除了 $r_i$ 以外的其他 $r$ 值的最小公倍数

所以， $x_i\%r_j=0(j≠i)$ ，即 $x_i$ 模其他的 $r$ 余数都为 $0$ ，只有模 $r_i$ 的时候，余数为 $a_i$

换言之，把 $x_i$ 加到满足其他方程 $j (j \neq = i)$ 的解 $x_j$ 上， $x_i+x_j)$ 也一样满足方程 $j$

同理，如果 $x_j$ 也是这么求出来的，则 $x_i+x_j)$ 也满足方程 $i$

那么，我们对于每一个方程，都按照这个方法求出来该方程的解

把这些解累加起来，发现，这个和仍然满足每一个方程

即 $x=∑i=1kai∗ci∗Ai%rix=\sum_{i=1}^ka_i*c_i*A_i\%r_i$

对于 $x$ ，加上所有的 $r$ 值的最小公倍数，它仍然满足所有方程

所以，只要存在 $x$ ，则意味着有无穷多组解

通解为： $x=∑i=1k(ai∗ci∗Ai%ri)+p∗∏i=1kri,p∈Zx=\sum_{i=1}^k(a_i*c_i*A_i\%r_i)+p*\prod_{i=1}^kr_i,p∈Z$

扩展中国剩余定理

求一个模线性方程组 $x$
${x≡a1(modr1)x≡a2(modr2)…x≡ak(modrk)\begin{cases}x\equiv a_1\ \ (mod\ \ r_1)\\x\equiv a_2\ \ (mod\ \ r_2)\\…\\x\equiv a_k\ \ (mod\ \ r_k)\end{cases}$
其中 $r_1,r_2,…,r_k$ 不一定互质

首先，取前两个方程 $x=k*r_1+a_1=p*r_2+a_2$ $k*r_1-p*r_2=a_2-a_1$

这种形如 $a x + b y = c$ 的不定方程，可以用扩展欧几里得计算

当 $gcd(r_1,r_2)$ 不能整除 $a_2-a_1$ 时，方程组无解

否则，根据 $e x g c d$ ，求出 $k_0$ ，满足 $k_0*r_1-p*r_2=a_2-a_1$

$k$ 的通解为：
$k=k_0+b*(r_2/gcd(r_1,r_2))$

带入到方程组 $x=k*r_1+a_1$ 中，则有 $x=(k_0+b*(r_2/gcd(r_1,r_2)))*r_1+a_1=k_0*r_1+b*lcm(r_1,r_2)+a_1,b∈Z$
即 $x≡a1(modlcm(r1,r2))x\equiv a_1\ \ (mod\ \ lcm(r_1,r_2))$
这个方程相当于合并了原来的两个方程，而形式上又和原来的方程一致

继续采用这个方法，不断地合并方程组中的两个方程

直到最后合并为一个方程，则可以得到 $x$ 的通解

注意在这个过程中，要注意求出的 $k_0$ 是 $k*r_1-p*r_2=(a_2-a_1)$ 的解

而不是 $k*r_1-p*r_2=gcd(r_1,r_2)$ 的解，前者是后者的倍数

//扩展中国剩余定理，求最小整数解x的模板代码
#include <cstdio>
#define MAXK 10000005
#define int long long
int mod[MAXK], r[MAXK];void exgcd( int a, int b, int &d, int &x, int &y ) {if( ! b ) d = a, x = 1, y = 0;else {exgcd( b, a % b, d, y, x );y -= x * ( a / b );}
}int Fabs( int x ) {return ( x < 0 ) ? -x : x;
}signed main() {int m;while( ~ scanf( "%lld", &m ) ) {for( int i = 1;i <= m;i ++ )scanf( "%lld %lld", &mod[i], &r[i] );int noans = 0, d, x, y;for( int i = 1;i < m;i ++ ) {exgcd( mod[i], mod[i + 1], d, x, y );if( Fabs( r[i + 1] - r[i] ) % d ) {noans = 1;break;}x = ( x * ( ( r[i + 1] - r[i] ) / d ) % ( mod[i + 1] / d ) + ( mod[i + 1] / d ) ) % ( mod[i + 1] / d );int lcm = mod[i] / d * mod[i + 1];mod[i + 1] = lcm, r[i + 1] = ( x * mod[i] + r[i] ) % lcm;}if( noans ) printf( "-1\n" );else printf( "%lld\n", r[m] );
//r[m]可能等于0，所以根据题目要求，若要最小正整数，则为mod[m]}return 0;
}

终于写完了！！！！！！！！！！！！！！！！！！！！！

利用以上所有知识进行证明

若 $p$ 是质数（ $p > 3$ ），则 $2 p + 1$ 和 $4 p + 2$ 至多有一个数是质数

抛开 $3$ 的倍数（肯定是合数），任何整数都可以被改写成 $3 k \pm 1$ 的形式

$p = 3 k + 1$
$2 p + 1 = 6 k + 3 = 3 (k + 1)$ ，合数
$4 p + 2 = 12 k + 6 = 6 (2 k + 1)$ ，合数
$p = 3 k - 1$
$2 p + 1 = 6 k - 1$ ，未知
$4 p + 2 = 12 k - 2 = 2 (6 k - 1)$ ，合数