紀錄一下數論

## 數論函數/算術函數 (Arithmetic Function) 指的是定義域在正整數 $\mathbb{Z^+}$, 對應域在複數 $\mathbb{C}$ 的函數: $$ f:\mathbb{Z^+} \rightarrow \mathbb{C} $$ 值得注意的是，它的定義域為正整數，**所以算術函數關注的主要是整數的整除性、因數關係、質因數對於函數本身的影響**，這句話聽起來非常數論，所以算術函數又稱為數論函數(我亂掰的)。 ## 積性函數 (Multiplicative Function) 如果一個算術函數 $f$ 滿足以下性質，則稱 $f$ 是積性函數: $$ \begin{align} &1. \ \ f(1)=1 \\ &2. \ \ \text{if} \ \ \gcd(a,b)=1, \ \text{then} \ \ f(ab)=f(a)f(b) \end{align} $$ 根據算術基本定理 $$ n=\prod_{i=1}^{r}{p_{i}^{k_i}}, \ \ p_i: \text{primes} $$ 因為 $p_{i}^{k_i}$ 兩兩互質，若要計算 $f(n)$，可用積性性質分解: $$ f(n)=\prod_{i=1}^{r}{f(p_{i}^{k_i})}=f(p_{1}^{k_1})f(p_{2}^{k_2})...f(p_{r}^{k_r}) $$ ## 一些常見的積性函數 ### 1. $\gcd(k,n)$, 當 $k$ 為定值 :::spoiler 積性欲證明: $$ \text{If } \gcd(n,m) = 1, \text{ then for any fixed } k \in \mathbb{Z}, \ \gcd(k,ab)=\gcd(k,a)\gcd(k,b) $$ 根據 $\text{Bézout's identity (gcd 的線性組合)}, \ 我們有$ $$ \begin{align} &\exists \ u,v, \in \mathbb{Z}\ \ \ \text{s.t.} \ \ \gcd(k,a)=uk+va \\ &\exists \ \alpha,\beta \in \mathbb{Z}\ \ \ \text{s.t.} \ \ \ \gcd(k,b)=\alpha k+\beta b \end{align} $$ 將 $\gcd(k,a)$ 與 $\gcd(k,b)$ 相乘: $$ \begin{align} \gcd(k,a)gcd(k,b) &= (uk+va)(\alpha k+\beta b) \\ &= u \alpha k^2+uk \beta b+va \alpha k+ va \beta b \\ &= (u \alpha k+ u \beta b + va \alpha)k + (v \beta)(ab) \end{align} $$ 因為$\gcd(k,a)\gcd(k,b)$ 存在於 $k$ 與 $ab$ 的線性組合中，通過簡單的計算，可以得到 $(1)$ 的結論: $$ \because \ \gcd(k,a)gcd(k,b) \in \{ xk+y(ab) \ | \ x,y \in \mathbb{Z} \} $$ $$ \begin{align} \because \ xk+y(ab) &= x(p \cdot \gcd(k,ab))+y(q \cdot \gcd(k,ab)) \ \text{for some } p, q \in \ \mathbb{Z} \\ &= \gcd(k,ab) \cdot (xp+yq) \end{align} $$ $$ \begin{align} \therefore \ \gcd(k,ab) \ | \ \gcd(k,a)\gcd(k,b) \ --------(1) \end{align} $$ 再來，根據 $\gcd$ 的定義，有 $$ \begin{align} &\gcd(k,a) \ | \ k \ , \ \gcd(k,b) \ | \ k\\ &\gcd(k,a) \ | \ a \ , \ \gcd(k,b) \ | \ b \end{align} $$ $$ \begin{align} &\because \gcd(a,b)=1\\ &\therefore \gcd(\gcd(k,a), \gcd(k,b))=1 \\ &\because \gcd(\gcd(k,a), \gcd(k,b))=1 \ \ \text{and} \ \ \gcd(k,a) \ | \ k \ , \ \gcd(k,b) \ | \ k\\ &\therefore \gcd(k,a)\gcd(k,b) \ | \ k \ --------------(2) \\\\ &\because \gcd(k,a) \ | \ a \ , \ \gcd(k,b) \ | \ b\\ &\therefore \gcd(k,a)\gcd(k,b) \ | \ ab \ -------------(3)\\ \end{align} $$ $\text{By (2)(3),}$ $$ \gcd(k,a)\gcd(k,b) \ | \ \gcd(k,ab) \ --------(4) $$ $\text{By (1)(4),}$ $$ \gcd(k,ab)=\gcd(k,a)\gcd(k,b) \ \ \blacksquare $$ ::: ### 2. 歐拉函數 $\varphi(n)$ $\varphi(n)$ : 小於等於 $n$ 的正整數中與 $n$ 互質的數字個數顯然的，當 $p$ 為質數， $\varphi(p) = p-1$ :::spoiler 積性欲證明 $$ \text{if} \ \gcd(a,b)=1, \ \text{then} \ \varphi(ab)=\varphi(a)\varphi(b) $$ 我們可以先把 $1, 2, ..., ab$ 數字全部列出來，建立一個 $a*b$ 的表格: $$ \begin{array}{|c|c|c|c|} \hline 1 & 2 & 3 & ... & b \\ \hline b+1 & b+2 & b+3 & ... & 2b \\ \hline \vdots & \vdots & \vdots & \ddots & \vdots \\ \hline (a-2)b+1 & (a-2)b+2 & (a-2)b+3 & ... & (a-1)b \\ \hline (a-1)b+1 & (a-1)b+2 & (a-1)b+3 & ... & ab \\ \hline \end{array} $$ 首先來看 $\varphi(b)$ 的部分，我們要引入一個好用的性質: $$ \gcd(a,b)=\gcd(a,b+ma)=\gcd(a+nb,b), \ \forall m,n \in \mathbb{Z} $$ 根據 $\varphi(b)$ 的定義，第一個row，也就是 $1,2,3,...,b$ 中共有 $\varphi(b)$ 的數字與 $b$ 互質，我們假設其中一個數字為 $k$ ，使用上述性質，有 $$ \gcd(k,b)=\gcd(k+nb,b)=1, \ \forall n \in \mathbb{Z} $$ 意即，共有 $\varphi(b)$ 個cloumn 與 $b$ 互質。 接著來看 $\varphi(a)$ 的部分，首先介紹完全剩餘系的概念: $$ \mathbb{Z}_n = \{ 0,1,...,n-1 \} $$ 稱模 $n$ 的完全剩餘系，也就是任意整數除以 $n$ 所有可能的餘數集合，而他有如下性質: $$ \text{If } \gcd(n,m) = 1, \text{ then for any fixed } k \in \mathbb{Z}, \ \{\, (k + m a) \bmod n \mid a \in \mathbb{Z}_n \,\} = \mathbb{Z}_n $$ 也就是說，當 $\gcd(n,m)=1$ ，你對 $\mathbb{Z}_n$ 做伸縮(乘以 $m$ 倍)和平移(加 $k$ )，模 $n$ 後的集合仍然是 $\mathbb{Z}_n$ 。有了以上知識，很明顯可以看出，表格中每一個column都是 $\mathbb{Z}_a$ 乘 $b$ 加 $k$ 的結果，因為 $\gcd(a,b)=1$ ，所以可以把每個column看成 $\mathbb{Z}_a = \{ 0,1,...,a-1 \}$ 就好。根據 $\varphi(a)$ 的定義， $0,1,...,a-1$ 中共有 $\varphi(a)$ 個數字與 $a$ 互質，意即，有 $\varphi(a)$ 個row與 $a$ 互質。 有 $\varphi(a)$ 個row與 $a$ 互質，並且有 $\varphi(b)$ 個cloumn 與 $b$ 互質，把row視為橫線，column視為直線，橫線與直線的交點不正是同時與 $a、b$ 兩數互質的數字嗎，假設該數字為 $k$ $$ \gcd(k,a)=1, \ \gcd(k,b)=1 \ \Longrightarrow \ \gcd(k,ab)=1 $$ 這是很明顯的事實，因此橫線與直線的交點數量 $\varphi(a)\varphi(b)$ 即為 $1,2,...,ab$ 中與 $ab$ 互質的數字數量 $\varphi(ab)$。 $$ \varphi(ab) = \varphi(a)\varphi(b) \ \ \blacksquare $$ ::: :::spoiler 質數冪次取值當 $p$ 為質數時，我們可以輕鬆求出 $\varphi(p^k)$。因為 $p^k$ 只有 $p$ 這一個質因數，因此除了 $p$ 的倍數外，其他數都與 $p^k$ 互質。 $$ \varphi(p^k) = p^k-\frac{p^k}{p}=p^k-p^{k-1}=(p-1)p^{k-1} $$ ::: 歐拉函數有以下公式: $$ \varphi(n) = n \prod_{i=1}^r{(1-\frac{1}{p_i})}, \ \ p_i:\text{prime factors of } n $$ :::spoiler 公式推導運用算術基本定理 $$ n=\prod_{i=1}^{r}{p_{i}^{k_i}}, \ \ p_i: \text{primes} $$ 因為 $p_i^{k_i}$ 兩兩互質，因此使用積性性質: $$ \varphi(n)=\prod_{i=1}^{r}{\varphi(p_{i}^{k_i})} $$ 再利用質數冪次取值的技巧: $$ \varphi(n)=\prod_{i=1}^{r}{p_i^{k_i-1}(p_i-1)} $$ 整理一下，最後得: $$ \varphi(n) = n \prod_{i=1}^r{(1-\frac{1}{p_i})} \ \ \blacksquare $$ ::: 計算 $\varphi(n)$ 看似需要對 $n$ 做質因數分解，但我們其實可以用線性篩以 $O(n)$ 時間建表。 :::spoiler 線性篩 ::: 線性篩的基本思想是利用 **最小質因數** 來篩數字，要找 $\varphi(n)$ ，我們首先找出 $\varphi(n)$ 和其最小質因數 $p$ 的關係，我們分成三個case。 ### 3. 莫比烏斯函數 $\mu(n)$ ### 4. 常數函數 $1(n)$ ### 5. 恆等函數 $\text{id}(n)$