裴蜀定理：

內容：若$gcd(a,b)=d$，則一定存在$m,n\in Z$，使$ma+nb=d$且$d$為$ma+nb$的最小正值（狹義）

證明：

令$d=gcd(a,b)$，則對任意$m,n\in Z$，有$d|am+bn$

設$am+bn$的最小正值為$s$，則令$q=[\frac{a}{s}],r=a$ $mod$ $s=a-q(am+bn)=a(1-qm)+b(-qn)$

考慮到$r=a$ $mod$ $s$，于是$0\leq r<s$

那么r也是$am+bn$的一個表達，由于s是最小正值，于是$r=0$（如果r不為0，那么r就是最小正值了）

于是$s|a$，同理$s|b$，于是s是a和b的公約數，于是$s\geq d$

考慮$d|a,d|b,s=am+bn$，則$d|s$，于是$d\geq s$

那么d=s

整數的唯一分解定理：

定理：對任意正整數$M\geq2$，M可以表示成唯一的一組$p_{1},p_{2}...p_{n}$的表達$M=p_{1}^{k_{1}}p_{2}^{k_{2}}...p_{n}^{k_{n}}$（$p_{1}<p_{2}<...<p_{n}$)

我們采用反證法證之：

引理：若質數p|ab，則p|a或p|b

證明：若p|a則定理得證，若p不是a的約數，則a,p互質（顯然）

于是根據裴蜀定理，存在$m,n\in Z$使$ma+np=1$，于是$b=b(ma+nb)=mab+nbp$

考慮$p|ab$，則上式右側能被$p$整除，于是左側也能被$p$整除，即$p|b$

設$M=p_{1}^{k_{1}}p_{2}^{k_{2}}...p_{n}^{k_{n}}=q_{1}^{a_{1}}q_{2}^{a_{2}}...q_{n}^{a_{n}}$是最小可以用兩種方法表示的正整數

那么有$p_{1}|q_{1}^{k_{1}}...q_{n}^{k_{n}}$

結合上述引理，有$p_{1}|q_{1}$或$p_{1}|q_{2}$...或$p_{1}|q_{n}$

那么為了保證$q$均為質數，不妨令$p_{1}|q_{1}$（不失一般性）則有$p_{1}=q_{1}$

不妨令$a_{1}\leq _{1}$，則構造$M^{'}=p_{1}^{a_{1}-k_{1}}p_{2}^{k_{2}}...p_{n}^{k_{n}}=q_{2}^{a_{2}}...q_{n}^{a_{n}}$

結合上述分析，有$p_{1}=q_{2}~q_{n}$中的一個

但是顯然這與$q_{1}...q_{n}$互不相同矛盾，于是必須有$a_{1}=k_{1}$

那么我可以構造$M^{"}=p_{2}^{k_{2}}...p_{n}^{k_{n}}=q_{2}^{a_{2}}...q_{n}^{a_{n}}<M$，這就是找到了一個比$M$更小的能用兩種方法表示的正整數，從而與假設矛盾

記$M=p_{1}^{k_{1}}...p_{n}^{k_{n}}$

約數個數公式：M的約數個數$d(M)=\pi_{i=1}^{n}(k_{i}+1)$

約數和公式：M的約數和$σ(M)=\pi_{i=1}^{n}(\sum_{j=0}^{k_{i}}p_{i}^{j})$

等比數列分治求和公式：$\sum_{i=1}^{n}p^{i}=\sum_{i=1}^{\frac{n}{2}}p_{i}+p^{\frac{n}{2}}\sum_{i=1}^{\frac{n}{2}}p_{i}$

歐拉函數的性質：

$\phi(p)=p-1$（p為質數）

令$M=\pi_{i=1}^{n}p_{i}^{k_{i}}$，則$\phi(M)=\pi_{i=1}^{n}(p_{i}-1)*p_{i}^{k_{i}-1}$

丟番圖題解：

$\frac{1}{x}+\frac{1}{y}=\frac{1}{n}$

移項通分：$n(x+y)=xy$，再整理：$x=\frac{ny}{y-n}$

令$t=y-n$，于是$y=t+n$，即$x=\frac{n(t+n)}{t}$，也即$x=n+\frac{n^{2}}{t}$

于是求出$n^{2}$的約數個數即可

模線性方程問題

$ax\equiv1$(mod b)

gcd問題：

令$d=gcd(a,b)$，記$a=kb+m$

顯然$d|a,d|b$，則$d|m$,也即$d|m,d|b$，也即$d|gcd(b,m)$

設$d^{'}=gcd(b,m)$，則$d^{'}|b,d^{'}|m$，也即$d^{'}|a$

注意到$d$是$a$與$b$的最大公約數，于是$d^{'}|d$

于是$d=d^{'}$（證明中隱含了一個內容：兩個數的最大公約數能被這兩個數所有的公約數整除）

ex_gcd問題

$ax\equiv 1$(mod b)即$ax+by=1$

這里我們知道a,b互質，于是原方程即為$ax+by=gcd(a,b)$

我們知道$gcd(a,b)=gcd(b,a$ $mod$ $b)$

于是令$a_{1}=b,b_{1}=a$ $mod $ $b$，輾轉一次即變為$a_{1}x_{1}+b_{1}y_{1}=gcd(a_{1},b_{1})$

以此類推，直至$b_{n}=0$，此時方程化為$a_{n}x_{n}=gcd(a_{n},0)$

顯然取$x_{n}=1$即可（$gcd(a_{n},0)$當然是$a_{n}$，因為$\frac{0}{a_{n}}=0$不是嗎...）

那在這個方程中其實我可以取$y_{n}$為任意值，但是為了計算簡便我們一般取$y_{n}=0$（不要作死地去取y為別的值，因為指不定后面的計算就給你整出點啥意外情況）

接下來討論怎么根據已有的$x_{k},y_{k}$反求$x_{k-1},y_{k-1}$

我們已知$a_{k}x_{k}+b_{k}y_{k}=gcd(a_{k},b_{k})$

但其實右側的值始終為$1$

也就是可以寫成這樣的形式：$a_{k-1}x_{k-1}+b_{k-1}y_{k-1}=a_{k}x_{k}+b_{k}y_{k}$

注意到前后$a$和$b$的對應關系，也即：

$a_{k-1}x_{k-1}+b_{k-1}y_{k-1}=b_{k-1}x_{k}+(a$ $mod$ $b)y_{k}$

注意到$a$ $mod$ $b$等價于$a-[\frac{a}{b}]b$

于是上式即為：$a_{k-1}x_{k-1}+b_{k-1}y_{k-1}=b_{k-1}x_{k}+(a_{k-1}-[\frac{a_{k-1}}{b_{k-1}}]b_{k-1})y_{k}$

展開右側，既得$a_{k-1}x_{k-1}+b_{k-1}y_{k-1}=a_{k-1}y_{k}+b_{k-1}(x_{k}-[\frac{a_{k-1}}{b_{k-1}}]y_{k}$

對應相等，于是$x_{k-1}=y_{k},y_{k-1}=x_{k}-[\frac{a_{k-1}}{b_{k-1}}]y_{k}$

我們也就找出了這組對應關系

 一般線性同余方程的求解：

考慮方程$ax+by=c$，其中$gcd(a,b)|c$

那么首先我們可以在兩側同時除掉一個$gcd(a,b)$，得到一個新的方程$a^{'}x+b^{'}y=c^{'}$，其中$gcd(a^{'},b^{'})=1$，這兩個方程顯然是等價的

那么我們不妨先求解方程$a^{'}x+b^{'}y=1$，這樣的話只需要對求出的$x,y$同時乘c就是原方程的解了

 逆元的線性遞推

設$p$為質數，我們想求$a$對$p$的逆元

我們構造一個$p$的拆分$p=ka+b$，要求(1<a<p,b<a)

在兩側同時乘$a$和$b$的逆元$a^{-1},b^{-1}$

于是得到了$kb^{-1}+a^{-1}\equiv 0($ $mod$ $p)$

移項：$a^{-1}\equiv -kb^{-1}$

代入得：$a^{-1}\equiv [\frac{p}{a}] (p$ $mod$ $a)^{-1}$

 注意到$p$ $mod$ $a<a$，也即后面的逆元是已經求出來的，這樣我們就可以從前向后遞推了

中國剩余定理：

考慮模線性方程組$x_{i}\equiv a_{i}($ $mod$ $p_{i}),i=1,2...n$

令$M=\pi_{i=1}^{n}p_{i}$，$M_{i}=\frac{M}{p_{i}}$

求解$M_{i}$對$m_{i}$的逆元$M_{i}^{-1}=x_{i}$

則最終原方程的通解即為$X=\sum_{i=1}^{n}a_{i}x_{i}M_{i}+tM(t\in Z)$

接下來給出證明：

首先我們證明這個解的正確性（其實正確性好證，舉一個方程為例代入即可）

令$X=\sum_{i=1}^{n}a_{i}x_{i}M_{i}$

代入任意一個方程$j$，對$i!=j$，都有$a_{i}x_{i}M_{i}\equiv 0($ $mod$ $p_{j})$

對$i=j$，根據上述求解過程知：$x_{i}M_{i}\equiv 1($ $mod$ $p_{i})$

于是$a_{i}x_{i}M_{i}\equiv a_{i}($ $mod$ $p_{i})$

即$X=\sum_{i=1}^{n}a_{i}x_{i}M_{i}\equiv a_{i}($ $mod$ $p_{j})$

這也就證明了這個解的正確性

接下來證明這組解的唯一性：

令$x_{1},x_{2}$是上述方程組的兩個解，則對任意$i=1,2...n$，有$x_{1}-x_{2}\equiv 0($ $mod$ $p_{i})$

考慮$p_{1}，p_{2},...p_{n}$互質，所以$M|x_{1}-x_{2}$

也即任意兩個解之間的差距一定是$M$的整數倍

那么上述通解也就是合理且唯一的

降冪公式：$a^{m}\equiv$ $a^{m mod \phi(p)+\phi(p)}($ $mod$ $p)$

bzoj 3884

記$f(p)=2^{2^{2^{2}}}...$ $mod$ $p$

由降冪公式：$f(p)=2^{2^{2^{2}}mod \phi(p)+\phi(p)}$ $mod$ $p$

注意到上面仍是無窮，所以$f(p)=2^{f(\phi(p))+\phi(p)}$ $mod$ $p$

于是遞歸求解即可，邊界為$f(1)=0$

RSA算法的證明：

任意選擇兩個質數$p,q$，并構造$n_{1}=pq$,$n_{2}=(p-1)(q-1)$，則對于$?m\in(1,n_{1})$,對于所有$e\in[1,n_{2})$且e與n2互質，令$c=m^{e}$ $mod$ $n_{1}$, 取$d\in[1,n_{2})$且要求$ed$ $mod$ $n_{2}\equiv1$,則$c^w0obha2h00$ $mod$ $n_{1}\equiv m$

其實要認識到一點：由于$p,q$是質數，所以$\phi(n_{1})=n_{2}$

結合上面的表達式：$c=m^{e}$，于是$c^w0obha2h00=m^{de}$

考慮到$de\equiv 1 ($ $mod$ $n_{2})$，$n_{2}=\phi(n_{1})$

于是$m^{de}\equiv m^{de mod \phi(n_{1})}\equiv m($ $mod$ $n_{1})$

也就得出了結果

盧卡斯定理：

若$p$為質數，則$C^{m}_{n}\equiv C^{[\frac{m}{p}]}_{[\frac{n}{p}]}C^{mmodp}_{nmodp}$ $($ $mod$ $p)$       

證明：顯然$C_{p}^{m}\equiv 0($ $mod$ $p)$

我們用二項式定理來證明：令$n=sp+q$

則$(1+x)^{n}=(1+x)^{sp+q}=(1+x)^{sp}(1+x)^{q}=[(1+x)^{p}]^{s}(1+x)^{q}$

在模$p$意義下，$(1+x)^{p}=1+x^{p}$（根據我們最開始證明的等式，二項式展開即可）

于是我們有$(1+x)^{n}=(1+x^{p})^{s}(1+x)^{q}=\sum_{i=0}^{s}C_{s}^{i}x^{ip}\sum_{j=0}^{q}C_{q}^{j}x^{j}$

考慮$x^{tp+m}$項的系數，根據最初的表達式，其系數為$C_{sp+q}^{tp+m}$

根據推導出的表達式，顯然只能取$i=t,j=m$，于是其系數為$C_{s}^{t}C_{q}^{m}$

也即$C_{sp+q}^{tp+m}\equiv C_{s}^{t}C_{q}^{m}$，于是定理得證