进阶≈ 15 分钟未开始

整除与带余除法

核心概念

整除:设 $a,\ b$ 是整数且 $b \neq 0$ 。如果存在整数 $q$ ,使得 $a = bq$ ,就说 $b$ 整除 $a$ ,记作 $b \mid a$ ,称 $b$ 是 $a$ 的约数(因数), $a$ 是 $b$ 的倍数。否则记作 $b \nmid a$ 。

带余除法:对任意整数 $a$ 和正整数 $b$ ,存在唯一的一对整数 $q,\ r$ ,使得

a = bq + r,\qquad 0 \le r < b.

这里 $q$ 是商, $r$ 是余数。 $b \mid a$ 当且仅当 $r = 0$ 。

整除的基本性质(设下列除数均非零):

整除的核心是"没有零头"。把 $a$ 个物体每 $b$ 个分成一堆, $q$ 是堆数, $r$ 是剩下分不满一堆的零头。整除就是"恰好分完,零头为 $0$ "。

"线性组合"性质是数论里最常用的武器:如果 $a$ 同时整除两个数,它就整除这两个数任意整数倍的和与差。很多"求证某式能被 $7$ 整除"的题,本质都是把目标式拆成 $7$ 的倍数的线性组合。

带余除法

23 = 5 × 4 + 3商 q = 4，余数 r = 3（0 ≤ 3 < 5）

被除数 a23

除数 b5

绿色是分满的整堆（共 4堆），红色是分不满一堆的零头。余数 r 永远满足 0 ≤ r < b。

例题 1用线性组合证整除

设整数 $d$ 同时整除 $3n+4$ 和 $2n+3$ ,求 $d$ 的所有可能值。

这说明 $3n+4$ 与 $2n+3$ 对任意整数 $n$ 都互质。

▸查看解答步骤

答: d ∣ 1,故 d = 1

例题 2带余除法定形

证明:任何整数的平方除以 $3$ 的余数只能是 $0$ 或 $1$ 。

▸查看解答步骤

答: r ∈ {0,1,2}，平方后余数 ∈ {0,1}

$100$ 除以 $13$ 的余数是多少?

$13\times 7 = 91$ , $100 - 91 = 9$ ,且 $0 \le 9 < 13$ ,所以余数是 $9$ 。

若 $a \mid b$ 且 $a \mid c$ ,下列一定成立的是?

a \mid (5b - 2c)

a \mid (b/c)

bc \mid a

a \mid (b + c + 1)

线性组合性质保证 $a \mid (5b-2c)$ 。其余选项都没有依据。

一个整数的平方除以 $4$ 的余数只能是 $0$ 或 $1$ 。

偶数 $2k$ 的平方 $4k^2$ 余 $0$ ;奇数 $2k+1$ 的平方 $4k^2+4k+1$ 余 $1$ 。

带余除法 $a = bq + r$ 中,余数 $r$ 必须满足?

0 \le r < b

0 < r \le b

r

可以是任意整数

r

必须小于

q

余数的标准范围是 $0 \le r < b$ ,这保证了 $q,\ r$ 的唯一性。

$123$ 除以 $7$ 的余数是多少?

$7\times17 = 119$ , $123 - 119 = 4$ 。

按 $0\le r<3$ 的规定, $-7$ 除以 $3$ 的余数是多少?

$-7 = 3\times(-3) + 2$ ,余数为 $2$ 。

把" $b$ 是 $a$ 的约数"和" $a$ 是 $b$ 的约数"搞反。 $b \mid a$ 读作" $b$ 整除 $a$ ",意思是 $a$ 是 $b$ 的倍数。
忽略余数的范围。 $-7 = 3\times(-3) + 2$ ,余数是 $2$ (不是 $-1$ ),因为要求 $0 \le r < 3$ 。
以为整除性质对除法也成立。 整除对加减、整数倍封闭,但对相除不封闭。

前置知识点

—

接下来学习