數學-初級數論

$n, m$ 代表正整數，而 $p, q$ 代表質數。我假設你已經學會除法原理、最小公因數、最大公倍數、輾轉相除法等基本概念。

除法原理：$a=bq+r, 0\leq r < |b|$

同餘

定義 1. 對於整數 $a, b$ 和正整數 $m$，我們説 $a\equiv b \pmod m$ 若且唯若 $m | a - b$。

性質 2. 同餘的基本運算規則：

若 $a \equiv b \pmod{m}$, $c \equiv d \pmod{n}$，則 $a \pm c \equiv b \pm d \pmod{m}$。
若 $a \equiv b \pmod{m}$, $c \equiv d \pmod{n}$，則 $ac \equiv bd \pmod{m}$。
若 $ca \equiv cb \pmod{m}$，則 $a \equiv b \pmod{\frac{m}{\gcd(c, m)}}$。
若 $ab \equiv 0 \pmod{p}$，則 $a \equiv 0$ 或 $b \equiv 0 \pmod{p}$。

定理 3. (Bézout Lemma) 不定方程 $ax - by = c$ 有整數解若且唯若 $\gcd(a, b) \mid c$。

證：貝祖定理是非常常用的數論定理，時常搭配擴展歐幾里得演算法求解。若 $ab = 0$，則有 $a|c$ 或 $b|c$，暫且不論；接下來假設 $ab\ne0$：

設 $d = \gcd(a, b)$，即 $a=da_1, b=db_1$，且 $\gcd(a_1,b_1) = 1$，代入方程式：

$$da_1x-db_1y=c$$ 將 d 提取出來，則有： $$a_1x-b_1y=\frac{c}d$$由於 $a_1, b_1, x, y$ 都是整數（題目預期整數解），代表題目存在整數解只有當 $d|c$ 成立的時候，即 $\gcd(a, b) | c$。

補充（擴展歐幾里得算法計算貝祖等式）： $$ax + by = \gcd(a, b)$$ 給定 $a, b$，擴展歐幾里得算法會去計算當中的 $x, y$。

typedef pair<ll, ll> pii;
pii extgcd(ll a, ll b) {
    if (b == 0) return {1, 0};
    ll k = a / b;
    pii p = extgcd(b, a - k * b);
    return {p.second, p.first - k * p.second};
}

注意到關鍵的迭代：

return {p.second, p.first - k * p.second};

我們知道輾轉相除法的核心是基於在 $a = bq + r$ 下可以得到 $\gcd(a, b) = \gcd(b, r)$。所以我們可以找到 $bx_1+ry_1=gcd(b,r)$，因爲 $r = a-bq$，所以有著： $$bx_1+(a-bq)y_1=\gcd(a,b)$$ 整理并且比較原式： $$ay_1+b(x_1-qy_1)=\gcd(a,b)$$ $$ax+by=\gcd(a,b)$$ 就知道每次迭代的時候，$x=y_1, y=x_1 - qy_1$，每次迭代的答案會變化，沒錯，但我們把他反向轉換回來，這樣就可以得到最終的正確答案了。

定義 4. 對 $a \in \mathbb{Z}$，存在 $b$ 使得 $ab \equiv 1 \pmod{m}$ 若且唯若 $\gcd(a, m) = 1$。此時 $b$ 被稱為 $a$ 的模反元素（模逆元），記為 $a^{-1}$。

定理 5. 若 $p$ 是質數，且 $\gcd(a, p) = 1$，則 $a^{p-1} \equiv 1 \pmod{p}$，此時 $a^{p-2}$ 是 $p$ 的模逆元。（費馬小定理）

證：

我們考慮模 $p$ 的乘法群整數集 $A = {1, 2, 3, ..., p - 1}$，這些整數顯然都和 $p$ 互質。我們現在來考慮數列：

$$a\cdot1,a\cdot2,a\cdot3,...,a\cdot(p-1)$$ 這些數字模 $p$ 後會變成 $A$ 的某種排列，將這些數字相乘，我們會獲得： $$a\cdot1\times a\cdot2 \times a\cdot3\times ... \times a\cdot(p-1) \equiv1\times2\times3\times...\times(p-1)\pmod p$$ 因爲他們在同一個乘法群，所以具備這個結論，我們可以將左右兩側相同元素消除，即可得到結論。

定義 6. 在數論中，對正整數 $n$，歐拉函數 $\varphi(n)$ 是小於等於 $n$ 的正整數中與 $n$ 互質的數的數目。

求值：

歐拉函數的性質：

歐拉函數是積性函數，如果 $\gcd(m,n) = 1$，則 $\varphi(mn)=\varphi(m)\varphi(n)$。因爲很顯然的，如果一個數字 $x$ 不是 $m$ 和 $n$ 的因數，那他也一定不是 $mn$ 的因數。
$\varphi(p^k)=p^k-p^{k-1}$，很顯然的，除了 $p$ 的倍數外，$p^k$ 與其它所有數字互質。
因此如果 $n=p_{1}^{k_1}p_2^{k_2}...$，則$\varphi{n}=\prod{(p_i^{k}-p_i^{k-1})}$

因此，在這種方式下，我們可以在因數分解的複雜度下求出歐拉函數值。

int phi(int x) {
    int r = x;
    for (int p = 2; p * p <= x; p++) {
        if (x % p == 0) {
            while (x % p == 0) x /= p;
            r -= r / p;
        }
    }
    if (x > 1) r -= r / x;
    return r;
}

但我們也可利用埃氏篩法的方式來 $O(nloglogn)$ 求出 $[0, n)$ 的歐拉函數值表。

vector<int> phi_in(int n) {
    vector<bool> p(n, 1); vector<int> r(n);
    for (int i = 0; i < n; i++) r[i] = i;
    r[1] = p[0] = p[1] = 0;
    for (int i = 2; i < n; i++) {
        if (!p[i]) continue;
        r[i]--;
        for (int j = i * 2; j < n; j += i)
            p[j] = 0, r[j] = r[j] / i * (i - 1);
    } return r;
}

定理 7. 若 $\gcd(a, n) = 1$，則 $a^{\varphi(n)} \equiv 1 \pmod{n}$，此時 $a^{\varphi(n)-1}$ 是 $a$ 的模逆元。（歐拉定理）

證明方式與費馬小定理類似，此處不贅述。

定理 8. 若 $p$ 是質數，則 $(p-1)! \equiv -1 \pmod{p}$ （威爾森定理）

證：在模質數的情況下，每個數字都有唯一一個配對的模逆元，而當中有 2 個最爲特別： $$1\times1\equiv1\pmod1,(p-1)\times(p-1)\equiv1\pmod1$$ 而其它 ${2,3,...,p-2}$ 的模逆元都是集合中的另一元素，因此在模 $p$ 的情況下都會消去，只留下 1。

定理 9. 若 $p$ 是質數，則 $\binom{n}{m} \mod p = \binom{\lfloor n/p \rfloor}{\lfloor m/p \rfloor} \cdot \binom{n \mod p}{m \mod p} \mod p$ （盧卡斯定理）

證：$\binom{p}{n}$ 在 $1 \le n \le p-1$ 的情況皆可被 $p$ 整除，因此，$(a+b)^p\equiv a^p + b^p \pmod p$ 。

而考慮 $(1+x)^n \equiv (1+x)^{p\lfloor{n/p\rfloor}}(1+x)^{{n\mod p}} \pmod p$，我們就是要求 $x^m$ 項的係數。而前者（即 $(1+x)^{p\lfloor n/p \rfloor}$）僅有冪次爲 $p$ 的倍數時才需要考慮（否則根據上面的結論會模 $p$ 爲 $0$）；至於後者，最高項已經小於 $p$ 了。

因此我們得到：$$\binom{n}{m} \mod p = \binom{\lfloor n/p \rfloor}{\lfloor m/p \rfloor} \cdot \binom{n \mod p}{m \mod p} \mod p$$

定理 10. 在給定如下形式的一元線性同餘方程組，當 $m_1,m_2,...,m_n$ 兩兩互質時，可求解。（中國剩餘定理，Chinese Remainder Theorem）

過程：

設 $M = \Pi^n_{i=1}{m_i}$
對於第 $i$ 個方程式，計算 $n_i = \frac{M}{m_i}$ 和 $n_i$ 在模 $m_i$ 下的模逆元 $n_i^{-1}$；
$x = \Sigma_{i=1}^k{a_in_in_i^{-1}} \pmod M$

證明： $\forall i \ne j$，我們有 $a_in_in_i^{-1} \equiv 0\pmod {m_j}$，因爲 $n_i=\frac{M}{m_i}\equiv 0 \pmod {m_j}$，明顯 $m_j$ 是 $n_i$ 的因數。因此對任何 $j$： $$\Sigma_{i=1}^k{a_in_in_i^{-1}} \pmod {m_j}$$ $$\equiv a_jn_jn_j^{-1} \pmod {m_j}$$ 注意到 $n_in_i^{-1} \equiv 1 \pmod {m_i}$，因此成功構造出 $x = \Sigma_{i=1}^k{a_in_in_i^{-1}} \equiv a_j \pmod {m_j}$。

原根（primitive root ）及其運用

定義 11. 滿足 $a^n\equiv 1 \pmod m$ 的最小正整數 $n$ 稱之爲 $a$ 模 $m$ 的階或是序，記作 $\delta_{m}(a)$ 或是 $\text{Ord}_m(a)$。

定義 12. 若 $\gcd(g, m) = 1$ 且 $\delta_m(g)=\varphi(m)$，則稱 $g$ 爲模 $m$ 的原根。

定理 13. 若 $m \ge 3, \gcd(g, m) = 1$，則 $g$ 是 $m$ 的原根的充要條件是對於 $\varphi(m)$ 的每一個質因數 $p$，都有 $g^{\varphi(m)/p} \not\equiv 1 \pmod m$。（原根判定原理）

應用：若要尋找質數 $p$ 的原根，可以採用下面演算法。

將 $p - 1$ 作質因數分解，$p - 1 = \Pi_{i=1}^kq_i^{e_i}$。
對於每一個 $i$，挑選一個 $a_i$ 使 $a_i^{(p-1)/q_i}\not\equiv1$，令 $\gamma_i = a_i^{(p-1)/(q_i^{e_i})}$，基本上這步隨機挑選 $a_i$。
$p$ 的其中一原根爲 $\gamma = \Pi_{i=1}^k{\gamma_i}$。

在第二步中，明顯 $\delta_p(\gamma_i)=q^{e^i}$ 。在第三步中，我們要運用一個性質，倘若 $\gcd(\delta_m(a), \delta_m(b)) = 1$，則 $\delta_m(ab) = \delta_m(a)\delta_m(b)$，因此 $\delta_p(\gamma) = p-1$，顯然，$\gamma$ 是原根。

定義 14. 倘若 $g$ 是 $m$ 的其中一個原根，且有滿足 $\gcd(a, m) = 1$ 的整數 $a$，我們知道必然存在唯一整數 $0 \le k < \varphi(m)$ 滿足：$g^k\equiv a \pmod m$，我們記作 $k = \text{ind}_g{a}$，這便是離散對數，擁有和對數相當相似的性質。

網路概論（二）