初等数论/數論函數

数论函数

数论函数是指定义域为正整数的函数。比如阶乘$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$，即费马小定理。