整除：数论的第一块砖

$a,b$ 是整数，$b\ne 0$。如果存在整数 $k$ 使 $a=bk$，就说 $b$ 整除 $a$，记作 $b\mid a$。

换成大白话：$a$ 是 $b$ 的整数倍，$a$ 除以 $b$ 余数为零。

几个立刻能看出来但常被忽略的事实：

• 任何整数都整除 $0$（$0=b·0$），但 $0$ 不整除任何非零整数
• $\pm 1$ 整除所有整数
• 若 $b\mid a$ 且 $a\ne 0$，则 $|b|\le |a|$

性质一（传递）：$a\mid b$，$b\mid c$ ⇒ $a\mid c$。

设 $b=am$，$c=bn$，则 $c=a(mn)$，成立。

性质二（可加可减）：$a\mid b$，$a\mid c$ ⇒ $a\mid (b\pm c)$。

设 $b=am$，$c=an$，则 $b\pm c=a(m\pm n)$。

性质三（倍数）：$a\mid b$ ⇒ $a\mid kb$，对任意整数 $k$ 成立。

性质四（线性组合）：$a\mid b$，$a\mid c$ ⇒ $a\mid (mb+nc)$，对任意整数 $m,n$。

第四条是前两条的合体，也是最常用的。它的实际意义是：如果一堆数都能被 $a$ 整除，那么它们的任意整数组合也能被 $a$ 整除。看到“证明 $a\mid$ 某个复杂式子”，第一反应就该是把它拆成若干个已知能被 $a$ 整除的部分。

任意整数 $a$ 除以正整数 $m$，都存在唯一的整数 $q$ 和 $r$，使

$q$ 叫商，$r$ 叫余数。$r=0$ 就是整除。

带余除法是“分类讨论”的依据：要证明某个性质对所有整数成立，按余数分成 $m$ 类分别验证，就穷尽了所有情况。$m=2$ 就是奇偶分析，$m=3$ 就是模 3 分类。

例1 用线性组合

证明：若 $a\mid b$ 且 $a\mid c$，则 $a\mid (3b-5c)$。

解：$b=am$，$c=an$，则 $3b-5c=3am-5an=a(3m-5n)$，故 $a\mid (3b-5c)$。

系数 $3,-5$ 是任意的，换成任何整数都一样。

例2 拆成已知部分

证明：对任意整数 $n$，$n^3-n$ 能被 $6$ 整除。

解：$n^3-n=n(n-1)(n+1)$，是连续三个整数。

三个连续整数中必有一个是 $3$ 的倍数；也必有一个是偶数。所以乘积被 $2$ 和 $3$ 整除，即被 $6$ 整除。

另一种写法（用带余除法）：按 $n$ 除以 $6$ 的余数分六类，逐一验证。笨但绝对可靠，考场上想不出分解时就用这个。

例3 幂的整除

证明：对任意正整数 $n$，$a-b\mid a^n-b^n$。

解：用因式分解： $$a^n-b^n=(a-b)(a^{n-1}+a^{n-2}b+\cdots +b^{n-1})$$ 后面那个括号是整数，所以 $a-b$ 整除 $a^n-b^n$。

这条结论几乎每年竞赛都会用到。特别地，$a=2$、$b=1$ 时得 $1\mid 2^n-1$（废话），但换成 $a=10$ 就得到“$9\mid {10}^n-1$”，可以用来证明“由 $n$ 个 1 组成的数能被 9 整除”。

例4 反过来用

已知 $a\mid b$，$b\mid a$，且 $a,b$ 都是正整数，求 $a$ 与 $b$ 的关系。

解：$b=am$，$a=bn$，代回得 $a=amn$，即 $a(1-mn)=0$。$a>0$，所以 $mn=1$。

$m,n$ 都是正整数，只能 $m=n=1$，故 $a=b$。

这类“互相整除”的推理在竞赛里很常见，套路是设出倍数、代回、利用正负和大小夹逼。

例5 整除与余数

求所有正整数 $n$，使 $n+1\mid n^2+1$。

思路：用 $n+1$ 去除 $n^2+1$，把 $n$ 换成 $(n+1)-1$。

解： $$n^2+1=[(n+1)-1{]}^2+1=(n+1{)}^2-2(n+1)+2$$ 前两项都被 $n+1$ 整除，所以要 $n+1\mid 2$。

$n+1$ 是大于 $1$ 的正整数，只能是 $2$，故 $n=1$。

检验：$n=1$ 时 $2\mid 2$，成立。