2020-04-02 18:21 已编辑华东师范大学算法工程师

关注

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

原文链接：

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

例题1

首先接着上节课同余继续讲，在第三章例题2中，我们遗留了一个问题：对于如下序列
$0\bmod m,n\bmod m,2n\bmod m, \ldots ,(m - 1)n\bmod m$
它的值就是
$0,d,2d, \ldots ,(m/d - 1)d$
的某个排列，并且重复了 $d$ 次。其中 $d = gcd(m, n)$

首先我们有如下同余式：
$jn \equiv kn(\bmod m) \Leftrightarrow j(n/d) \equiv k(n/d)(\bmod m/d)$
这就可以看出该序列的确是重复出现了 $d$ 次，那么剩下的问题就是证明这 $m/d$ 个数恰好就是
$\{ 0,d,2d, \ldots ,m - d\}$
的某个排列。
令 $m = m'd,n = n'd$ ，所以有
$kn\bmod m = d(kn'\bmod m')$
所以我们只考虑 $m \bot n$ 的情形，在此情形下，我们可以得到
$jn \equiv kn(\bmod m) \Leftrightarrow j \equiv k(\bmod m)$
由此可以看出，这 $m-1$ 个数一定就是
$\{ 0,1,2, \ldots ,m - 1\}$
至此得证。

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

费马最后定理

对于所有的正整数 $a,b,c,n>2$ ，有
${a^n} + {b^n} \ne {c^n}$

费马小定理

如果 $n \bot p$ ，那么有
${n^{p - 1}} \equiv 1(\bmod p)$

证明也很好证。

之前证过了，序列
$n\bmod p,2n\bmod p, \ldots ,(p - 1)n\bmod p$
结果就是
$1,2, \ldots ,p-1$
的某个排列，所以有
$n \cdot (2n) \cdot \ldots \cdot ((p - 1)n) \equiv (p - 1)!$
所以
$(p - 1)!{n^{p - 1}} \equiv (p - 1)!(\bmod p)$
所以
${n^{p - 1}} \equiv 1(\bmod p)$

欧拉函数

定义 $\varphi (m)$ 为小于 $m$ 且与其互素的正整数个数。

所以我们有欧拉定理
${n^{\varphi (m)}} \equiv 1(\bmod m)$
其中 $n \bot m$ ，可以发现，当 $m$ 是素数时，欧拉定理就是费马小定理，所以欧拉定理是费马小定理的推广形式。

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

莫比乌斯函数

定义莫比乌斯函数 $\mu (m)$ 为
$\sum\limits_{d|m} {\mu (d)} = [m = 1]$

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

这个函数有什么用呢？主要用来进行莫比乌斯反演：
$g(m) = \sum\limits_{d|m} {f(d)} \Leftrightarrow f(m) = \sum\limits_{d|m} {\mu (d)g(\frac{m}{d})}$

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

组合数入门

定义组合数 $\left( {\begin{array}{c}n\\k\end{array}} \right)$ 为从 $n$ 个物品中取出 $k$ 个物品的方法数，具体计算为
$\left( {\begin{array}{c}n\\k\end{array}} \right) = \frac{ {n(n - 1) \ldots (n - k + 1)}}{ {k(k - 1) \ldots 1}}$

推广到实数领域，定义
$\left( {\begin{array}{c}r\\k\end{array}} \right) = \left\{ {\begin{array}{c}{\frac{ {r(r - 1) \ldots (r - k + 1)}}{ {k(k - 1) \ldots 1}} = \frac{ { {r^{\underline{k}}}}}{ {k!}},k \ge 0}\\{0,k < 0}\end{array}} \right.$

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

性质1

$\left( {\begin{array}{c}n\\k\end{array}} \right) = \left( {\begin{array}{c}n\\{n - k}\end{array}} \right),n,k \in \mathbb{Z},n \ge 0$

这里为什么要限定 $n \ge 0$ 呢？举个例子，如果 $n = -1$ ，那么有

$\left( {\begin{array}{c}{ - 1}\\k\end{array}} \right) \ne \left( {\begin{array}{c}{ - 1}\\{ - 1 - k}\end{array}} \right)$

因为左边等于 ${( - 1)^k}$ ，而右边等于 ${( - 1)^{-1-k}}$ 。

性质2

$\left( {\begin{array}{c}r\\k\end{array}} \right) = \frac{r}{k}\left( {\begin{array}{c}{r - 1}\\{k - 1}\end{array}} \right)$

性质3

$(r - k)\left( {\begin{array}{c}r\\k\end{array}} \right) = r\left( {\begin{array}{c}{r - 1}\\k\end{array}} \right)$

性质4

$\left( {\begin{array}{c}r\\k\end{array}} \right) = \left( {\begin{array}{c}{r - 1}\\k\end{array}} \right) + \left( {\begin{array}{c}{r - 1}\\{k - 1}\end{array}} \right)$

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

性质5

$\sum\limits_{k \le n} {\left( {\begin{array}{c}{r + k}\\k\end{array}} \right)} = \left( {\begin{array}{c}{r + n + 1}\\n\end{array}} \right)$

性质6

$\sum\limits_{0 \le k \le n} {\left( {\begin{array}{c}k\\m\end{array}} \right)} = \left( {\begin{array}{c}{n + 1}\\{m + 1}\end{array}} \right)$

性质7

微分形式：

$\Delta \left( {\left( {\begin{array}{c}x\\m\end{array}} \right)} \right) = \left( {\begin{array}{c}{x + 1}\\m\end{array}} \right) - \left( {\begin{array}{c}x\\m\end{array}} \right) = \left( {\begin{array}{c}x\\{m - 1}\end{array}} \right)$

$\sum {\left( {\begin{array}{c}x\\m\end{array}} \right)\delta x = } \left( {\begin{array}{c}x\\{m + 1}\end{array}} \right) + C$

二项式系数

${(x + y)^r} = \sum\limits_k {\left( {\begin{array}{c}r\\k\end{array}} \right)} {x^k}{y^{r - k}},r \in \mathbb{Z}$

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

${2^n} = \left( {\begin{array}{c}n\\0\end{array}} \right) + \left( {\begin{array}{c}n\\1\end{array}} \right) + \cdots + \left( {\begin{array}{c}n\\n\end{array}} \right)$

${0^n} = \left( {\begin{array}{c}n\\0\end{array}} \right) - \left( {\begin{array}{c}n\\1\end{array}} \right) + \cdots + {( - 1)^n}\left( {\begin{array}{c}n\\n\end{array}} \right)$