數論

費馬小定理

(\(p\)為質數)
\[a^p≡a\ (mod\ p)\]
\[a^{p-1}≡1\ (mod\ p)\]

Proof

首先先考慮\((b+1)^p\)的展開，模p：

\[ (b+1)^p= (\frac{p}{0})b^p+(\frac{p}{1})b^{p-1}+(\frac{p}{2})b^{p-2}...+(\frac{p}{p})b^{0}\ (mod\ p) \]

假設\((\frac{p}{k})\)，k != 0 or p，分子有p，分母沒有p，因此p不會被約分掉，\((\frac{p}{k})\)是p的倍數，模p=0，因此

\[ (b+1)^p\ (mod\ p)\\ ≡(\frac{p}{0})b^p+(\frac{p}{p})b^{0}\ (mod\ p)\\ ≡b^p+1\ (mod\ p) \]

接著把\(b^p\)轉成((\(b\)-1)+1)\(^p\)的形式繼續展開

\[ (b+1)^p\ (mod\ p)\\ ≡b^p+1\ (mod\ p)\\ ≡((b-1)^p+1)+1\ (mod\ p)\\ ≡(((b-2)^p+1)+1)+1\ (mod\ p)\\ .\\ .\\ ≡(b+1)個1\ (mod\ p)\\ ≡b+1\ (mod\ p) \]

把\(b+1\)換成\(a\)

\[ a^p≡a\ (mod\ p) \]

歐拉函數

\[\varphi (x)\]

定義

在小於等於\(x\)的正整數中，與\(x\)互質的個數
(特別定義\(\varphi(1)=1\))

當\(x\)為質數時

(\(p\)表質數)
\[\varphi (p)=p-1\]
除了\(p\)自己本身以外，其他數都與\(p\)互質。

當\(x\)為質數的次方時

(\(p\)表質數，n表次方)
\[\varphi (p^n)=p^n-p^{n-1}=p^n(1-\frac{1}{p})\]

因為和質數的次方不互質的數很少，因此可由所有的數減去和\(p^n\)不互質的數來計算。

如果要計算有幾個數不和\(p^n\)互值，那該數的質因數中一定要有至少一個質因數和\(p^n\)的質因數相同，也就是要有\(p\)，因此可由\(p\)的倍數去構造，且要小於等於\(p^n\)，所有的可能為：
\[ p*1,p*2,p*3\ ...\ ,p*p^{n-1}=p^n \]
因此不與\(p^n\)互值的個數有\(p^{n-1}\)個

推廣到多維

(\(P_i\)為質因數分解的底數)
\[ \varphi(n)=n(1-\frac1 P_1)(1-\frac1 P_2)...(1-\frac1 P_m) \]

一個數的質因數分解可寫成第二點的形式

\(5600=2^5×5^2×7^1\)

由於歐拉函數是積性函數

\(\varphi(5600)=\varphi(2^5)×\varphi(5^2)×\varphi(7^1)\)

因此
\[ n={P_1}^{k_1}×{P_2}^{k_2}...×{P_m}^{k_m}\\ \varphi(n)=\varphi({P_1}^{k_1})×\varphi({P_2}^{k_2})...×\varphi({P_m}^{k_m})\\ ={P_1}^{k_1}(1-\frac1 P_1)×{P_2}^{k_2}(1-\frac1 P_2)...×{P_m}^{k_m}(1-\frac1 P_m)\\ =n(1-\frac1 P_1)(1-\frac1 P_2)...(1-\frac1 P_m) \]

int phi(int n){
    if(n==1) return 1;
    int ans=n;
    for(int i=2;i*i<=n;i++){
        if(n%i==0){
            while(n%i==0) n/=i;
            ans=ans*(i-1)/i;
            
        }
    }
    if(n!=1) ans=ans*(n-1)/n;
    return ans;
}

尤拉定理

(\(p\)為質數)
\[a^{\varphi (p)}≡1\ (mod\ p)\]

尤拉定理為費馬小定理的推廣，由於

\[\varphi(p)=p-1\]

因此費馬小定理可改寫成
\[ a^{p}≡a\ (mod\ p)\\ a^{p-1}≡1\ (mod\ p)\\ a^{\varphi (p)}≡1\ (mod\ p)\\ \]