具体数学-第12课（数论进阶与组合数入门）

原文链接：

具体数学-第12课 - WeiYang Bloggodweiyang.com

这节课内容太多了，再加上感冒身体不舒服，下面的定理就不一一证明了，大家可以自行练习。以后有空我会补上的！

例题1

首先接着上节课同余继续讲，在第三章例题2中，我们遗留了一个问题：对于如下序列

它的值就是

的某个排列，并且重复了

次。其中

首先我们有如下同余式：

这就可以看出该序列的确是重复出现了

次，那么剩下的问题就是证明这

个数恰好就是

的某个排列。 令

，所以有

所以我们只考虑

的情形，在此情形下，我们可以得到

由此可以看出，这

个数一定就是

至此得证。

下面介绍几个著名的数论定理。

费马最后定理

对于所有的正整数

，有

费马小定理

如果

，那么有

证明也很好证。

之前证过了，序列

结果就是

的某个排列，所以有

所以

所以

欧拉函数

定义

为小于

且与其互素的正整数个数。

所以我们有欧拉定理

其中

，可以发现，当

是素数时，欧拉定理就是费马小定理，所以欧拉定理是费马小定理的推广形式。

欧拉定理有很多有趣的性质，这里就不一一介绍了，详情见博客地址。

莫比乌斯函数

定义莫比乌斯函数

为

这个定义看起来很奇怪是不是？其实这是一个递归定义，可以递归地计算得到所有的值。

这个函数有什么用呢？主要用来进行莫比乌斯反演：

详细的性质及应用也不介绍了，给大家推荐一个牛逼的博客博客地址，我当时学ACM的时候这部分都是看着他的学的。

组合数入门

定义组合数

为从

个物品中取出

个物品的方法数，具体计算为

推广到实数领域，定义

下面介绍一些组合数性质。

性质1

这里为什么要限定

呢？举个例子，如果

，那么有

因为左边等于

，而右边等于

。

性质2

性质3

性质4

这条性质可以通过性质3和性质4两边分别相加得到。

性质5

性质6

性质7

微分形式：

二项式系数

二项式系数也有很多有趣的性质。

即奇数项系数和等于偶数项系数和。

推广到实数域：

可以通过泰勒展开证明。