跳到正文
Mastering
AMC 10/12
数论 · 第 22 章

整除与勒让德公式

只看数字就判断整除，求出缺失的数字；不用乘出来，就能数出阶乘里某个质因数的个数。

这一章讲什么？
你需要先会
在 YouTube 上打开
22.0a0%

整除判定法则

在本节中，你将能够 只看各位数字，就判断一个数能否被 2–12 或 15 整除，并用这些法则求出缺失的数字。

找出只由 4 和 9 组成、能被 36 整除的最小的数。你根本不用做除法：4 的法则决定结尾，9 的法则决定需要几个 4。

每条法则只看数的一部分。对于 22、44、55、88 和 1010，看末几位就够了，因为 1010、100100 和 10001000 已经是这些除数的倍数。 对于 33 和 99，看数字和，因为 10≡110 \equiv 1（mod 99）。

对于 1111，把奇数位置上的数字和偶数位置上的数字分别相加。注意：10≡−110 \equiv -1（mod 1111），所以各数位的位值在 +1+1 和 −1-1 之间交替。

66、1212 和 1515 的法则只是把两条更简单的法则合起来。缺失的数字在法则里变成一个未知数，法则就变成了一个小方程。

动手探索先玩，再学公式

444944 不能被 9 整除：数字和 4 + 4 + 4 + 9 + 4 + 4 = 29，不是 9 的倍数。

点击一个数字，让它加 1。

  • 数字和 4 + 4 + 4 + 9 + 4 + 4 = 29，不是 9 的倍数。
444944 不能被 9 整除

用除法验证： 444944 ÷ 9 = 49438 余 2

444944 不能被 9 整除。数字和 4 + 4 + 4 + 9 + 4 + 4 = 29，不是 9 的倍数。

认识概念

概念 22.0.1 · 整除判定法则

除数 法则
22 个位数字是偶数
33 各位数字之和能被 33 整除
44 末 22 位能被 44 整除
55 个位数字是 00 或 55
66 能被 22 和 33 整除
77 不断减去 77 的倍数，直到剩下一个小数，看它能否被 77 整除
88 末 33 位能被 88 整除
99 各位数字之和能被 99 整除
1010 个位数字是 00
1111 把奇数位置上的数字相加（OO），把偶数位置上的数字相加（EE）。如果 ∣O−E∣\lvert O - E \rvert 能被 1111 整除，那么这个数也能被 1111 整除
1212 能被 33 和 44 整除
1515 能被 33 和 55 整除

看例题先预测，再揭晓

例 22.1

AMC 10

设 nn 是同时能被 44 和 99 整除、并且十进制表示只由数字 44 和 99 组成（两种数字都至少出现一次）的最小正整数。nn 的末四位是什么？

整除放大镜 (总数在例题最后一步揭晓)

  • 末 2 位是 49，49 = 4 × 12 + 1，不是 4 的倍数。
? (例题最后一步揭晓)

用除法验证： 49 ÷ 4 = ? (例题最后一步揭晓)

49 ÷ 4。末 2 位是 49，49 = 4 × 12 + 1，不是 4 的倍数。

  1. 1

    先看 44。只有末两位有关系。由 44 和 99 组成的哪种结尾是 44 的倍数？

    先预测一下：
    点击一个选项，或输入它的字母（A–E）。
在 YouTube 上打开

自己做

习题 22.1.2

AMC 12

这道题在书中还以 21.3.15 的编号出现。

有多少个奇的正 33 位整数能被 33 整除，但不含数字 33？

习题 22.1.6

AMC 10

如果一个正整数的每一位数字都严格大于它前一位数字，就称它为上坡数。例如 13571357、8989、55 都是上坡数，而 3232、12401240、466466 都不是。有多少个上坡数能被 1515 整除？

竞赛角真实竞赛题

习题 22.1.5

AIME

使 n3+100n^3 + 100 能被 n+10n + 10 整除的最大正整数 nn 是多少？

习题 22.1.7（补充题）

AMC 10

对所有正偶数 nn，都能整除

(n+1)(n+3)(n+5)(n+7)(n+9)(n + 1)(n + 3)(n + 5)(n + 7)(n + 9)

的最大整数是多少？

习题 22.1.13（补充题）

AMC 10

有多少个正整数 n≤1000n \le 1000 使得

⌊998n⌋+⌊999n⌋+⌊1000n⌋\left\lfloor \frac{998}{n} \right\rfloor + \left\lfloor \frac{999}{n} \right\rfloor + \left\lfloor \frac{1000}{n} \right\rfloor

不能被 33 整除？（回忆：⌊x⌋\lfloor x \rfloor 表示小于或等于 xx 的最大整数。）

过关检测（第 22.0a 节）

3 题中答对 2 题即可掌握本节。每题只有一次机会，没有提示。
1

哪个数字 AA 能使四位数 3A723A72 被 99 整除？

2

数字 dd 取何值时，六位数 73d,42573d{,}425 能被 1111 整除？

3

下面这些数中有几个能被 66 整除：  135,  2340,  1236,  4510,  8112\;135,\; 2340,\; 1236,\; 4510,\; 8112？

22.0b0%

勒让德公式

在本节中，你将能够 用勒让德公式数出 n! 中质因数 p 的个数，并用它数出阶乘末尾有几个零。

100!100! 末尾有几个零？它的 158158 位数字你一个都不需要。只要数一数有几个 55。

末尾的一个零就是一个因数 10=2×510 = 2 \times 5。阶乘里的 22 总比 55 多，所以零的个数就是 55 的个数。

要数 100!100! 中有几个 55，先数 55 的倍数（每个贡献一个 55），再数 2525 的倍数（每个再贡献第二个），依此类推。这就是勒让德公式。

动手探索先玩，再学公式

19! 中因数 5 的个数：3 = 3

n19
51015
  • 第 1 层：不超过 19 的 5 = 5 的倍数：3
19! 中因数 5 的个数：3 = 3

19! 有 16 个因数 2 和 3 个因数 5。每个零需要一个 2 和一个 5，所以末尾零的个数是 min(16, 3) = 3

19! 中因数 5 的个数：3 = 3

认识概念

定理 22.0.2 · 勒让德定理

对于质数 pp，n!n! 中因数 pp 的个数是

vp(n!)=⌊np⌋+⌊np2⌋+⌊np3⌋+⋯v_p(n!) = \left\lfloor \frac{n}{p} \right\rfloor + \left\lfloor \frac{n}{p^2} \right\rfloor + \left\lfloor \frac{n}{p^3} \right\rfloor + \cdots

一旦 pk>np^k > n，求和就停止，因为后面的每一项都是 00。

看例题先预测，再揭晓

例 22.2

AIME

设 NN 是乘积 1! 2! 3! 4!⋯99! 100!1!\,2!\,3!\,4! \cdots 99!\,100! 的十进制表示中，右端连续的 00 的个数。求 NN 除以 10001000 的余数。

勒让德堆叠 (总数在例题最后一步揭晓)

20406080100
  • 第 1 层：对 k = 1 … 100 把 ⌊k/5⌋ 加起来：?
  • 第 2 层：对 k = 1 … 100 把 ⌊k/5²⌋ = ⌊k/25⌋ 加起来：?
1!·2!·…·100! 中因数 5 的个数：0（目前）

1!·2!·…·100! 中因数 5 的个数：0（目前）

  1. 1

    末尾的每个零都是一个因数 10=2×510 = 2 \times 5。在 1! 2!⋯100!1!\,2!\cdots100! 中，哪个质数先用完，从而决定了 NN？

    先预测一下：
    点击一个选项，或输入它的字母（A–E）。
在 YouTube 上打开

例 22.3

AMC 10

19!19! 的十进制表示是 121,6T5,100,40M,832,H00121{,}6T5{,}100{,}40M{,}832{,}H00，其中 TT、MM 和 HH 表示未给出的数字。T+M+HT + M + H 是多少？

整除放大镜 (总数在例题最后一步揭晓)

点击一个字母，给它试一个数字。

  • 数字和 1 + 2 + 1 + 6 + T + 5 + 1 + 0 + 0 + 4 + 0 + M + 8 + 3 + 2 + H + 0 + 0 = 33 + T + M + H 必须是 9 的倍数。
1216T510040M832H00 能被 9 整除吗？取决于 T、M、H

使它能被 9 整除的 T、M、H 的取值：

? (例题最后一步揭晓)

1216T510040M832H00 能被 9 整除吗？取决于 T、M、H。数字和 1 + 2 + 1 + 6 + T + 5 + 1 + 0 + 0 + 4 + 0 + M + 8 + 3 + 2 + H + 0 + 0 = 33 + T + M + H 必须是 9 的倍数。

  1. 1

    先求 HH。19!19! 中有几个因数 55？

    先预测一下：
在 YouTube 上打开

自己做

习题 22.1.3

AMC 10

对于所有整数 n≥9n \ge 9，

(n+2)!−(n+1)!n!\frac{(n + 2)! - (n + 1)!}{n!}

的值总是下列哪一种？

点击一个选项，或输入它的字母（A–E）。

竞赛角真实竞赛题

习题 22.1.8（补充题）

AMC 12

数 21!=51,090,942,171,709,440,00021! = 51{,}090{,}942{,}171{,}709{,}440{,}000 有超过 60,00060{,}000 个正因数。从中随机选一个。它是奇数的概率是多少？

习题 22.1.15（补充题）

AIME

定义 n!!n!!：当 nn 为奇数时为 n(n−2)(n−4)⋯3⋅1n(n - 2)(n - 4) \cdots 3 \cdot 1，当 nn 为偶数时为 n(n−2)(n−4)⋯4⋅2n(n - 2)(n - 4) \cdots 4 \cdot 2。把

∑i=12009(2i−1)!!(2i)!!\sum_{i=1}^{2009} \frac{(2i - 1)!!}{(2i)!!}

写成最简分数时，它的分母是 2ab2^a b，其中 bb 是奇数。求 ab10\dfrac{ab}{10}。

过关检测（第 22.0b 节）

3 题中答对 2 题即可掌握本节。每题只有一次机会，没有提示。
1

30!30! 中有几个因数 33？（也就是说，使 3k∣30!3^k \mid 30! 的最大 kk 是多少？）

2

125!125! 末尾有几个零？

3

使 2k2^k 整除 50!50! 的最大 kk 是多少？

22.1

练习题

在本节中，你将能够 综合运用本章的所有工具：穿过网格线、最大公因数、模 99 的余数和数字和技巧。

这些题把各种法则混在一起。有些是本书前面出现过的题：如果你当时做过了，这次试试换一条路。

竞赛角真实竞赛题

习题 22.1.1

AMC 10

一块宽 1010 英尺、长 1717 英尺的长方形地板铺着 170170 块边长一英尺的正方形瓷砖。一只虫子沿直线从一个角走到对角。包括第一块和最后一块瓷砖在内，虫子经过了多少块瓷砖？

习题 22.1.4

IMO

证明：对于每个自然数 nn，分数 21n+414n+3\frac{21n + 4}{14n + 3} 都是既约分数。

这道题要求写出证明。先在纸上写出你的证明，需要时可以看提示，然后和书面证明对照。

习题 22.1.9（补充题）

AMC 10

这道题在书中还以 22.1.6 的编号出现。

如果一个正整数的每一位数字都严格大于它前一位数字，就称它为上坡数。例如 13571357、8989 和 55 都是上坡数，而 3232、12401240 和 466466 都不是。有多少个上坡数能被 1515 整除？

习题 22.1.10（补充题）

AMC 10

这道题在书中还以 21.3.20 的编号出现。

设 N=123456789101112…4344N = 123456789101112 \dots 4344 是把从 11 到 4444 的整数按顺序依次写下所组成的 7979 位数。NN 除以 4545 的余数是多少？

习题 22.1.11（补充题）

AMC 10

这道题在书中还以 22.1 的编号出现。

设 nn 是同时能被 44 和 99 整除、并且十进制表示只由数字 44 和 99 组成（两种数字都至少出现一次）的最小正整数。nn 的末四位是什么？

习题 22.1.12（补充题）

AMC 10

一个由三位整数组成的有限数列具有如下性质：每一项的十位数字和个位数字分别是下一项的百位数字和十位数字，并且最后一项的十位数字和个位数字分别是第一项的百位数字和十位数字。例如，这样的数列可能以 247247、475475、756756 这几项开头，并以 824824 这一项结尾。设 SS 是数列所有项的和。总能整除 SS 的最大质因数是多少？

习题 22.1.14（补充题）

AIME

设 a10=10a_{10} = 10，并且对每个正整数 n>10n > 10，令 an=100an−1+na_n = 100a_{n-1} + n。求使 ana_n 是 9999 的倍数的最小正整数 n>10n > 10。