數論合集
數論合集
\(Part\) \(1\): 裴蜀定理
定理：對於任意整數 \(a,b\) ，記 \(\gcd(a,b)=d\) ，則對於所有整數 \(x,y\) ，都有 \(d|ax+by\) ，特別的，一定存在整數 \(x,y\) 使得 \(ax+by=d\) 。
證明：因為 \(d=gcd(a,b)\) ，所以有 \(a\equiv b\equiv 0\pmod d\) ，所以 \(ax+by\equiv 0\times x+0\times y\equiv 0\pmod d\) ，所以 \(d|ax+by\) 。
記所有 \(ax+by\) 的集合為 \(S\) ，設 \(w=ax_1+by_1\) 是 \(S\) 中的最小正值，則有 \(w\ge d\) ；
對於所有 \(u=ax_2+by_2\in S\) ，有 \(u\mod w=u-kw=(x_1-kx_2)a+(y_1-ky_2)b\in S\) ，又因為 \(0\le u\mod w<w\) ，所以 \(u\mod v\) 只能等於 \(0\)，即對於所有 \(u\in S\) ，都有 \(w|u\) 。
又因為 \(a,b\in S\) ，所以 \(w|a, w|b\) ， 所以 \(w\) 是 \(a,b\) 的公因數，所以有 \(w\le d\) 。
綜上所述 , \(w=d\) ，即 \(d\) 是集合 \(S\) 中的最小正值，證畢。
\(Part\) \(2\): 費馬小定理
定理：若 \(p\) 為質數，則對於任意自然數 \(a\) ，都有 \(a^{p-1}\equiv 1\pmod p\) ，即 \(a^p\equiv a\pmod p\) 。
證明如下：
\(\bullet\)引理1：一個數 \(a\) 在模 \(p\) 意義下的乘法逆元存在的充要條件是 \(\gcd(a,b)=1\) 。
證明：若方程 \(ax\equiv 1\pmod p\) 有解，相當於 \(ax=py+1\) 即 \(ax+py=1\) 有解，由裴屬定理可得，如果方程有解當且僅當 \(\gcd(a,p)=1\) ，且此時 \(ax+py\) 的最小正值為 \(1\) ，充分性和必要性同時得證。
\(\bullet\)引理2：對於正整數 \(a,b,c,p\) ，且 \(\gcd(c,p)=1\) 如果 \(ac\equiv bc\pmod p\) ，則有 \(a\equiv b\pmod p\) 。
證明：由於 \(\gcd(c,p)=1\) ，由引理 \(1\) 可得 \(c\) 在模 \(p\) 意義下存在乘法逆元，所以 \(ac\equiv bc\pmod p\rightarrow ac\times c^{-1}\equiv bc\times c^{-1}\pmod p\rightarrow a\equiv b\pmod p\) 。
\(\bullet\)證明：
我們構造兩個序列 \(S={1,2,…，p-1}\) ，\(T=a,2a,3a,…,(p-1)a\) ，其中 \(a\not \equiv 0\pmod p\) 。
首先由引理 \(2\) 可知，\(T\) 中元素兩兩不同，因為如果 \(i a\equiv j a\pmod p\) ，則 \(i=j\) ，所以 \(S\) 與 \(T\) 同構。
所以 \(\prod_{i\in S}i=\prod_{i\in T}i\) ，即 \((p-1)!\equiv a^{p-1}(p-1)!\pmod p\) 。
又因為 \(p\) 為質數，所以 \(\forall 1\le i<p\) ，\(\gcd(i,p)=1\) ，所以 \(\gcd((p-1)!,p)=1\) ，那麼再次應用引理 \(2\) ，可得：
\(a^{p-1}(p-1)!\equiv (p-1)!\pmod p\rightarrow a^{p-1}\equiv 1\pmod p\) ，證畢。
\(Part\) \(3\): 歐拉函數相關
定義：在 \(1\) ~ \(n\) 中與 \(n\) 互質的數的個數稱為 \(n\) 的歐拉函數，記為 \(\varphi_n\) 。
\(Part\) \(3.1\): 歐拉函數的性質
性質\(1\). 如果 \(x\) 是質數，則 \(\varphi_x=x-1\) 。
性質\(2\). 歐拉函數是積性函數，即如果 \(\gcd(x,y)=1\) ，則 \(\varphi_{x y}=\varphi_x\varphi_y\) 。
性質\(3\).\(\varphi_{p^k}=p^{k-1}(p-1)\) 。
性質\(4\). 若 \(x\) 的唯一分解是 \(x=\prod_{}{p_i^{k_i}}\) ，則 \(\varphi_x=n\prod_{}{(1-\frac{1}{p_i})}\) 。
\(Part\) \(3.2\): 歐拉函數的求解
單個求解時： 利用性質 \(4\) ，試除法求出所有質因數，時間複雜度 \(O(\sqrt{n})\) 。
多個求解時： 利用性質 \(2\) 和性質 \(3\) ，使用線性篩求積性函數，時間複雜度 \(O(n)\) 。
\(Code:\)
inline void prework() {
for(int i=2;i<=n;++i) {
if(!vis[i]) vis[i]=1,pri[++cnt]=i,phi[i]=i-1;
for(int j=1;j<=cnt && i*pri[j]<=n;++j) {
vis[i*pri[j]]=1;
if(i%pri[j]) phi[i*pri[j]]=phi[i]*(pri[j]-1);
else phi[i*pri[j]]=phi[i]*pri[j];
if(i%pri[j]==0) break;
}
}
}
\(Part\) \(3.3\): 歐拉反演：
\(n=\sum_{d|n}\varphi_d\)
證明：記 \(f_x=\sum_{i=1}^{n}{[\gcd(i,n)=x]}\) ，則顯然有 \(n=\sum_{i=1}^n f_i=\sum_{d|n}f_d\) 。
又因為 \(f_x=\sum_{i=1}^{n}{[\gcd(i,n)=x]}=\sum_{i=1}^{\lfloor\frac{n}{x}\rfloor}{[\gcd(i,\frac{n}{x})=1]}=\varphi_{\frac{n}{x}}\) ，所以 \(n=\sum_{d|n}{f_d}=\sum_{d|n}\varphi_{\frac{n}{d}}\) ，根據約數的對稱性，可得 \(n=\sum_{d|n}\varphi_d\) ，證畢。
\(Part\) \(3.4\): 歐拉定理
定理：對於正整數 \(a,p\)，若 \(\gcd(a,b)=1\) ，則有 \(a^{\varphi_p}\equiv 1\pmod p\) 。
證明： 同理於費馬小定理的證明，我們依然構造兩個序列，\(S={r_1,r_2,…,r_{\varphi_p}}\) ， 表示所有小於 \(p\) 且與 \(p\) 互質的數，再構造 \(T={a r_1,a r_2,…,ar_{\varphi_p}}\) 。
若 \(a r_i\equiv q r_j\pmod p\) ，那麼就有 \(i=j\) ，又因為 \(\gcd(a,p)=1\bigwedge\gcd(r_i,p)=1\rightarrow \gcd(a r_i,p)=1\) ，所以序列 \(S\) 與 \(T\) 同構。
記 \(w=\prod_{i=1}^{\varphi_p}{r_i}\) ，則有 \(a^{\varphi_p}w\equiv w\pmod p\) ，又因為 \(\gcd(w,p)=1\) ，所以 \(w\) 在模 \(p\) 意義下存在逆元，所以有：
\(a^{\varphi_p}w\equiv w\pmod p\rightarrow a^{\varphi_p}w\times w^{-1}\equiv w\times w^{-1}\pmod p\rightarrow a^{\varphi_p}\equiv 1\pmod p\) ，證畢。
\(Part\) \(3.4.1\): 拓展歐拉定理
定理：\(\forall a,p\)都有
\begin{cases}
a^{b\bmod\varphi(p)},\,&\gcd(a,\,p)=1\\
a^b,&\gcd(a,\,p)\ne1,\,b<\varphi(p)\\
a^{b\bmod\varphi(p)+\varphi(p)},&\gcd(a,\,p)\ne1,\,b\ge\varphi(p)
\end{cases}
\pmod p
\]
證明如下：
我們嘗試證明 \(\forall a,p,a^{n\varphi_p+r}\equiv a^{\varphi_p+r}\pmod p\) ，其中 \(0\le r<\varphi_p,n\ge2\) 。
記 \(a\) 的完全分解為 \(a=\prod_{}{p_i^{c_i}}\) 。
引理 \(1\). \(\forall p_i,\varphi_{p_i^{c_i}}|\varphi_p\) ：
因為 \(\gcd(p_i^{c_i},p)=1\) ，由歐拉函數的積性可知，\(\varphi_p=\varphi_{p_i^{c_i}}\varphi_{\frac{p}{p_i^{c_i}}}\)，所以可得 \(\varphi_{p_i^{c_i}}|\varphi_p\) 。
\(\bullet\) 證明 \(1\). 對於 \(a\) 是質數及質數的冪的情況，上式成立：
記 \(a=x^y , p=x^kb\) ，其中 \(\gcd(a,b)=1\) ，若 \(k=0\) ，則 \(\gcd(a,p)=1\)， 由歐拉定理可知 \(a^{\varphi_p}\equiv 1\pmod p\rightarrow a^{n\varphi_p+r}\equiv a^{\varphi_p+r}\pmod p\) ；
若 \(k>0\) ，由引理 \(1\) 可得 \(\varphi_b|\varphi_p\) ，因為 \(\gcd(b,p)=1\) ，所以由歐拉定理得 \(a^{\varphi_b}\equiv 1\pmod b\rightarrow x^{y\varphi_p}\equiv 1\pmod b\) 。
記 \(x^{y\varphi_p}=ub+1\) ，兩邊同時乘上 \(x^k\) ，得到 \(x^{y\varphi_p+k}=um+x^k\rightarrow x^{\varphi_p+k}\equiv x^k\pmod p\) 。
因為 \(\varphi_p=\varphi_{x^k}\varphi_b=x^{k-1}(x-1)\varphi_b\) ，由於 \(x>=2\) （質數），所以 \(x^{k-1}(x-1)\ge k\) ，即 \(\varphi_p\ge k\) ，所以有推導如下：
\(x^{\varphi_p+k}\equiv x^k\pmod p\rightarrow x^{\varphi_p+k}\times x^{\varphi_p+r-k}\equiv x^k\times x^{\varphi_p+r-k}\pmod p\rightarrow x^{2\varphi_p+r}\equiv x^{\varphi_p+r}\pmod p\) ，由數學歸納法可以得到 \(x^{n\varphi_p+r}\equiv x^{\varphi_p+r}\pmod p\)
所以 \((x^{n\varphi_p+r})^y\equiv(x^{\varphi_p+r})^y\pmod p\rightarrow a^{n\varphi_p+r}\equiv a^{\varphi_p+r}\pmod p\) ，證畢。
\(\bullet\) 證明 \(2\). 對於 \(a\) 不是質數或者質數的冪的情況，上式依然成立：
由證明 \(1\) 可以得到 \(a^{n\varphi_p+r}\equiv\prod(p_i^{c_i})^{n\varphi_p+r}\equiv\prod(p_i^{c_i})^{\varphi_p+r}\equiv a^{\varphi_p+r}\pmod p\) ，證畢。
綜上所述，\(\forall a,p,a^{n\varphi_p+r}\equiv a^{\varphi_p+r}\pmod p\) ，拓展歐拉定理得證。
\(Part\) \(4\): [exGCD]拓展歐幾里得演算法
——用於求解形如 \(ax+by=k\) 的二元一次方程。
設 \(\gcd(x,y)=d\) ，由裴屬定理可知，方程有解的條件是 \(d|k\) ，我們首先考慮如何求解 \(ax+by=d\) 。
思考我們使用歐幾里得演算法求 \(gcd\) 的方式：
int Gcd(int u,int v){
return v?Gcd(v,u%v):u;
}
當 \(v=0\) 時，\(u=d\) ，此時方程 \(au+bv=d\) 的解為 \(a=1,b=0\) 。考慮從這一層的答案推導出上一層的答案，\(u=v’,v=u’-\lfloor\frac{u’}{v’}\rfloor\times v’\) ，帶入得 \(au+bv=d\rightarrow av’+b(u’-\lfloor\frac{u’}{v’}\rfloor\times v’)=d\rightarrow bu’+(a-\lfloor\frac{u’}{v’}\rfloor)v’=d\) ，所以上一層的解為 \(a’=b,b’=a-\lfloor\frac{u’}{v’}\rfloor\) ，遞歸求解即可。
\(Code:\) 時間複雜度 \(O(log_{}{n})\)
int exgcd(int a,int b,int &x,int &y) {
if(!b) {x=1,y=0; return a;}
int ans=exgcd(b,a%b,x,y);
int x0=x; x=y,y=x0-y*(a/b);
return ans;
}
然後 \(ax+by=k\) 的一組解就是 \(\frac{bk}{d}x+\frac{ak}{d}y=k\) 。
通解： 方程 \(ax+by=d\) 的所有整數解為 \((a-\frac{wy}{d})x+(b+w\frac{wx}{d})y=d\) 。
\(Part\) \(5\): [CRT]中國剩餘定理
——求解同餘方程組
對於同餘方程組如下，
x\equiv a_1\pmod {p_1}\\
x\equiv a_2\pmod {p_2}\\
……\\
x\equiv a_n\pmod {p_n}\\
\end{cases}
\]
其中 \(p_1,p_2,…,p_n\) 兩兩互質。中國剩餘定理說明了該方程一定有解，且解在模 \(M=\prod_{i=1}^{n}{p_i}\) 意義下唯一，解為 \(x=\sum_{i=1}^{n}{\frac{a_i M}{p_i}inv_i}\mod M\) ，其中 \(inv_i\) 為 \(\frac{M}{p_i}\) 在模 \(p_i\) 意義下的逆元（可以證明一定存在）。
\(\bullet\) 首先我們證明我們構造的這個解的正確性：
對於一個同餘方程 \(x\equiv a_i\pmod {p_i}\) ，可以發現對於所有 \(i\not=j\) ，因為 \(p_i|M\)，所以有 \(\frac{M}{p_j}\equiv0\pmod {p_i}\) ，所以 \(\sum_{j\not=i}{\frac{a_j M}{p_j}inv_j}\equiv0\pmod {p_i}\) ，因此我們只需要關心 \(\frac{a_i M}{p_i}inv_i \mod p_i\) 的值，而這個值顯然為 \(a_i\mod p_i\) ，即對於所有 \(1\le i\le n\) ，\(x\equiv a_i\pmod {p_i}\)，證畢。
\(\bullet\) 其次我們來證明解在模 \(M\) 下的唯一性：
引理：對於正整數 \(a,b,c\) ，如果 \(b|c\) ，則有 \(a\equiv (a\mod c)\pmod b\) 。
證明：設 \(a=k c+r\) ，因為 \(b|c\) ，所以 \(b|k c\) ，則 \(a\equiv(kc+r)\equiv r\equiv(a\mod c)\pmod b\) 。
接著繼續證明， 如果方程有兩個解 \(x\) 與 \(x’\)，那麼 \(\forall 1\le i\le n\) ，由引理可知，都有 \((x\mod M)\equiv (x’\mod M)\pmod {p_i}\)。
即 \(\forall 1\le i\le n\)， \(p_i|(x\mod M)-(x’\mod M)\) ，又因為 \(p_i\) 兩兩互質，所以 \(M|(x\mod M)-(x’\mod M)\rightarrow x\equiv x’\pmod M\) ，證畢。
\(Part\) \(5.1\): [exCRT]拓展中國剩餘定理
——合併同餘方程組
對於同餘方程組如下，
x\equiv a_1\pmod {p_1}\\
x\equiv a_2\pmod {p_2}\\
……\\
x\equiv a_n\pmod {p_n}\\
\end{cases}
\]
與CRT不同的是，\(p_1,p_2,……,p_n\) 不再兩兩互質，我們可以通過合併同餘方程來求解上述同餘方程組。
考慮每次我們需要將兩個同餘方程：
x\equiv a_1\pmod {p_1}\\
x\equiv a_2\pmod {p_2}\\
\end{cases}
\]
合併成一個方程 \(x\equiv a\pmod {lcm(a_1,a_2)}\) 。
記 \(a=k_1 p_1+a_1=k_2 p_2+a_2\) ，即 \(k_1p_1-k_2p_2=a_2-a_1\) ，是一個線性方程組，此時：
若 \(a_2-a_1\not\equiv0\pmod {\gcd(p_1,p_2)}\)，由裴屬定理說明該同餘方程組已經無解了。
若 \(a_2-a_1\equiv0\pmod{\gcd(p_1,p_2)}\)，此時我們利用exGCD求出一組解 \(k_1,k_2\) ，此時滿足 \(x=k_1p_1+a_1=k_2p_2+a_2\) ，所以兩個同餘方程被我們合併成了一個：\(x\equiv(k_1p_1+a_1)\pmod {lcm(p_1,p_2)}\) ，可以發現所有解之差均為 \(w\times lcm(p_1,p_2)\) 的形式，因此合併出來的結果在模 \(lcm(p_1,p_2)\) 意義下是唯一的。
對於所有同餘方程，我們依次合併即可。
