初等数论/數論函數

数论函数

数论函数是指定义域为正整数的函数。比如阶乘$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）： $\phi (n)=\sum _{\gcd (d,n)=1}1$

从上面的式子可以看出，欧拉函数计算的是在小于$n$的正整数中与$n$互质的数的个数。公式2如下：

若$n$的标准分解形式是$n=\prod _{i=1}^k{p}_i^{{\alpha }_i}$，则$\phi (n)=n\cdot \prod _{i=1}^k\frac{p_i-1}{p_i}$

由这个数论函数可以推导出费马-欧拉定理，再推出著名的费马小定理。先看欧拉定理。我们定义一种数组叫做模$n$的简化剩余系（以下简称缩系），其中含有$\phi (n)$个元素。在这些元素中任意取两个数都不模$n$同余，且每个数都与$n$互质。

假设有一个模$n$的缩系$A=\{a_1,a_2,\cdots ,a_{\phi (n)}\}$，则对于一个正整数$a$满足$\gcd (a,n)=1$，$\gcd (a{a}_i,n)=1,i\in \{1,2,\cdots ,\phi (n)\}$。故$B=\{a{a}_1,a{a}_2,\cdots ,a{a}_{\phi (n)}\}$也是一个模$n$的缩系。所以$\prod _{i=1}^{\phi (n)}a{a}_i\equiv a^{\phi (n)}\prod _{i=1}^{\phi (n)}{a}_i\equiv \prod _{i=1}^{\phi (n)}{a}_i(\mathrm{mod}n)$。因为缩系里的每一个元素都与$n$互质，所以它们的乘积也与$n$互质。所以我们可以得到$a^{\phi (n)}\equiv 1(\mathrm{mod}n)$

这就是费马-欧拉定理。不难发现$n=p$时，$\phi (p)=p-1$，即费马小定理。