[數論] 進階質數與模運算

2021-07-29

[2021 Jul 29] 初稿
[2021 Aug 17] 我發現 Miller-Rabin 質數測試部分是爛掉的，之後會把這部分重寫，請先不要參考
[2025 Feb 10] 拿掉質數跟原根，以及重新修整一些敘述。這兩個主題有機會的話會（大概不是在這裡）補上。

質數

待補。

除法

Newton–Raphson 除法

與直式除法不同的是，Newton–Raphson 除法的目的是在除法的式子中：

N / D = Q

如果能找到 $D$ 的乘法反元素（即倒數），就可以用乘法的方式去做除法。

所以如果能找到一個方程式 $f (x)$ 讓 $x = 1 / D$ 是其中的一根，就可以用牛頓法去求解，先觀察一下牛頓法的迭代過程：

x_{i + 1} = x_{i} - \frac{f (x_{i})}{f^{'} (x_{i})}

最好想到的方程式是 $f (x) = D x - 1$ ，然而微分過後會出現 $f^{'} (x) = D$ ，分母有出現 $D$ ，然而我們還沒計算出 $D$ 的反元素，這個方程式是不可行的，所以我們把原式 $x = 1 / D$ 換成 $D = 1 / x$ ，就有 $f (x) = 1 / x - D$ ，微分過後會出現 $f^{'} (x) = - 1 / x^{2}$ ，此時代入牛頓法的公式，會得到：

x_{i + 1} = x_{i} - \frac{\frac{1}{x_{i}} - D}{- \frac{1}{{x_{i}}^{2}}} = x_{i} - \frac{x_{i} - D {x_{i}}^{2}}{- 1} = x_{i} + x_{i} - D {x_{i}}^{2} = x_{i} (2 - D x_{i})

雖然 $x_{i} + x_{i} - D {x_{i}}^{2}$ 和 $x_{i} (2 - D x_{i})$ 看起來很像，不過計算時用後者，意義上的精度會是前者的兩倍。

如果把第 $i$ 步的錯誤設為 $ε_{i} = 1 - D x_{i}$ ，則第 $i + 1$ 步的錯誤就會是：

ε_{i + 1} = 1 - D x_{i + 1} = 1 - D x_{i} (2 - D x_{i}) = 1 - 2 D x_{i} - D^{2} x_{i}^{2} = (1 - D x_{i})^{2} = ε_{i}^{2}

也就是說誤差會持續被開平方根，但同時也表示初始值 $x_{0}$ 不能亂選，最終取得 $N$ 位精度需要 $O (\log N)$ 的時間。

進階模運算

數論函數

其實數論函數本身沒有什麼特殊的，基本上就是符合 $f : Z^{+} \to C$ 。簡單來說就是滿足吃進一個正整數，吐出一個 $Z$ 、 $R$ 或 $C$ 的都算。

積性函數

一個積性函數要滿足：

定義域是 $Z^{+}$ ，也就是說要是數論函數
當 $\gcd (a, b) = 1$ ， $f (a) f (b) = f (a b)$

以下都是積性函數：

$Φ (n)$ — 歐拉函數
$μ (n)$ — 莫比烏斯函數
- ${\begin{cases} μ (n) = 1 & n = 1 \\ μ (n) = (- 1)^{k} & n = p_{1} p_{2} \dots p_{k} \\ μ (n) = 0 & n 有次數大於 1 的質因數 \end{cases}$
$\gcd (n, k)$ （當 $k$ 固定）— 最大公因數
$1 (n)$ — 1 函數
- $1 (n) = 1$

另外積性函數有個很重要的性質：

n = p_{1}^{a_{1}} p_{2}^{a_{2}} \dots p_{k}^{a_{k}} ⟹ f (n) = f (p_{1}^{a_{1}}) f (p_{2}^{a_{2}}) \dots f (p_{k}^{a_{k}})

狄利克雷卷積

定義狄利克雷卷積的目的在於：讓數論函數的乘法是狄利克雷卷積、加法是普通加法，就可以讓數論函數是一個交換環（一個環但多滿足交換律）。

定義兩個數論函數的狄利克雷卷積如下：

(f * g) (n) = \sum_{d | n} f (d) g (\frac{n}{d})

注意它也有另一個形式：

(f * g) (n) = \sum_{d d^{'} = n} f (d) g (d^{'})

而狄利克雷卷積滿足下列運算：

交換律 $f * g = g * f$
- 證明：用第二種形式就很顯然，因為整數乘法有交換律。
結合律 $(f * g) * h = f * (g * h)$
- 證明：用第二種形式也很顯然，因為下面總和會是三個東西乘起來 $a b c = n$ 然後 $f (a) g (b) h (c)$ 的總和。
分配律 $f * (g + h) = f * g + f * h$
- 證明：可以自己驗。
有單位函數 $ϵ$ 使得 $f * ϵ = f$
- 其中 ${\begin{cases} ϵ (n) = 1 & n = 1 \\ ϵ (n) = 0 & otherwise \end{cases}$
對於任意數論函數 $f$ ，若 $f (1) \neq 0$ ，則存在唯一的 $f^{- 1}$ ，使得 $f * f^{- 1} = ϵ$
- 可以先構造，因為要有 $f (1) f^{- 1} (1) = 1$ ， $f^{- 1} (1) = f (1)^{- 1}$ ，
  而對 $n \neq 1$ ，有以下這件事：
  $\sum_{d | n} f (d) f^{- 1} (\frac{n}{d}) = 0$
  所以可以直接用 $f (1) f^{- 1} (n) = - \sum_{d | n, d \neq 1} f (d) f^{- 1} (\frac{n}{d})$ 推出 $f^{- 1} (n) = - \frac{\sum_{d | n, d \neq 1} f (d) f^{- 1} (\frac{n}{d})}{f (1)}$
- 因為前面有交換律所以自然會有 $f * f^{- 1} = f^{- 1} * f = ϵ$
- 假如有兩個 $g, h$ 都有 $f * g = f * h = ϵ$ ，那 $ϵ = f * h = f * g * g^{- 1} * h = f * g^{- 1} * h \Rightarrow g = h$ 所以 $g = h$ ，反元素唯一。
積性函數的狄利克雷卷積還是積性函數
- 證明：令 $\gcd (a, b) = 1$ ，
  $\begin{aligned} (f * g) (a b) & = \sum_{d | a b} f (d) g (\frac{a b}{d}) \\ = \sum_{d_{a} | a} \sum_{d_{b} | b} f (d_{a} d_{b}) g (\frac{a b}{d_{a} d_{b}}) \\ = \sum_{d_{a} | a} \sum_{d_{b} | b} f (d_{a}) f (d_{b}) g (\frac{a}{d_{a}}) g (\frac{b}{d_{b}}) \\ = \sum_{d_{a} | a} f (d_{a}) g (\frac{a}{d_{a}}) \sum_{d_{b} | b} f (d_{b}) g (\frac{b}{d_{b}}) \\ = (f * g) (a) (f * g) (b) \end{aligned}$
$f, g, f * g$ 三個裡面有兩個是積性的，那剩下的也是。
- 證明：如果 $f, g$ 是那直接根據上面。如果不是那不失一般性假設 $f, f * g$ 是。反證一下，根據良序定理（粗淺的說，我們可以把整數數對排好順序，然後找最小的東西）， $g$ 若不是積性，那可以找到最小的組合 $a, b$ 互質使得 $g (a) g (b) \neq g (a b)$ 。這邊最小的定義可以找 $a + b$ 最小的。這代表說所有 $a^{'} + b^{'} < a + b$ 都會還有 $g (a^{'}) g (b^{'}) = g (a^{'} b^{'})$ 。
  $\begin{aligned} (f * g) (a) (f * g) (b) & = \sum_{p q = a} f (p) g (q) \sum_{r s = b} f (r) g (s) \\ = \sum_{p q = a, r s = b} f (p) g (q) f (r) g (s) \\ = \sum_{p q = a, r s = b} f (p r) g (q) g (s) \\ = f (1) g (a) g (b) + \sum_{p q = a, r s = b, p r \neq 1} f (p r) g (q) g (s) \\ = f (1) g (a) g (b) + \sum_{x y = a b, p r \neq 1} f (p r) g (q s) & (*) \\ = f (1) g (a) g (b) + (f * g) (a b) - g (a b) \\ = g (a) g (b) + (f * g) (a b) - g (a b) \end{aligned}$
  $(*)$ 這步第一個是因為只有 $q s = a b$ 這組是不能用上面的方法拿掉的（這剛好也是我們想要的）。第二是因為 $(p, s), p ∣ a, s ∣ b$ 的所有方法會一一對應到 $x ∣ a b$ ，因為 $a, b$ 互質，任何質因數一定只有一邊有效。
  所以 $g (a) g (b) = g (a b)$ ，矛盾。 $g$ 是積性。
積性函數的反元素（不是反函數）還是積性函數
- 由上一點可證

莫比烏斯反演

首先，觀察到

\sum_{d | n} μ (d) = [n = 1]

原因是因為：假如 $n$ 有 $k$ 種質因數，

\sum_{d | n} μ (d) = (\binom{k}{0}) - (\binom{k}{1}) + (\binom{k}{2}) - \dots + (- 1)^{k} (\binom{k}{k}) = {\begin{cases} 1 & n = 1 \\ (1 - 1)^{k} = 0 & otherwise \end{cases}

（考慮到取二次方以上都是 $0$ ）

當 $n = 1$ ， $原式 = 1$ ，否則 $原式 = 0$ 。所以我們有 $\sum_{d | n} μ (d) = ϵ$ 。也就是說：

\sum_{d | n} μ (d) 1 (\frac{n}{d}) = ϵ (n) \Rightarrow μ * 1 = ϵ \Rightarrow μ^{- 1} = 1

根據這個性質，可以發現如果有兩個函數滿足 $F (x) = \sum_{d | x} f (d)$ ，就可以透過莫比烏斯函數的逆函數做出這個轉換：

F (x) = \sum_{d | x} f (d) 1 (\frac{n}{d})

F = f * 1 ⟹ F * μ = f

對於某些跟因數有關的函數可以做出這樣的轉換。

因數

因數個數

對於一個整數 $N$ ，他的因數個數是 $d (N)$ 。

簡單的因數個數 $d (N)$ 的上界是 $O (\sqrt{N})$ ，用於估計的話最實際的方法就是跑個爆搜去看看，不過因數個數也是有一個數學上的上界的，這邊會一步一步推導出來。

首先需要知道的有：

\begin{matrix} (1) & e^{x} \approx 1 + x + \frac{x^{2}}{2!} + \frac{x^{3}}{3!} + \dots \geq 1 + x \end{matrix}

（在 $x$ 很小的時候， $e^{x}$ 的泰勒展開式。）

接下來，如果 $N$ 有 $k$ 個質數，可以把 $N$ 表示成：

\begin{matrix} (2) & N = p_{1}^{a_{1}} \dots p_{k}^{a_{k}} \end{matrix}

然後又由一點點的排列組合， $d (N)$ 可以表示為：

\begin{matrix} (3) & d (N) = (a_{1} + 1) \dots (a_{k} + 1) \end{matrix}

現在要證明的是，對於任何 $ε > 0$ ，都有一個常數 $C_{ε}$ 使得：

\begin{matrix} (4) & d (N) \leq C_{ε} N^{ε} \end{matrix}

換句話說就是：

d (N) = o (N^{ε})

證明的方式是，首先，把 $(4)$ 寫成這個樣子：

\begin{matrix} (5) & \frac{d (N)}{N^{ε}} \leq C_{ε} \end{matrix}

左邊的部分用 $(2) (3)$ 帶入，得到：

\begin{matrix} (6) & \prod_{i = 1}^{k} \frac{a_{i} + 1}{p_{i}^{ε a_{i}}} \end{matrix}

把每個質因數分開討論，分母是指數成長，分子是線性成長，所以在這個條件下 $a_{i}$ 夠大時分母會超過分子。但是 $ε$ 是可以任意選的，所以可能有些組合會讓分子大於分母，不過可以發現，要達成分子大於分母，必須要 $a_{i}$ 夠小、 $p_{i}$ 也夠小。

對於夠大的質數，想要比較的是 $p_{i}^{ε a_{i}} \geq a_{i} + 1$ 。

由於 $e^{a_{i}} \geq a_{i} + 1$ （使用 $(1)$ 的泰勒展開式），可以先確定當 $p_{i}^{ε a_{i}} \geq e^{a_{i}} \geq a_{i} + 1$ 的時候， $p_{i} \geq e^{1 / ε}$ ，而且這一項的貢獻最多只有 $1$ 。

那對於 $p_{i} < e^{1 / ε}$ 的質數呢？
由於 $a_{i} \to \infty$ 的時候， $\frac{a_{i} + 1}{p_{i}^{ε a_{i}}}$ 會趨近於 $0$ ，所以這個 $\frac{a_{i} + 1}{p_{i}^{ε a_{i}}}$ 一定會有某個常數 $C_{p_{i}, ε}$ 是他的上界，因此，所有小於 $e^{1 / ε}$ 的質數都只有對 $(6)$ 有有限度的貢獻，但是總共的小質數數量也被 $ε$ 給限制住了，所以 $(6)$ 就會小於某個只隨著 $ε$ 變動的常數 $C_{ε}$ ，因此原式得證。

競程中似乎有一個上界是 $O (\sqrt[3]{N})$ ，這個上界可以用剛剛所證明的代進數字，不過這樣估因為常數的關係會有點不準。

有了這個上界之後，可以更進一步把他限制得更緊：

首先，要達到更緊的上界，要先把 $C_{ε}$ 求出比較精確的值，回去考慮 $(6)$ ：

\begin{matrix} (6, revisited) & \prod_{i = 1}^{k} \frac{a_{i} + 1}{p_{i}^{ε a_{i}}} \end{matrix}

分母的部分可以用剛剛用過的 $(1)$ （泰勒展開式）處理一下：

p_{i}^{ε a_{i}} = e^{ε a_{i} \ln p_{i}} \geq 1 + ε a_{i} \ln p_{i}

所以

\begin{matrix} (7) & \frac{a_{i} + 1}{p_{i}^{ε a_{i}}} \leq \frac{a_{i} + 1}{1 + ε a_{i} \ln p_{i}} \leq O (\frac{1}{ε \log p_{i}}) \end{matrix}

當然這個上界可以再逼近一點，不過 $e^{x}$ 的泰勒展開式在 $x$ 很小的時候相當的精確，所以能逼近的不多。

把 $(7)$ 代入 $(6)$ ，會發現 $(6)$ 的上界是：

\prod_{p < e^{1 / ε}} O (\frac{1}{ε \log p_{i}})

為了方便討論，把小於 $e^{1 / ε}$ 的質數的上界設為 $e^{1 / ε}$ 、 $\log p_{i}$ 的上界設為 $\log 2$ 並當作常數，
當然還是可以再更逼近一點，但是這裡有個小技巧：
在處理 $A^{B}$ 這類的上界的時候，除了 $A$ 很接近 $1$ 的情況，否則把 $B$ 限縮在更好的上界會比限縮 $A$ 更有效。

(6) \leq O {(\frac{1}{ε})}^{e^{1 / ε}} = e^{e^{O (1 / ε)}}

（因為是漸近符號，可以這樣操作）

d (N) \leq e^{e^{O (1 / ε)}} N^{ε}

d (N) \leq N^{O (1 / \log \log N)}

質因數種類數

首先，先定義一個東西叫做質數階乘，對於質數 $P$ ：

$P # = \prod_{p \leq P and p is prime} p$

把質因數種類數表示成 $ω (n)$ ，顯然最差的狀況會發生在 $n$ 是質數階乘的時候，

根據一些酷酷的定理，有這個東西：

\log x # = ϑ (x) \sim x

所以 $p # = e^{(1 + o (1)) p}$ 。

令 $p$ 是第 $k$ 個質數，所以有 $p \sim k \ln k$ ，由於 $\log p # = ϑ (p) \sim p$ ，（ $ϑ$ 是 first Chebyshev function）這樣就會推導出：

k = ω (p #) = ω (e^{(1 + o (1)) p}) = ω (e^{(1 + o (1)) k \ln k}) = ω (k^{(1 + o (1)) k})

接下來就是把 $k$ 解出來了，因為：

p # = k^{(1 + o (1)) k}

所以：

k = \frac{\ln p #}{W (\ln p #)}

其中 $W$ 是 Lambert W function，簡單來說是 $f (x) = x e^{x}$ 的反函數，

把它用上下界代入：

k = \frac{\ln p #}{\log (\ln p #) - O (\log \log (\ln p #))} \sim \frac{\ln p #}{\log (\ln p #)} = O (\frac{\log p #}{\log \log p #})

由這個結論得知， $ω (n)$ 會是 $O (\frac{\log n}{\log \log n})$ 的。

Reference

The Divisor Bound
Primorial
Prime number theorem
Upper bound number of distinct prime factors
Chebyshev function
Inequalities On The Lambert W Function And Hyperpower Function