初等数论笔记 · Shun Li's Notes

组合数和排列数是整数

我们熟知，从 $n$ 个元素中取出 $k$ 个元素进行无序组合（ $k \leqslant n$ ），有

Copy LaTeX

种取法，取 $n$ 个元素进行有序排列（ $k \leqslant n$ ），有

Copy LaTeX

种取法。一个自然产生的数论问题是：如何直接证明组合数和排列数都是整数？显然只需要证明组合数是整数。最简单的证明是利用帕斯卡恒等式归纳证明。

Lemma (帕斯卡恒等式、杨辉三角)

Copy LaTeX

Proof

直接验证即可

Copy LaTeX

可以从组合的观点理解：标记一个特殊元素，从 $n$ 个元素中取出 $k$ 个元素的取法可以分成两类：

第一类是包含这个特殊元素的，需要从剩下的 $n-1$ 个元素中取 $k-1$ 个元素；
第二类是不包含这个特殊元素的，需要从剩下的 $n-1$ 个元素中取 $k$ 个元素。

这个恒等式也就是著名的杨辉三角（帕斯卡三角）体现的关系。

Proposition

组合数 $C_n^k = \binom{n}{k}$ 是整数。

Proof

由帕斯卡恒等式，只需要考虑临界情况：在 $m-n$ 平面上，为第一象限中 $m=0$ 和 $m=n$ 两条线上的整格点，由于

Copy LaTeX

因此临界情况均满足，由帕斯卡恒等式可得： $m-n$ 平面的第一象限中 $m=0$ 和 $m=n$ 围成区域的所有整格点对应取值均为整数。

Remark

另一种证明思路是对素数幂次计数，证明对于任意素数 $p$ ， $n!$ 含有的素数幂次一定不小于 $k!\,(n-k)!$ 含有的素数幂次，从而保证整除关系。

与之实质相同但表述略有不同的问题是：证明连续 $m$ 个正整数的乘积必是 $m!$ 的倍数，即

Copy LaTeX

这里不能利用 “这 $n$ 个连续自然数一定有 $n$ 的倍数、 $n-1$ 的倍数 …” 进行证明，因为倍数不存在一一对应关系，无法直接消除。

勾股数

Definition

称满足勾股定理的三个正整数组成的数组 $(a,b,c)$ 为勾股数，即

Copy LaTeX

如果三者互素，称为本原勾股数。

Remark

显然定义中的的 $a$ 和 $b$ 可以交换，而且乘以任意整数倍得到的 $(na,nb,nc)$ 也是勾股数，因此我们主要讨论本原勾股数即可。

显然有 $(3,4,5)$ 和 $(5,12,13)$ 是典型的且数值最小的两组本原勾股数。事实上，我们可以给出所有勾股数的表达式

Copy LaTeX

其中 $m > n$ 为任意两个正整数。验证上述表达式是勾股数是显然的

Copy LaTeX

这里构造的勾股数是本原勾股数当且仅当 $m$ 和 $n$ 互素，而且和为奇数。下面给出这个表达式的一种推导过程。

我们可以把这个问题等价转换为在单位圆上的第一象限寻找有理点 $(x,y)$ 的问题，用高中解析几何即可完成推导。取一点 $(-1,0)$ ，作斜率为 $k$ 的直线，假设与单位圆在第一象限有交点 $(x_0,y_0)$ ，那么 $k$ 是有理数当且仅当 $(x_0,y_0)$ 是有理点，联列

Copy LaTeX

由韦达定理可得

Copy LaTeX

交点在第一象限要求 $0<k<1$ ，记有理数 $k = \frac{n}{m}$ （ $m > n$ 为两个正整数），得到

Copy LaTeX

由此自然得到了勾股数的一般表达式。

费马小定理和欧拉定理

Theorem (费马小定理)

设 $p$ 为素数， $a \in \mathbb{Z}$ ，若 $(a,p)=1$ ，则

Copy LaTeX

Proof

考虑集合 $\{1,2,\dots,p-1\}$ ，则

Copy LaTeX

是其一个排列（若 $ia \equiv ja \pmod p$ ，则 $i \equiv j$ ）。因此

Copy LaTeX

由于 $p \nmid (p-1)!$ ，两边可约去 $(p-1)!$ ，得到

Copy LaTeX

Remark

如果移除 $(a,p)=1$ 这个条件，对于任意的 $a \in \mathbb{Z}$ ，费马小定理可以写作

Copy LaTeX

因为 $(a,p) \neq 1$ 意味着 $p \mid a$ ，此时上式显然成立。

Remark

费马小定理的逆命题不成立：即使对于某个整数 $p$ ，上述命题成立，也不能推出这个整数是素数。

Definition (Euler φ 函数)

对正整数 $n$ ，定义

Copy LaTeX

即在 $1$ 到 $n$ 中与 $n$ 互素的正整数个数。

Proposition

若 $n = p_1^{k_1} \cdots p_m^{k_m}$ ，则

Copy LaTeX

Proof

对素数幂 $p^k$ ，不与其互素的整数恰为 $p$ 的倍数，共有 $p^{k-1}$ 个，因此

Copy LaTeX

一般情形由互素情况下的乘法性得到。

Theorem (欧拉定理)

对于一般的整数 $n \in \mathbb{Z}$ ， $a \in \mathbb{Z}$ ，若 $(a,n)=1$ ，则

Copy LaTeX

Proof

设 $x_1,\dots,x_{\varphi(n)}$ 为 $\{1,\dots,n\}$ 中所有与 $n$ 互素的整数，则

Copy LaTeX

构成同一集合的一个排列。因此

Copy LaTeX

由于该乘积与 $n$ 互素，两边可约去，得到

Copy LaTeX

Remark

欧拉定理给出的 $\varphi(n)$ 并不能保证是最优的，可能存在更小的正整数 $\lambda(n)$ ，满足 $\lambda(n) \mid \varphi(n)$ ，使得

Copy LaTeX

中国剩余定理（孙子定理）

Theorem

设 $n_1, n_2, \dots, n_k$ 两两互素，即 $(n_i,n_j)=1$ （ $i\neq j$ ），则同余方程组

Copy LaTeX

存在解，且解在模 $N = n_1 n_2 \cdots n_k$ 意义下唯一。

Proof (构造性证明)

记 $N = n_1 n_2 \cdots n_k$ ，并令 $N_i = \frac{N}{n_i}$ ，由于 $(N_i, n_i)=1$ ，存在整数 $M_i$ ，使

Copy LaTeX

构造

Copy LaTeX

则对任意 $j$ ，有：

Copy LaTeX

因此 $x$ 是所求的解。解在模 $N = n_1 n_2 \cdots n_k$ 意义下的唯一性显然。

Remark

对于 $n_1, n_2, \dots, n_k$ 不满足两两互素的情况，为了应用中国剩余定理，必须要拆解转换为互素的情况进行处理。

Example

求解：

Copy LaTeX

Solution

$N=15$ ， $N_1=5$ ， $N_2=3$ 。

Copy LaTeX

因此

Copy LaTeX

整数值多项式

Definition (整数值多项式)

设多项式 $f \in \mathbb{Q}[x]$ ，满足

Copy LaTeX

称此类多项式为在 $\mathbb{Z}$ 上的整数值多项式，记为

Copy LaTeX

Definition (二项式基)

对非负整数 $k \in \mathbb{Z}_{\geqslant 0}$ ，定义

Copy LaTeX

Lemma

对任意 $k \in \mathbb{Z}_{\geqslant 0}$ 和 $n \in \mathbb{Z}$ ，有 $\binom{n}{k} \in \mathbb{Z}$ 。

Proof

当 $n \geqslant k$ 时， $\binom{n}{k}$ 为通常的组合数，显然为整数。当 $n < k$ 时，利用恒等式

Copy LaTeX

右端为整数，因此 $\binom{n}{k} \in \mathbb{Z}$ 。

Theorem (整数值多项式的刻画)

多项式 $f \in \mathbb{Q}[x]$ 满足 $f(\mathbb{Z}) \subset \mathbb{Z}$ 当且仅当存在整数系数 $a_k \in \mathbb{Z}$ ，使得

Copy LaTeX

并且该表示唯一。亦即： $\mathrm{Int}(\mathbb{Z})$ 是以 $\{\binom{x}{k}\}$ 为基的 $\mathbb{Z}$ -模。

Copy LaTeX

并且有严格包含关系

Copy LaTeX

Proof

递归定义前向差分算子

Copy LaTeX

对任意次数不超过 $d$ 的多项式，都可以写成 Newton 插值的形式：

Copy LaTeX

必要性： 若 $f(n) \in \mathbb{Z}$ 对所有 $n \in \mathbb{Z}$ 成立，则
$Copy LaTeX$
取 $a_k := \Delta^k f(0) \in \mathbb{Z}$ 即可满足要求。由于 $\{\binom{x}{k}\}_{k=0}^d$ 构成 $\mathbb{Q}[x]_{\leqslant d}$ 的一组基，因此表示唯一。
充分性： 若
$Copy LaTeX$
由引理可知，对任意 $n \in \mathbb{Z}$ ，每一项均为整数，因此
$Copy LaTeX$

Example

Copy LaTeX

Example

求证：

Copy LaTeX

Solution

这个同余形式的命题等价于

Copy LaTeX

根据前面的定理，只需要验证 $f(x)$ 是否可以用二项式基展开，分解可得

Copy LaTeX

因此原命题得证。

Remark

当然，这个命题也可以用费马小定理直接证明：显然有 $n^5 \equiv n \pmod{5}$ ，奇偶性分析可得 $n^5 \equiv n \pmod{2}$ ，因此得证。