关注公众号【算法码上来】，每日算法干货马上就来！
这节课内容太多了，再加上感冒身体不舒服，下面的定理就不一一证明了，大家可以自行练习。以后有空我会补上的！
例题1
首先接着上节课同余继续讲，在第三章例题2中，我们遗留了一个问题：对于如下序列
<!–swig0–>
它的值就是
<!–swig1–>
的某个排列，并且重复了$d$次。其中$d = gcd(m, n)$
首先我们有如下同余式：
<!–swig4–>
这就可以看出该序列的确是重复出现了$d$次，那么剩下的问题就是证明这$m/d$个数恰好就是
<!–swig7–>
的某个排列。
令$m = m'd,n = n'd$，所以有
<!–swig9–>
所以我们只考虑$m \bot n$的情形，在此情形下，我们可以得到
<!–swig11–>
由此可以看出，这$m-1$个数一定就是
<!–swig13–>
至此得证。
下面介绍几个著名的数论定理。
费马最后定理
对于所有的正整数$a,b,c,n>2$，有
<!–swig15–>
费马小定理
如果$n \bot p$，那么有
<!–swig17–>
证明也很好证。
之前证过了，序列
<!–swig18–>
结果就是
<!–swig19–>
的某个排列，所以有
<!–swig20–>
所以
<!–swig21–>
所以
<!–swig22–>
欧拉函数
定义$\varphi (m)$为小于$m$且与其互素的正整数个数。
所以我们有欧拉定理
<!–swig25–>
其中$n \bot m$，可以发现，当$m$是素数时，欧拉定理就是费马小定理，所以欧拉定理是费马小定理的推广形式。
欧拉定理有很多有趣的性质，这里就不一一介绍了，详情见博客地址。
莫比乌斯函数
定义莫比乌斯函数$\mu (m)$为
<!–swig29–>
这个定义看起来很奇怪是不是？其实这是一个递归定义，可以递归地计算得到所有的值。
这个函数有什么用呢？主要用来进行莫比乌斯反演：
<!–swig30–>
详细的性质及应用也不介绍了，给大家推荐一个牛逼的博客博客地址，我当时学ACM的时候这部分都是看着他的学的。
组合数入门
定义组合数$\left( {\begin{array}{c}n\\k\end{array}} \right)$为从$n$个物品中取出$k$个物品的方法数，具体计算为
<!–swig34–>
推广到实数领域，定义
<!–swig35–>
下面介绍一些组合数性质。
性质1
<!–swig36–>
这里为什么要限定$n \ge 0$呢？举个例子，如果$n = -1$，那么有
<!–swig39–>
因为左边等于${( - 1)^k}$，而右边等于${( - 1)^{-1-k}}$。
性质2
<!–swig42–>
性质3
<!–swig43–>
性质4
<!–swig44–>
这条性质可以通过性质3和性质4两边分别相加得到。
性质5
<!–swig45–>
性质6
<!–swig46–>
性质7
微分形式：
<!–swig47–>
<!–swig48–>
二项式系数
<!–swig49–>
二项式系数也有很多有趣的性质。
<!–swig50–>
<!–swig51–>
即奇数项系数和等于偶数项系数和。
推广到实数域：
<!–swig52–>
可以通过泰勒展开证明。
