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

原文链接：

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

例题1

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

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

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

费马最后定理

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

费马小定理

如果 $n ot p$ ，那么有
${n^{p - 1}} equiv 1(mod p)$

证明也很好证。

之前证过了，序列
$nmod p,2nmod p, ldots ,(p - 1)nmod 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)!(mod p)$
所以
${n^{p - 1}} equiv 1(mod p)$

欧拉函数

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

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

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

莫比乌斯函数

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

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

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

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

组合数入门

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

推广到实数领域，定义
$left( {egin{array}{c}r\kend{array}} ight) = left{ {egin{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}} ight.$

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

性质1

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

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

$left( {egin{array}{c}{ - 1}\kend{array}} ight) e left( {egin{array}{c}{ - 1}\{ - 1 - k}end{array}} ight)$

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

性质2

$left( {egin{array}{c}r\kend{array}} ight) = frac{r}{k}left( {egin{array}{c}{r - 1}\{k - 1}end{array}} ight)$

性质3

$(r - k)left( {egin{array}{c}r\kend{array}} ight) = rleft( {egin{array}{c}{r - 1}\kend{array}} ight)$

性质4

$left( {egin{array}{c}r\kend{array}} ight) = left( {egin{array}{c}{r - 1}\kend{array}} ight) + left( {egin{array}{c}{r - 1}\{k - 1}end{array}} ight)$

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

性质5

$sumlimits_{k le n} {left( {egin{array}{c}{r + k}\kend{array}} ight)} = left( {egin{array}{c}{r + n + 1}\nend{array}} ight)$

性质6

$sumlimits_{0 le k le n} {left( {egin{array}{c}k\mend{array}} ight)} = left( {egin{array}{c}{n + 1}\{m + 1}end{array}} ight)$

性质7

微分形式：

$Delta left( {left( {egin{array}{c}x\mend{array}} ight)} ight) = left( {egin{array}{c}{x + 1}\mend{array}} ight) - left( {egin{array}{c}x\mend{array}} ight) = left( {egin{array}{c}x\{m - 1}end{array}} ight)$

$sum {left( {egin{array}{c}x\mend{array}} ight)delta x = } left( {egin{array}{c}x\{m + 1}end{array}} ight) + C$

二项式系数

${(x + y)^r} = sumlimits_k {left( {egin{array}{c}r\kend{array}} ight)} {x^k}{y^{r - k}},r in mathbb{Z}$

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

${2^n} = left( {egin{array}{c}n\0end{array}} ight) + left( {egin{array}{c}n\1end{array}} ight) + cdots + left( {egin{array}{c}n\nend{array}} ight)$

${0^n} = left( {egin{array}{c}n\0end{array}} ight) - left( {egin{array}{c}n\1end{array}} ight) + cdots + {( - 1)^n}left( {egin{array}{c}n\nend{array}} ight)$

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

推广到实数域：

${(1 + z)^r} = sumlimits_k {left( {egin{array}{c}r\kend{array}} ight){z^k}} ,left| z ight| < 1,r in mathbb{R}$

可以通过泰勒展开证明。