跳转至

數論基礎

本文對於數論的開頭部分做一個簡介。

整除

整除的定義：設 \(a,b\in\mathbf{Z}\)，\(a\ne 0\)。如果 \(\exists q\in\mathbf{Z}\)，使得 \(b=aq\)，那麼就説 \(b\) 可被 \(a\) 整除，記作 \(a\mid b\)；\(b\) 不被 \(a\) 整除記作 \(a\nmid b\)。

整除的性質：

  • \(a\mid b\iff-a\mid b\iff a\mid-b\iff|a|\mid|b|\)
  • \(a\mid b\land b\mid c\implies a\mid c\)
  • \(a\mid b\land a\mid c\iff\forall x,y\in\mathbf{Z}, a\mid(xb+yc)\)
  • \(a\mid b\land b\mid a\implies b=\pm a\)
  • 設 \(m\ne0\)，那麼 \(a\mid b\iff ma\mid mb\)。
  • 設 \(b\ne0\)，那麼 \(a\mid b\implies|a|\le|b|\)。
  • 設 \(a\ne0,b=qa+c\)，那麼 \(a\mid b\iff a\mid c\)。

約數（因數）：若 \(a\mid b\)，則稱 \(b\) 是 \(a\) 的倍數，\(a\) 是 \(b\) 的約數。

\(0\) 是所有非 \(0\) 整數的倍數。對於整數 \(b\ne0\)，\(b\) 的約數只有有限個。

平凡約數（平凡因數）：對於整數 \(b\ne0\)，\(\pm1\)、\(\pm b\) 是 \(b\) 的平凡約數。當 \(b=\pm1\) 時，\(b\) 只有兩個平凡約數。

對於整數 \(b\ne 0\)，\(b\) 的其他約數稱為真約數（真因數、非平凡約數、非平凡因數）。

約數的性質：

  • 設整數 \(b\ne0\)。當 \(d\) 遍歷 \(b\) 的全體約數的時候，\(\dfrac{b}{d}\) 也遍歷 \(b\) 的全體約數。
  • 設整數 \(b\gt 0\)，則當 \(d\) 遍歷 \(b\) 的全體正約數的時候，\(\dfrac{b}{d}\) 也遍歷 \(b\) 的全體正約數。

在具體問題中，如果沒有特別説明，約數總是指正約數。

帶餘數除法

餘數的定義：設 \(a,b\) 為兩個給定的整數，\(a\ne0\)。設 \(d\) 是一個給定的整數。那麼，一定存在唯一的一對整數 \(q\) 和 \(r\)，滿足 \(b=qa+r,d\le r<|a|+d\)。

無論整數 \(d\) 取何值，\(r\) 統稱為餘數。\(a\mid b\) 等價於 \(a\mid r\)。

一般情況下，\(d\) 取 \(0\)，此時等式 \(b=qa+r,0\le r<|a|\) 稱為帶餘數除法（帶餘除法）。這裏的餘數 \(r\) 稱為最小非負餘數。

餘數往往還有兩種常見取法：

絕對最小余數：\(d\) 取 \(a\) 的絕對值的一半的相反數。即 \(b=qa+r,-\dfrac{|a|}{2}\le r<|a|-\dfrac{|a|}{2}\)。

最小正餘數：\(d\) 取 \(1\)。即 \(b=qa+r,1\le r<|a|+1\)。

帶餘數除法的餘數只有最小非負餘數。如果沒有特別説明，餘數總是指最小非負餘數。

餘數的性質：

  • 任一整數被正整數 \(a\) 除後，餘數一定是且僅是 \(0\) 到 \((a-1)\) 這 \(a\) 個數中的一個。
  • 相鄰的 \(a\) 個整數被正整數 \(a\) 除後，恰好取到上述 \(a\) 個餘數。特別地，一定有且僅有一個數被 \(a\) 整除。

最大公約數與最小公倍數

關於公約數、公倍數、最大公約數與最小公倍數，四個名詞的定義，見 最大公約數。

互素

兩個整數互素（既約）的定義：若 \(\gcd(a_1,a_2)=1\)，則稱 \(a_1\) 和 \(a_2\) 互素（既約）。

多個整數互素（既約）的定義：若 \(\gcd(a_1,\ldots,a_k)=1\)，則稱 \(a_1,\ldots,a_k\) 互素（既約）。

多個整數互素，不一定兩兩互素。例如 \(6\)、\(10\) 和 \(15\) 互素，但是任意兩個都不互素。

互素的性質與最大公約數理論：裴蜀定理（Bézout's identity）。見 裴蜀定理。

輾轉相除法

輾轉相除法是一種算法，也稱 Euclid 算法。見 最大公約數。

素數與合數

關於素數的算法見 素數。

設整數 \(p\ne0,\pm1\)。如果 \(p\) 除了平凡約數外沒有其他約數，那麼稱 \(p\) 為素數（不可約數）。

若整數 \(a\ne0,\pm 1\) 且 \(a\) 不是素數，則稱 \(a\) 為合數。

\(p\) 和 \(-p\) 總是同為素數或者同為合數。如果沒有特別説明，素數總是指正的素數。

整數的因數是素數，則該素數稱為該整數的素因數（素約數）。

素數與合數的簡單性質：

  • 大於 \(1\) 的整數 \(a\) 是合數，等價於 \(a\) 可以表示為整數 \(d\) 和 \(e\)（\(1<d,e<a\)）的乘積。
  • 如果素數 \(p\) 有大於 \(1\) 的約數 \(d\)，那麼 \(d=p\)。
  • 大於 \(1\) 的整數 \(a\) 一定可以表示為素數的乘積。
  • 對於合數 \(a\)，一定存在素數 \(p\le\sqrt{a}\) 使得 \(p\mid a\)。
  • 素數有無窮多個。
  • 所有大於 \(3\) 的素數都可以表示為 \(6n\pm 1\) 的形式1。

算術基本定理

算術基本引理：

設 \(p\) 是素數，\(p\mid a_1a_2\)，那麼 \(p\mid a_1\) 和 \(p\mid a_2\) 至少有一個成立。

算術基本引理是素數的本質屬性，也是素數的真正定義。

算術基本定理（唯一分解定理）：

設正整數 \(a\)，那麼必有表示：

\[ a=p_1p_2\cdots p_s \]

其中 \(p_j(1\le j\le s)\) 是素數。並且在不計次序的意義下，該表示唯一。

標準素因數分解式：

將上述表示中，相同的素數合併，可得：

\[ a={p_1}^{\alpha_1}{p_2}^{\alpha_2}\cdots{p_s}^{\alpha_s},p_1<p_2<\cdots<p_s \]

稱為正整數 \(a\) 的標準素因數分解式。

算術基本定理和算術基本引理，兩個定理是等價的。

同餘

同餘的定義：設整數 \(m\ne0\)。若 \(m\mid(a-b)\)，稱 \(m\) 為模數（模），\(a\) 同餘於 \(b\) 模 \(m\)，\(b\) 是 \(a\) 對模 \(m\) 的剩餘。記作 \(a\equiv b\pmod m\)。

否則，\(a\) 不同餘於 \(b\) 模 \(m\)，\(b\) 不是 \(a\) 對模 \(m\) 的剩餘。記作 \(a\not\equiv b\pmod m\)。

這樣的等式，稱為模 \(m\) 的同餘式，簡稱同餘式。

根據整除的性質，上述同餘式也等價於 \(a\equiv b\pmod{(-m)}\)。

如果沒有特別説明，模數總是正整數。

式中的 \(b\) 是 \(a\) 對模 \(m\) 的剩餘，這個概念與餘數完全一致。通過限定 \(b\) 的範圍，相應的有 \(a\) 對模 \(m\) 的最小非負剩餘、絕對最小剩餘、最小正剩餘。

同餘的性質：

  • 自反性：\(a\equiv a\pmod m\)。
  • 對稱性：若 \(a\equiv b\pmod m\)，則 \(b\equiv a\pmod m\)。
  • 傳遞性：若 \(a\equiv b\pmod m,b\equiv c\pmod m\)，則 \(a\equiv c\pmod m\)。
  • 線性運算：若 \(a,b,c,d\in\mathbf{Z},m\in\mathbf{N}^*,a\equiv b\pmod m,c\equiv d\pmod m\) 則有：
    • \(a\pm c\equiv b\pm d\pmod m\)。
    • \(a\times c\equiv b\times d\pmod m\)。
  • 若 \(a,b\in\mathbf{Z},k,m\in\mathbf{N}^*,a\equiv b\pmod m\), 則 \(ak\equiv bk\pmod{mk}\)。
  • 若 \(a,b\in\mathbf{Z},d,m\in\mathbf{N}^*,d\mid a,d\mid b,d\mid m\)，則當 \(a\equiv b\pmod m\) 成立時，有 \(\dfrac{a}{d}\equiv\dfrac{b}{d}\left(\bmod\;{\dfrac{m}{d}}\right)\)。
  • 若 \(a,b\in\mathbf{Z},d,m\in\mathbf{N}^*,d\mid m\)，則當 \(a\equiv b\pmod m\) 成立時，有 \(a\equiv b\pmod d\)。
  • 若 \(a,b\in\mathbf{Z},d,m\in\mathbf{N}^*\)，則當 \(a\equiv b\pmod m\) 成立時，有 \(\gcd(a,m)=\gcd(b,m)\)。若 \(d\) 能整除 \(m\) 及 \(a,b\) 中的一個，則 \(d\) 必定能整除 \(a,b\) 中的另一個。

還有性質是乘法逆元。見 乘法逆元。

C/C++ 的整數除法和取模運算

在 C/C++ 中，整數除法和取模運算，與數學上習慣的取模和除法不一致。

對於所有標準版本的 C/C++，規定在整數除法中：

  1. 當除數為 0 時，行為未定義；
  2. 否則 (a / b) * b + a % b 的運算結果與 a 相等。

也就是説，取模運算的符號取決於除法如何取整；而除法如何取整，這是實現定義的（由編譯器決定）。

從 C992和 C++113標準版本起，規定 商向零取整（捨棄小數部分）；取模的符號即與被除數相同。從此以下運算結果保證為真：

1
2
3
4
5 % 3 == 2;
5 % -3 == 2;
-5 % 3 == -2;
-5 % -3 == -2;

數論函數

數論函數指定義域為正整數的函數。數論函數也可以視作一個數列。

積性函數

定義

若函數 \(f(n)\) 滿足 \(f(1)=1\) 且 \(\forall x,y\in\mathbf{N}^*,\gcd(x,y)=1\) 都有 \(f(xy)=f(x)f(y)\)，則 \(f(n)\) 為積性函數。

若函數 \(f(n)\) 滿足 \(f(1)=1\) 且 \(\forall x,y\in\mathbf{N}^*\) 都有 \(f(xy)=f(x)f(y)\)，則 \(f(n)\) 為完全積性函數。

性質

若 \(f(x)\) 和 \(g(x)\) 均為積性函數，則以下函數也為積性函數：

\[ \begin{aligned} h(x)&=f(x^p)\\ h(x)&=f^p(x)\\ h(x)&=f(x)g(x)\\ h(x)&=\sum_{d\mid x}f(d)g\left(\dfrac{x}{d}\right) \end{aligned} \]

設 \(x=\prod p_i^{k_i}\)

若 \(F(x)\) 為積性函數，則有 \(F(x)=\prod F(p_i^{k_i})\)。

若 \(F(x)\) 為完全積性函數，則有 \(F(x)=\prod F(p_i)^{k_i}\)。

例子

  • 單位函數：\(\varepsilon(n)=[n=1]\)。（完全積性）
  • 恆等函數：\(\operatorname{id}_k(n)=n^k\)，\(\operatorname{id}_{1}(n)\) 通常簡記作 \(\operatorname{id}(n)\)。（完全積性）
  • 常數函數：\(1(n)=1\)。（完全積性）
  • 除數函數：\(\sigma_{k}(n)=\sum_{d\mid n}d^{k}\)。\(\sigma_{0}(n)\) 通常簡記作 \(d(n)\) 或 \(\tau(n)\)，\(\sigma_{1}(n)\) 通常簡記作 \(\sigma(n)\)。
  • 歐拉函數：\(\varphi(n)=\sum_{i=1}^n[\gcd(i,n)=1]\)
  • 莫比烏斯函數：\(\mu(n)=\begin{cases}1&n=1\\0&\exists d>1,d^{2}\mid n\\(-1)^{\omega(n)}&\text{otherwise}\end{cases}\)，其中 \(\omega(n)\) 表示 \(n\) 的本質不同質因子個數，它是一個加性函數。
加性函數

此處加性函數指數論上的加性函數 (Additive function)。對於加性函數 \(f\)，當整數 \(a,b\) 互質時，均有 \(f(ab)=f(a)+f(b)\)。 應與代數中的加性函數 (Additive map) 區分。

參考資料與註釋

  1. Are all primes (past 2 and 3) of the forms 6n+1 and 6n-1? ↩

  2. Arithmetic operators (C) - cppreference.com ↩

  3. Arithmetic operators (C++) - cppreference.com ↩

本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用