# 數論

## 費馬小定理
($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)
$$

:::spoiler Code

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)\\
$$