初等數論/數論函數

數論函數

數論函數是指定義域為正整數的函數。比如階乘$n!$，約數個數$d(n)$。

約數個數函數

約數個數的計算公式1：

$d(n)=\sum _{d|n}1$

這種方式是求出約數個數最樸素的方式，也是最繁瑣的方式，因為這就是約數個數的定義。我們一般用下面說的公式2來計算約數個數：

若$n=\prod _{i=1}^{k}p_{i}^{\alpha _{i}}$，則$d(n)=\prod _{i=1}^{k}(\alpha _{i}+1)$。其中$p_{i}$是質數，$\alpha _{i}$均為正整數。

這個公式很好推導，只是運用了一些簡單的乘法原理。對於任意一個$n$的素因子$p_{i}$，我們可以選擇$p_{i}^{0},p_{i}^{1},\cdots ,p_{i}^{\alpha _{i}}$共$\alpha _{i}+1$種情況種的一個來作為一個$n$一個約數的約數。由乘法原理，就可以推導出公式2。這個公式在計算約數個數時應該是最常用、最方便、最快速的。儘管它仍然很繁瑣。

約數和函數

約數和的計算公式1：

$\sigma (n)=\sum _{d|n}d$

沒錯，這就是約數和的定義。計算約數個數一般也用下面的公式2：

若$n=\prod _{i=1}^{k}p_{i}^{\alpha _{i}}$，則$\sigma (n)=\prod _{i=1}^{k}\left(\sum _{j=0}^{\alpha _{i}}p_{i}^{j}\right)$

這裏我們給出詳細的推導過程。

首先我們考慮當$n$只有兩個素因子時的情況。設這兩個素因子為$p_{1},p_{2}$，且次數分別為$\alpha _{1},\alpha _{2}$。如果我們選擇$p_{1}^{a}p_{2}^{b}$作為$n$的標準分解形式，那我們先定死$p_{2}^{b}$不動，那麼標準分解形式種含有$p_{2}^{b}$的約數的和應該為$\sum _{i=0}^{\alpha _{1}}p_{1}\cdot p_{2}^{b}$。

同樣地，對其它$p_{2}^{k}$做其它相同的事，再將$\sum _{i=0}^{\alpha _{1}}p_{1}$作為公因式提取出來，就可以得到：

$\sigma (n)=\sum _{i=0}^{\alpha _{1}}p_{1}\sum _{i=0}^{\alpha _{2}}p_{2}$

現在，我們使用上面這種簡化版的問題的結論，將其推廣，就可以得到公式2。

歐拉函數

歐拉函數定義（公式1）： $\varphi (n)=\sum _{\gcd(d,n)=1}1$

從上面的式子可以看出，歐拉函數計算的是在小於$n$的正整數中與$n$互質的數的個數。公式2如下：

若$n$的標準分解形式是$n=\prod _{i=1}^{k}p_{i}^{\alpha _{i}}$，則$\varphi (n)=n\cdot \prod _{i=1}^{k}{\frac {p_{i}-1}{p_{i}}}$

由這個數論函數可以推導出費馬-歐拉定理，再推出著名的費馬小定理。先看歐拉定理。我們定義一種數組叫做模$n$的簡化剩餘系（以下簡稱縮系），其中含有$\varphi (n)$個元素。在這些元素中任意取兩個數都不模$n$同餘，且每個數都與$n$互質。

假設有一個模$n$的縮系$A=\{a_{1},a_{2},\cdots ,a_{\varphi (n)}\}$，則對於一個正整數$a$滿足$\gcd(a,n)=1$，$\gcd(aa_{i},n)=1,i\in \{1,2,\cdots ,\varphi (n)\}$。故$B=\{aa_{1},aa_{2},\cdots ,aa_{\varphi (n)}\}$也是一個模$n$的縮系。所以$\prod _{i=1}^{\varphi (n)}aa_{i}\equiv a^{\varphi (n)}\prod _{i=1}^{\varphi (n)}a_{i}\equiv \prod _{i=1}^{\varphi (n)}a_{i}{\pmod {n}}$。因為縮系裏的每一個元素都與$n$互質，所以它們的乘積也與$n$互質。所以我們可以得到$a^{\varphi (n)}\equiv 1{\pmod {n}}$

這就是費馬-歐拉定理。不難發現$n=p$時，$\varphi (p)=p-1$，即費馬小定理。