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

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

同余，整除

整除的性质：

• 传递性：若$a|b,b|c$，则$a|c$
• $a|b,a|c$等价于对于任意的整数$x,y$，有$a|(bx+cy)$
• 设$m\ne 0$，则$a|b$等价于$ma|mb$
• 设整数$x,y$满足$ax+by=1,a|n,b|,n$，则$(ab)|n$
• 若$b=q\ast d+c$，则$d|b$的充要条件是$d|c$

---

同余的性质：

• 同加性：若$a\equiv b(modp)$，则$a+c\equiv b+c(modp)$
• 同减性：若$a\equiv b(modp)$，则$a-c\equiv b-c(modp)$
• 同乘性：若$a\equiv b(modp)$，则$a\times c\equiv b\times c(modp)$
• 同除性：若$a\equiv b(modp),c|a,c|b,(c,p)=1$，则$a/c\equiv b/c(modp)$
• 同幂性：若$a\equiv b(modp),c>0$，则ac≡bc(modp)a^c\equiv b^c(mod\ p)ac≡bc(mod p)
• 若$a\%p=x,a\%q=x,(p,q)=1$，则$a\%(p\ast 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\times b)\%c=(a\%c\times b\%c)\%c$
• (ab)%c=(a%c)b%c(a^b)\% c=(a\% c)^b\% c(ab)%c=(a%c)b%c

2.放缩性

• 如果$a\%b=c,d\ne 0$，则有$(a\times d)\%(b\times d)=c\times d$
• 如果$a\%b=c,d|a,d|b$，则$(a/d)\%(b/d)=(c/d)$

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

---

埃式筛法

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

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

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

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

所以时间复杂度为$O(NlogN)$

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;}
}

---

欧拉筛法

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

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

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

---

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

同时有一个$bool$数组$flag$，表示删除标记

有两层循环：

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

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

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

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

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

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

先将i∗pii*p_ii∗pi​打上标记

如发现$i$是pip_ipi​的倍数时

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

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

---

为什么满足这种条件就可以提前$break$呢？

设后续的质数为pi′p_i'pi′​，而pi′>pip_i'>p_ipi′​>pi​

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

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

∵pi′>pi∵p_i'>p_i∵pi′​>pi​

$\therefore b>a$

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

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

所以后续所有的质数就都留给倍数$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)\times lcm(a,b)=a\ast b$$

证明：
将$a,b$进行质因子分解，设$a,b$的质因子集合并集为p1,p2,p3…pkp_1,p_2,p_3…p_kp1​,p2​,p3​...pk​
设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)设a=p1i1​​p2i2​​...pkik​​,(0≤i1​,0≤i2​...0≤ik​)
设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)设b=p1j1​​p2j2​​...pkjk​​,(0≤j1​,0≤j2​...0≤jk​)
gcd(a,b)=p1min(i1,j1)p2min(i2,j2)…pkmin(ik,jk)gcd(a,b)=p_1^{min(i_1,j_1)}p_2^{min(i_2,j_2)}…p_k^{min(i_k,j_k)}gcd(a,b)=p1min(i1​,j1​)​p2min(i2​,j2​)​...pkmin(ik​,jk​)​
lcm(a,b)=p1max(i1,j1)p2max(i2,j2)…pkmax(ik,jk)lcm(a,b)=p_1^{max(i_1,j_1)}p_2^{max(i_2,j_2)}…p_k^{max(i_k,j_k)}lcm(a,b)=p1max(i1​,j1​)​p2max(i2​,j2​)​...pkmax(ik​,jk​)​
∵min(it,jt)+max(it,jt)=it+jt∵min(i_t,j_t)+max(i_t,j_t)=i_t+j_t∵min(it​,jt​)+max(it​,jt​)=it​+jt​
∴gcd(a,b)+lcm(a,b)=p1i1+j1p2i2+j2…pkik+jk∴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)+lcm(a,b)=p1i1​+j1​​p2i2​+j2​​...pkik​+jk​​

---

辗转相除法

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

证明：
设$d=gcd(a,b),a=x\ast d,b=y\ast d$

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

$\because (x,y)=1$

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

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

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

辗转相减法：

$gcd(a,b)=gcd(b,a-b),a>b$

证明：

令$a=Ad,b=Bd,(A,B)=1\to (a,b)=d$

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

若$gcd(b,a-b)=gcd(Bd,(A-B)d)\ne d$

说明$gcd(B,A-B)>1$

令$gcd(B,A-B)=g,B=sg,A-B=tg$

则一定有$g|A$

与$(A,B)=1$矛盾，所以$gcd(B,A-B)=1$

---

更相减损术

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

---

裴蜀定理

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

证明：

转化证明存在$x,y$使得$ax+by=d$

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

$\because (a,b)=d$

$\therefore$设a′=a/d,b′=b/da'=a/d,b'=b/da′=a/d,b′=b/d

则有a′x+b′y=1,(a′,b′)=1a'x+b'y=1,(a',b')=1a′x+b′y=1,(a′,b′)=1

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

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

---

引理一

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

证明：

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

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

$\because (a,b)=1$

$\therefore a$不可能整除$b$

$\because 0<k<b$

$\therefore k$亦不可能整除$b$

---

推论

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

证明：

反证法

设存在$0<i<j<b$，使得$a\ast i\equiv a\ast j(modb)$

则有$(i-j)\ast a\equiv 0(modb)$

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

---

引理二

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

证明：

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

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

---

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

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

---

威尔逊定理

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

证明：

先证充分性$\to p$为质数，有$(p-1)!\equiv p-1(modp)$

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

使得$i\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=0i2%p=1⇒(i+1)(i−1)%p=0

$\therefore i+1=0$或$p$，$i-1=0$或$p$

$\because 0<i<p$

$\therefore i+1=p,i-1=0$

即$i=p-1,1$

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

显然成立，证毕

---

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

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

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

• 若$i\ne p/i$，则$1\times 2\times 3\times ...\times (p-1)$一定是$p$的倍数，取模$p$为$0$

• 若$i=p/i$，则$1\times 2\times 3\times ...\times (p-1)$一定是$i$的倍数，模$p$必为$i$的倍数

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

---

费马定理

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

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

---

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

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

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

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

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

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

---

欧拉函数

欧拉函数即为缩系的大小

$\varphi (1)=1$

• 如果$n$为质数，则$$\varphi (n)=n-1$$
• 如果n=apn=a^pn=ap，且$a$为质数，则ϕ(n)=ap−ap−1=ap(1−1a)\phi(n)=a^p-a^{p-1}=a^p(1-\frac{1}{a})ϕ(n)=ap−ap−1=ap(1−a1​)
• 令n=a1p1a2p2…akpkn=a_1^{p_1}a_2^{p_2}…a_k^{p_k}n=a1p1​​a2p2​​...akpk​​，根据积性函数性质
  ϕ(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)=ϕ(a1p1​​)ϕ(a2p2​​)...ϕ(akpk​​)=a1p1​​(1−a1​1​)∗a2p2​​(1−a2​1​)...akpk​​(1−ak​1​)
  =n∗(1−1a1)∗(1−1a2)∗…∗(1−1ak)=n*(1-\frac{1}{a_1})*(1-\frac{1}{a_2})*…*(1-\frac{1}{a_k})=n∗(1−a1​1​)∗(1−a2​1​)∗...∗(1−ak​1​)

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

考虑用分数形式证明

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

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

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

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

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

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

则t={n−a1,n−a2,…,n−ak}t=\{n-a_1,n-a_2,…,n-a_k\}t={n−a1​,n−a2​,...,n−ak​}也是模$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)aϕ(p)≡1(mod p)

证明：

设$p$的简化剩余系为{p1,p2,p3,…,pk}\{p_1,p_2,p_3,…,p_k\}{p1​,p2​,p3​,...,pk​}

$\because (a,p)=1$

∴{a∗p1,a∗p2,…,a∗pk}∴\{a*p_1,a*p_2,…,a*p_k\}∴{a∗p1​,a∗p2​,...,a∗pk​}也构成了$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∗p1​)∗(a∗p2​)∗...∗(a∗pk​)≡p1​∗p2​∗...∗pk​(mod p)

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

---

扩展欧拉定理

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

证明：

分类讨论

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

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

• 若$(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 (mod m)x≡y (mod n)​
则有
$x\equiv y(modlcm(n,m))$

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

---

引理二：

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

证明：

给两种证明方法

法一：

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

显然(p,p−1)=1,(p2,p2−1)=1,…,(pq,pq−1)=1(p,p-1)=1,(p^2,p^2-1)=1,…,(p^q,p^q-1)=1(p,p−1)=1,(p2,p2−1)=1,...,(pq,pq−1)=1

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

---

法二：

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

根据数学归纳法

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

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

$\because k>1$

$\therefore$显然pk∗(p−1)>=k+1p^k*(p-1)>=k+1pk∗(p−1)>=k+1

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

---

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

• 若m=pkm=p^km=pk，即$m$为质数的幂时

  $\because (a,m)>1$

  $\therefore p|a$

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

  $\therefore r>\varphi (m)\ge k$

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

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

  ∴ar≡ar%ϕ(m)+ϕ(m)≡0(modm)∴a^r\equiv a^{r\%\phi(m)+\phi(m)}\equiv 0(mod\ \ m)∴ar≡ar%ϕ(m)+ϕ(m)≡0(mod  m)

• 若m=p1k1p2k2…pnknm=p_1^{k_1}p_2^{k_2}…p_{n}^{k_n}m=p1k1​​p2k2​​...pnkn​​

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

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

  $......$

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

  m1,m2,…,mnm_1,m_2,…,m_nm1​,m2​,...,mn​ 不同的质数的幂，两两互质

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

  又根据引理一，则得到：

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

区间逆元

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

证明：

若$(a,p)>1$，则令$d=gcd(a,p),d|a,d|p$

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

$\therefore a\equiv (x\%y)d(modp)$

$\because d>1$

$\therefore (x\%y)d\ne 1$

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

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

证明：

---

公式一：

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

证明：

$f[i]\ast i\equiv 1(modm)$

$f[i]\ast (m-i)\equiv -1(modm)$

$f[m-i]\ast (m-i)\equiv 1(modm)$

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

---

公式二：

$f[i]=k\ast f[k\ast i]$

证明：

$f[i\ast k]\ast (i\ast k)\equiv 1(modm)$

$(f[i\ast k]\ast k)\ast i\equiv 1(modm)$

$f[i]\ast i\equiv 1(modm)$

$f[i\ast k]\ast k=f[i]$

---

$f[n]=k\ast f[k\ast n]=m/n\times f[m-m\%n]$

$f[m-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;

扩展欧几里得

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

算法思想：递归求解

先求方程$ax+by=gcd(a,b)$，求出该方程的解，乘上系数$c/gcd(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'ax+by=gcd(a,b)=gcd(b,a%b)=bx′+(a%b)y′=bx′+(a−a/b∗b)y′
将$a,b$看做变量，移项合并同类项
ax+by=bx′+(a−a/b∗b)y′ax+by=bx'+(a-a/b*b)y'ax+by=bx′+(a−a/b∗b)y′
ax+by−bx′−ay′+a/b∗by′=0ax+by-bx'-ay'+a/b*by'=0ax+by−bx′−ay′+a/b∗by′=0
xa−y′a+yb−x′b+a/b∗y′b=0xa-y'a+yb-x'b+a/b*y'b=0xa−y′a+yb−x′b+a/b∗y′b=0
(x−y′)a+(y−x′+a/b∗y′)b=0(x-y')a+(y-x'+a/b*y')b=0(x−y′)a+(y−x′+a/b∗y′)b=0
$$\because a\ast b\ne 0$$
∴x−y′=0,y−x′+a/b∗y′=0∴x-y'=0,y-x'+a/b*y'=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′y=x′−y′∗(a/b)​
只需要求出x′,y′x',y'x′,y′就可以求出$x,y$

而求x′,y′x',y'x′,y′可以继续递归下去

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

于是有$ax+by=gcd(a,0)=a$，可以求出$x=1,y=0$

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

---

注意，$exgcd$求出来的$x,y$满足的方程组是$ax+bx=gcd(a,b)$

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

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

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

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}⎩⎪⎪⎪⎨⎪⎪⎪⎧​x≡a1​  (mod  r1​)x≡a2​  (mod  r2​)...x≡ak​  (mod  rk​)​
其中r1,r2,…,rkr_1,r_2,…,r_kr1​,r2​,...,rk​互质

对于rir_iri​，设Ai=∏j≠irjA_i=\prod_{j≠i}r_jAi​=∏j​=i​rj​

∵(r1,r2,…,rk)=1∵(r_1,r_2,…,r_k)=1∵(r1​,r2​,...,rk​)=1

∴(Ai,ri)=1∴(A_i,r_i)=1∴(Ai​,ri​)=1

则一定存在一个整数cic_ici​满足ci∗Ai%ri=1c_i*A_i\% r_i=1ci​∗Ai​%ri​=1

设xi=ai∗ci∗Aix_i=a_i*c_i*A_ixi​=ai​∗ci​∗Ai​，则xi%ri=aix_i\%r_i=a_ixi​%ri​=ai​

因为AiA_iAi​是除了rir_iri​以外的其他$r$值的最小公倍数

所以，xi%rj=0(j≠i)x_i\%r_j=0(j≠i)xi​%rj​=0(j​=i)，即xix_ixi​模其他的$r$余数都为$0$，只有模rir_iri​的时候，余数为aia_iai​

换言之，把xix_ixi​加到满足其他方程$j(j\ne i)$的解xjx_jxj​上，(xi+xj)(x_i+x_j)(xi​+xj​)也一样满足方程$j$

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

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

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

即x=∑i=1kai∗ci∗Ai%rix=\sum_{i=1}^ka_i*c_i*A_i\%r_ix=∑i=1k​ai​∗ci​∗Ai​%ri​

对于$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∈Zx=i=1∑k​(ai​∗ci​∗Ai​%ri​)+p∗i=1∏k​ri​,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}⎩⎪⎪⎪⎨⎪⎪⎪⎧​x≡a1​  (mod  r1​)x≡a2​  (mod  r2​)...x≡ak​  (mod  rk​)​
其中r1,r2,…,rkr_1,r_2,…,r_kr1​,r2​,...,rk​不一定互质

首先，取前两个方程x=k∗r1+a1=p∗r2+a2x=k*r_1+a_1=p*r_2+a_2x=k∗r1​+a1​=p∗r2​+a2​k∗r1−p∗r2=a2−a1k*r_1-p*r_2=a_2-a_1k∗r1​−p∗r2​=a2​−a1​

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

当gcd(r1,r2)gcd(r_1,r_2)gcd(r1​,r2​)不能整除a2−a1a_2-a_1a2​−a1​时，方程组无解

否则，根据$exgcd$，求出k0k_0k0​，满足k0∗r1−p∗r2=a2−a1k_0*r_1-p*r_2=a_2-a_1k0​∗r1​−p∗r2​=a2​−a1​

$k$的通解为：
k=k0+b∗(r2/gcd(r1,r2))k=k_0+b*(r_2/gcd(r_1,r_2))k=k0​+b∗(r2​/gcd(r1​,r2​))

带入到方程组x=k∗r1+a1x=k*r_1+a_1x=k∗r1​+a1​中，则有x=(k0+b∗(r2/gcd(r1,r2)))∗r1+a1=k0∗r1+b∗lcm(r1,r2)+a1,b∈Zx=(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∈Zx=(k0​+b∗(r2​/gcd(r1​,r2​)))∗r1​+a1​=k0​∗r1​+b∗lcm(r1​,r2​)+a1​,b∈Z
即x≡a1(modlcm(r1,r2))x\equiv a_1\ \ (mod\ \ lcm(r_1,r_2))x≡a1​  (mod  lcm(r1​,r2​))
这个方程相当于合并了原来的两个方程，而形式上又和原来的方程一致

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

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

注意在这个过程中，要注意求出的k0k_0k0​是k∗r1−p∗r2=(a2−a1)k*r_1-p*r_2=(a_2-a_1)k∗r1​−p∗r2​=(a2​−a1​)的解

而不是k∗r1−p∗r2=gcd(r1,r2)k*r_1-p*r_2=gcd(r_1,r_2)k∗r1​−p∗r2​=gcd(r1​,r2​)的解，前者是后者的倍数

//扩展中国剩余定理，求最小整数解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$），则$2p+1$和$4p+2$至多有一个数是质数

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

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

最多就是那个未知情况为质数，得证

$$gcd(f(n),f(m))=f(gcd(n,m))$$
$f:$ 斐波拉契数列

gcd⁡(an−1,am−1)=agcd(n,m)−1\gcd(a^n-1,a^m-1)=a^{gcd(n,m)}-1gcd(an−1,am−1)=agcd(n,m)−1