查看“︁初等数论/數論函數”︁的源代码

== 数论函数 ==
数论函数是指定义域为正整数的函数。比如阶乘<math>n!</math>，约数个数<math>d(n)</math>。

=== 约数个数函数 ===
约数个数的计算公式1：

<math>d(n)=\sum_{d|n}1</math>

这种方式是求出约数个数最朴素的方式，也是最繁琐的方式，因为这就是约数个数的定义。我们一般用下面说的公式2来计算约数个数：

若<math>n=\prod_{i=1}^kp_i^{\alpha_i}</math>，则<math>d(n)=\prod_{i=1}^k(\alpha_i+1)</math>。其中<math>p_i</math>是素数，<math>\alpha_i</math>均为正整数。

这个公式很好推导，只是运用了一些简单的乘法原理。对于任意一个<math>n</math>的素因子<math>p_i</math>，我们可以选择<math>p_i^0,p_i^1,\cdots,p_i^{\alpha_i}</math>共<math>\alpha_i+1</math>种情况种的一个来作为一个<math>n</math>一个约数的约数。由乘法原理，就可以推导出公式2。这个公式在计算约数个数时应该是最常用、最方便、最快速的。尽管它仍然很繁琐。

=== 约数和函数 ===
约数和的计算公式1：

<math>\sigma(n)=\sum_{d|n}d</math>

没错，这就是约数和的定义。计算约数个数一般也用下面的公式2：

若<math>n=\prod_{i=1}^kp_i^{\alpha_i}</math>，则<math>\sigma(n)=\prod_{i=1}^k\left(\sum_{j=0}^{\alpha_i}p_i^j\right)</math>

这里我们给出详细的推导过程。

首先我们考虑当<math>n</math>只有两个素因子时的情况。设这两个素因子为<math>p_1,p_2</math>，且次数分别为<math>\alpha_1,\alpha_2</math>。如果我们选择<math>p_1^ap_2^b</math>作为<math>n</math>的标准分解形式，那我们先定死<math>p_2^b</math>不动，那么标准分解形式种含有<math>p_2^b</math>的约数的和应该为<math>\sum_{i=0}^{\alpha_1}p_1\cdot p_2^b</math>。

同样地，对其它<math>p_2^k</math>做其它相同的事，再将<math>\sum_{i=0}^{\alpha_1}p_1</math>作为公因式提取出来，就可以得到：

<math>\sigma(n)=\sum_{i=0}^{\alpha_1}p_1\sum_{i=0}^{\alpha_2}p_2</math>

现在，我们使用上面这种简化版的问题的结论，将其推广，就可以得到公式2。

=== 欧拉函数 ===
欧拉函数定义（公式1）：
<math>\varphi(n)=\sum_{\gcd(d,n)=1}1</math>

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

若<math>n</math>的标准分解形式是<math>n=\prod_{i=1}^kp_i^{\alpha_i}</math>，则<math>\varphi(n)=n\cdot\prod_{i=1}^k\frac{p_i-1}{p_i}</math>

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

假设有一个模<math>n</math>的缩系<math>A=\{a_1,a_2,\cdots,a_{\varphi(n)}\}</math>，则对于一个正整数<math>a</math>满足<math>\gcd(a,n)=1</math>，<math>\gcd(aa_i,n)=1,i\in\{1,2,\cdots,\varphi(n)\}</math>。故<math>B=\{aa_1,aa_2,\cdots,aa_{\varphi(n)}\}</math>也是一个模<math>n</math>的缩系。所以<math>\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</math>。因为缩系里的每一个元素都与<math>n</math>互质，所以它们的乘积也与<math>n</math>互质。所以我们可以得到<math>a^{\varphi(n)}\equiv1\pmod n</math>

这就是费马-欧拉定理。不难发现<math>n=p</math>时，<math>\varphi(p)=p-1</math>，即费马小定理。