初等数论/数论函数

数论函数 编辑

数论函数是指定义域为正整数的函数。比如阶乘 ,约数个数 

约数个数函数 编辑

约数个数的计算公式1:

 

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

 ,则 。其中 是素数, 均为正整数。

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

约数和函数 编辑

约数和的计算公式1:

 

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

 ,则 

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

首先我们考虑当 只有两个素因子时的情况。设这两个素因子为 ,且次数分别为 。如果我们选择 作为 的标准分解形式,那我们先定死 不动,那么标准分解形式种含有 的约数的和应该为 

同样地,对其它 做其它相同的事,再将 作为公因式提取出来,就可以得到:

 

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

欧拉函数 编辑

欧拉函数定义(公式1):  

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

 的标准分解形式是 ,则 

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

假设有一个模 的缩系 ,则对于一个正整数 满足  。故 也是一个模 的缩系。所以 。因为缩系里的每一个元素都与 互质,所以它们的乘积也与 互质。所以我们可以得到 

这就是费马-欧拉定理。不难发现 时, ,即费马小定理。