初等数论/数论函数

维基教科书,自由的教学读本

数论函数[编辑]

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

约数个数函数[编辑]

约数个数的计算公式1:

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

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

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

约数和函数[编辑]

约数和的计算公式1:

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

,则

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

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

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

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

欧拉函数[编辑]

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

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

的标准分解形式是,则

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

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

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