---
# System prepended metadata

title: 紀錄一下數論

---

## 數論函數/算術函數 (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}
$$

<br><br>

首先來看 $\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$ 互質。

<br><br>

接著來看 $\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$ 互質。

<br><br>

有 $\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}
$$
:::

<br>

歐拉函數有以下公式:
$$
     \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
$$
:::

<br>

計算 $\varphi(n)$ 看似需要對 $n$ 做質因數分解，但我們其實可以用線性篩以 $O(n)$ 時間建表。

:::spoiler 線性篩

:::

線性篩的基本思想是利用 **最小質因數** 來篩數字，要找 $\varphi(n)$ ，我們首先找出 $\varphi(n)$ 和其最小質因數 $p$ 的關係，我們分成三個case。

### 3. 莫比烏斯函數 $\mu(n)$

### 4. 常數函數 $1(n)$

### 5. 恆等函數 $\text{id}(n)$