AMC10/12教材 - 数学 (10)

§2.1 基础:素数(prime number)与合数(composite number)

定义 2.1.1

素数(prime number)指只能被1和它本身整除的数。合数(composite number)指不是素数的任何整数，其正因数多于2个。

掌握整除规则非常重要。

被2整除规则:个位数字必须为偶数。

被3整除规则:各位数字之和必须能被3整除。

被4整除规则:末两位数字必须能被4整除。

被5整除规则:末位数字必须是0或5。

被8整除规则:末三位数字必须能被8整除。

被9整除规则:各位数字之和必须能被9整除。

被11整除规则:数字的交替和之差必须能被11整除。

若想判断一个数能否被6、10或12整除，只需写出这些数的素因数分解(prime factorization)，然后分别应用对应素因数的整除规则。例如，6= \( 2 \cdot 3 \) ，因此需同时满足被2和被3整除的规则；10需满足被2和被5整除的规则；12需满足被3和被4整除的规则。

问题2.1.2——某直角三角形的两个锐角分别为 \( {a}^{ \circ } \) 和 \( {b}^{ \circ } \) ，其中 \( a > b \) ，且 \( a \) 和 \( b \) 均为素数(prime number)。求 \( b \) 的最小可能值。 \( \textbf{(A)}2\;\textbf{(B)}3\;\textbf{(C)}5\;\textbf{(D)}7\;\textbf{(E)}{11} \) 来源:2020 AMC 10

解答:由于任何三角形内角和为 \( {180}^{ \circ } \) ，而已有一个角为 \( {90}^{ \circ } \) ，故a与b之和必为 \( {90}^{ \circ } \) 。为使b最小，我们从 \( {1}^{ \circ } \) 开始向上测试 \( b \) 的值。注意:只需测试奇数，因为除 \( {2}^{ \circ } \) 外，偶数不可能是素数。

\( \angle \mathrm{B}\left( {\angle \mathrm{A} = {90} - \angle \mathrm{B}}\right) \) 的试验

1:不是素数

2: \( \mathrm{A} = {90} - 2 = {88} \) (偶数)

3: \( \mathrm{A} = {90} - 3 = {87} \) (可被3整除)

5: \( \mathrm{A} = {90} - 5 = {85} \) (可被5整除)

7: \( \mathrm{A} = {90} - 7 = {83} \) (质数)

因此，答案是7(D)

问题2.1.3——设 \( p, q \) 和 \( r \) 为质数，使得 \( {2pqr} + p + q + r = {2020} \) 。求 \( {pq} + {qr} + {pr} \) 。

来源:2020 Purple Comet

解答:本题中，我们假设所有质数 \( (p, q \) 和 \( r \) 均为奇数，因为除非该质数为2，否则总是如此。

可以看出 \( {2pqr} \) 始终为偶数。此外，若 \( p, q, r \) 为奇数，则 \( {2pqr} + p + q + r \) 的和为奇数。然而，2020为偶数，这不可能。

因此，其中一个质数必须是2。假设 \( p \) 为2，则方程变为 \( {4qr} + q + r = {2018} \) 。

根据西蒙的因式分解技巧(稍后的代数章节将介绍)，可将表达式因式分解为

\[ \left( {{2q} + \frac{1}{2}}\right) \left( {{2r} + \frac{1}{2}}\right) = {2018} + \frac{1}{4} \]

两边同乘4得

\( \left( {{4q} + 1}\right) \left( {{4r} + 1}\right) = {8073} \)

进行质因数分解: \( {8073} = {3}^{3} \cdot {13} \cdot {23} \)

现在需找到一对数，其乘积等于上述质因数分解结果。我们将这两个数分别设为 \( {4q} + 1 \) 和 \( {4r} + 1 \) ，以检验 \( q \) 和 \( r \) 是否为质数。

可逐一测试这些数对，可行的组合为 \( {3}^{2} \cdot {13} \) 和 \( 3 \cdot {23} \) 。若令 \( {3}^{2} \cdot {13}\left( {117}\right) \) 等于 \( {4q} + 1 \) ， \( 3 \cdot {23}\left( {69}\right) \) 等于 \( {4r} + 1 \) ，则得到 \( q = {29} \) 和 \( r = {17} \) 。

已知 \( p = 2, q = {29}, r = {17} \) ，将其代入 \( {pq} + {qr} + {pr} \) ，可得答案为585。

§2.2 倍数、约数、质因数分解

定义 2.2.1

一组数的最小公倍数(Least Common Multiple，LCM)是能被该组所有数整除的最小整数。通常，你可以通过对该组所有数进行质因数分解来求出最小公倍数。

定理 2.2.2

设 a 和 b 的质因数分解分别为:

\[ a = {p}_{1}^{{a}_{1}} \cdot {p}_{2}^{{a}_{2}}\cdots {p}_{n}^{{a}_{n}}\text{ and }b = {p}_{1}^{{b}_{1}} \cdot {p}_{2}^{{b}_{2}}\cdots {p}_{n}^{{b}_{n}}, \]

则 \( \operatorname{lcm}\left( {a, b}\right) = {p}_{1}^{\max \left( {{a}_{1},{b}_{1}}\right) } \cdot {p}_{1}^{\max \left( {{a}_{2},{b}_{2}}\right) }\cdots {p}_{n}^{\max \left( {{a}_{n},{b}_{n}}\right) } \)

上述定理用于求两个数的最小公倍数。若对任意一组数进行质因数分解，则对所有出现的质数取其在各数中的最大指数即可。若你尚未理解上述定理，无需慌张，稍后将有示例说明。

定义 2.2.3

一组数的最大公约数(Greatest Common Divisor，GCD)是能整除该组所有数的最大整数。通常，你可以通过对该组所有数进行质因数分解来求出最大公约数。

定理 2.2.4

设 a 和 b 的质因数分解分别为:

\[ a = {p}_{1}^{{a}_{1}} \cdot {p}_{2}^{{a}_{2}}\cdots {p}_{n}^{{a}_{n}}\text{ and }b = {p}_{1}^{{b}_{1}} \cdot {p}_{2}^{{b}_{2}}\cdots {p}_{n}^{{b}_{n}}, \]

则 \( \gcd \left( {a, b}\right) = {p}_{1}^{\min \left( {{a}_{1},{b}_{1}}\right) } \cdot {p}_{1}^{\min \left( {{a}_{2},{b}_{2}}\right) }\cdots {p}_{n}^{\min \left( {{a}_{n},{b}_{n}}\right) } \)

上图是学习最大公约数的最佳视角。若对任意一组数进行质因数分解，则对所有出现的质数取其在各数中的最小指数即可。例如，若 \( \mathrm{I} \) 正在求最大公约数的两个数分别能被 \( {2}^{6} \) 和 \( {2}^{8} \) 整除，则取 \( {2}^{6} \) 来计算最大公约数，因为 6 小于 8。下面将给出一个简单示例。

例 2.2.5

15 和 24 的最大公约数是多少？

解:进行质因数分解得 15 = \( 3 \cdot 5 \) ，24 = \( {2}^{3} \cdot 3 \) 。

我们现在将统计这两个数的所有唯一质因数(prime divisors)，即使某个质因数只整除其中一个数。我们的唯一质因数为2、3和5。由于因数2的最小指数是0(因为它不整除15)，我们的最大公约数(GCD)将包含 \( {2}^{0} \) 。同理，质因数3的最小指数就是1。对于质因数5，尽管它整除15，但在24的质因数分解中5的指数为0(小于1)。

因此，我们的最大公约数是 \( {2}^{0} \cdot {3}^{1} \cdot {5}^{0} = 3 \) 。

关键提示:记住，即使某个质因数只整除集合中的一个数，其最小指数仍为0，因为它并未整除所有数。

对于最小公倍数(LCM)同理，你需对所有唯一质因数取指数的最大值。

例2.2.6

求18、22和24的最小公倍数。解法:我们将写出所有数的质因数分解。

\( {18} = {2}^{1} \cdot {3}^{2} \)

\( {22} = {2}^{1} \cdot {11} \)

\( {24} = {2}^{3} \cdot 3 \)

由于2、3和11的最大指数分别为3、2和1，因此最小公倍数为 \( {2}^{3} \cdot {3}^{2} \cdot {11}^{1} = {792} \)

注意:只需记住，最小公倍数是各唯一因数所有指数的最大值，而最大公约数是各唯一因数所有指数的最小值。

问题2.2.7——正整数 \( n \) 与18的最小公倍数为180，且 \( n \) 与45的最大公约数为15。求 \( n? \) 的各位数字之和。

\( \textbf{(A)}\;3\;\textbf{(B)}\;6\;\textbf{(C)}\;8\;\textbf{(D)}\;9\;\textbf{(E)}\;{12} \)

来源:2022 AMC

解法:由于最小公倍数需对数集进行质因数分解，并取所有唯一质因数的最大指数(所有质因数的并集)，我们将对 \( n \) 和18进行此操作。对45亦同理。

\( {18} = 2 \cdot {3}^{2} \)

\( {180} = {2}^{2} \cdot {3}^{2} \cdot 5 \)

\[ {45} = {3}^{2} \cdot 5 \]

\( {15} = 3 \cdot 5 \)

利用前两次质因数分解，我们知道 \( {2}^{2} \) 必须整除 \( n \) ，因为 \( {2}^{2} \) 整除最小公倍数180，但不整除18(我们希望质因数的最大指数能整除最小公倍数)。我们无法用质因数3得出任何结论，因为 \( {3}^{2} \) 同时整除最小公倍数和18。这意味着 \( n \) 中3的指数必须在0到2之间，因为该质因数的最大指数条件已满足。

现在我们处理45和15。显然5必须整除 \( n \) ，因为它整除45与 \( n \) 的最大公约数15。我们还知道3必须整除 \( n \) ，才能使最大公约数为15(若 \( n \) 不含因数3，则最大公约数将不能被3整除)。

因此， \( n \) 为 \( {2}^{2} \cdot 3 \cdot 5 \) ，计算得60。我们的答案是 \( 6 + 0 \) ，即6(B)。

问题2.2.8——有多少个正整数 \( n \) 满足: \( n \) 是5的倍数，且5!与 \( n \) 的最小公倍数等于10!与 \( n \) 的最大公约数的5倍？

\( \textbf{(A)}{12}\;\textbf{(B)}{24}\;\textbf{(C)}{36}\;\textbf{(D)}{48}\;\textbf{(E)}{72} \)

来源:2021 AMC

解:给定方程为 \( \operatorname{lcm}\left( {5!, n}\right) = 5 \cdot \gcd \left( {{10}!, n}\right) \)

我们可以对5!进行质因数分解得到 \( {2}^{3} \cdot 3 \cdot 5 \) 。

我们可以对10!进行质因数分解得到 \( {2}^{8} \cdot {3}^{4} \cdot {5}^{2} \cdot 7 \) 。

注:上述数字均使用勒让德定理(Legendre's theorem)进行质因数分解，你很快就会学到。现在无需担心这一步。

最小公倍数(LCM)取每个唯一质因数的最大指数，而最大公约数(gcd)取每个唯一质因数的最小指数。我们将关注每个唯一的质因数。

从2开始:由于最小公倍数涉及任何唯一质因数的最大指数，我们知道最小公倍数必须至少能被 \( {2}^{3} \) 整除，因为5!。

在最大公约数中看2，2的指数必须小于或等于8。因此，n可以取3到8的所有值。

对于3，最小公倍数至少有一个指数为1的3。最大公约数关系告诉我们3的最大指数为4。因此， \( n \) 的质因数3的指数可以是1到4之间的任何值。

对于5，我们必须使用给定条件5整除 \( \mathrm{n} \) 。假设 \( n = {5}^{a} \cdot x \) 。我们可以写出 \( 5 : \max \left( {1, a}\right) = 1 + \min \left( {2, a}\right) \) 的指数方程。测试 \( a \) 的值，发现唯一可行的是3，这意味着 \( n \) 必须能被 \( {5}^{3} \) 整除。

对于7，我们可以写出指数的方程。假设 \( {7}^{b} \) 整除 \( n \) 。那么，我们得到 \( \max \left( {0,\mathrm{\;b}}\right) = \min \left( {1,\mathrm{\;b}}\right) \) 。测试值表明0和1都可行。这意味着质因数7的可能指数为0和1。

由于2有6种可能的指数，3有4种，5有1种，7有2种，我们的答案是这些数字相乘 \( \left( {6 \cdot 4 \cdot 1 \cdot 2}\right) \) ，得到48(D)。

问题2.2.9 - 求满足以下方程组的正整数7元组(a, b, c, d, e, f, g)的数量:

\[ {abc} = {70} \]

\[ \text{cde} = {71} \]

\[ {efg} = {72}\text{.} \]

来源:2019 AIME

解:由于 \( c \) 在第一和第二个方程中共同出现， \( e \) 在第二和第三个方程中共同出现，我们知道 \( c \) 必须整除71和70，而 \( e \) 必须整除71和72。

处理 \( c \) ，显然除了1之外没有能同时整除71和70的因数。因此， \( c = 1 \) 。同样，除了1之外没有能同时整除71和72的因数，所以 \( e = 1 \) 。

我们的3个方程现在变为

\[ {ab} = {70} \]

\[ d = {71} \]

\[ {fg} = {72} \]

既然我们已经知道我们的值 \( c, d, e \) 分别为1、71、1，我们只需利用方程 \( {ab} = {70} \) 和 \( {fg} = {72} \) 来求这4个变量可能取值的个数。

由于 \( {70} = 2 \cdot 5 \cdot 7 \) ，该数共有8个因数(如果你不明白为何有8个因数，别担心，书中稍后将会解释相关定理)。我们只需把乘积为70的因数配对，例如(a, b)的可能取值为 \( \left( {1,{70}}\right) ,\left( {{70},1}\right) ,\left( {2,{35}}\right) \) 以及(35,2)。显然，选择 \( a \) 和 \( b \) 的值共有8种方式。

先对 \( {fg} = {72} \) 进行此操作，得到 \( {72} = {2}^{3} \cdot {3}^{2} \) 。它有 \( \left( {3 + 1}\right) \left( {2 + 1}\right) = {12} \) 个因数，这意味着选择 \( f \) 和 \( g \) 的值共有这么多方式。

我们选择变量的总方式数为 \( 8 \cdot {12} \) ，即96。

问题2.2.10——设 \( {a}_{1},{a}_{2},{a}_{3},{a}_{4},{a}_{5} \) 为正整数，使得 \( {a}_{1},{a}_{2},{a}_{3} \) 和 \( {a}_{3},{a}_{4},{a}_{5} \) 均为几何序列，且 \( {a}_{1},{a}_{3},{a}_{5} \) 为等差序列。若 \( {a}_{3} = {1575} \) ，求 \( \left| {{a}_{4}{a2}}\right| \) 的所有可能值。

来源:2017 CMIMC

解法:本题中，我们假设几何序列 \( {a}_{1},{a}_{2},{a}_{3} \) 的公比为 \( r \) 。我们倒推，用 \( {a}_{3}\left( {a}_{3}\right. \) (已知为1575)和 \( r \) 表示项 \( {a}_{1} \) 和 \( {a}_{2} \) 。

\[ {a}_{1} = \frac{1575}{{r}^{2}} \]

\[ {a}_{2} = \frac{1575}{r} \]

设几何序列 \( {a}_{3},{a}_{4},{a}_{5} \) 的公比为 \( s \) ，则

\[ {a}_{4} = {1575s} \]

\[ {a}_{5} = {1575}{s}^{2} \]

由于 \( {a}_{1},{a}_{3},{a}_{5} \) 构成等差序列，我们知道 \( {a}_{5} - {a}_{3} = {a}_{3} - {a}_{1} \) (因为相邻两项的差必须相同)，于是得到 \( {a}_{1} + {a}_{5} = 2{a}_{3} \) 。代入数值得

\( \frac{1575}{{r}^{2}} + {1575}{s}^{2} = 2 \cdot {1575} \)

方程两边除以1575得

\[ \frac{1}{{r}^{2}} + {s}^{2} = 2 \]

由于所有项均为整数， \( r \) 和 \( {r}^{2} \) 都能整除1575，我们对1575进行质因数分解得 \( {3}^{2} \cdot {5}^{2} \cdot 7 \) 。

由此，使 \( r \) 和 \( {r}^{2} \) 都能整除1575的 \( r \) 的可能取值为1、3、5、15。我们将逐一测试这些 \( r \) ，代入 \( \frac{1}{{r}^{2}} + {s}^{2} = 2 \) ，再用该方程求 \( s \) ，并检查 \( {1575s} \) 和 \( {1575}{s}^{2} \) 是否为整数。

测试所有 \( r \) 的值后，发现只有1和5可行，分别使 \( s \) 为0和 \( \frac{7}{5} \) 。

现在我们计算 \( {a}_{4} - {a}_{2} \) 的值，结果为 \( {1575s} - \frac{1575}{r} \) 。将我们求得的 \( r, s \) 代入，得到可能值为0和1890。

问题2.2.11——一个正整数 \( n \) 恰有4个正因数，且其所有因数之和为 \( \sigma \left( n\right) = {2112} \) 。已知小于 \( n \) 且与 \( n \) 互质的正整数个数为 \( \phi \left( n\right) = {1932} \) ，求 \( n \) 的所有真因数之和。

来源:2021 SMT

解:由于我们知道 \( n \) 有4个因数，其质因数分解必为 \( p \cdot q \) 或 \( {p}^{3} \) 的形式。

情况1: \( n = p \cdot q \)

此时所有因数之和为 \( \left( {1 + p}\right) \left( {1 + q}\right) = {2112} \)

与 \( n \) 互质的数的个数可用欧拉函数(Euler’s Totient Function)求得，结果为 \( p \cdot q \cdot \frac{p - 1}{p} \cdot \frac{q - 1}{q} \)

我们将其化简为 \( \left( {p - 1}\right) \left( {q - 1}\right) = {1932} \)

我们处理方程 \( \left( {1 + p}\right) \left( {1 + q}\right) = {2112} \) ，并将2112质因数分解为 \( {2}^{6} \cdot 3 \cdot {11} \) 。

接下来，我们为 \( 1 + p \) 和 \( 1 + q \) 配对，使其乘积为2112，得到一对48与44。由此可知，一个质数为47，另一个为43。

我们将其代入 \( \left( {p - 1}\right) \left( {q - 1}\right) = {1932} \) 验证，发现成立。因此，真因数(除自身外的所有因数)之和为 \( 1 + {43} + {47} = \mathbf{{91}} \) 。

你可以自行检验上述问题的第二种情况 \( \left( {n = {p}^{3}}\right) \) ，会发现不存在满足条件的 \( n \) 。

§2.3 因数个数与所有因数之和

要求因数个数，必须先对该数进行质因数分解。然后将所有指数加1，再将这些数相乘即可。

例如，对于数字18，其质因数分解为 \( {3}^{2} \cdot {2}^{1} \) 。接着只需将各质因数的指数加1。指数分别为2和1，加1后得3和2，相乘得6个因数。

再以180为例。180= \( {2}^{2} \cdot {3}^{2} \cdot {5}^{1} \) ，3个不同质因数的指数分别为2、2、1。各加1得3、3、2，相乘得18个因数。

定理2.3.1

所有因数之和的表达式为 \( {\sigma }_{1}\left( n\right) .{\sigma }_{1}\left( n\right) = \left( {1 + {p}_{1} + {p}_{1}^{2} + \cdots {p}_{1}^{{e}_{1}}}\right) (1 + \) \( \left. {{p}_{2} + {p}_{2}^{2} + \cdots + {p}_{2}^{{e}_{2}}}\right) \cdots \left( {1 + {p}_{k} + {p}_{k}^{2} + \cdots + {p}_{k}^{{e}_{k}}}\right) \) 。

上述公式告诉我们如何计算任意数的所有因数之和。我们逐个处理每个质因数:将该质因数的1次方到最高次方全部相加，得到该质因数的部分和；最后将所有部分和相乘即可。

例 2.3.2

140 的所有因数之和是多少？

解:要求任意数的因数之和，必须先对其进行质因数分解。

\( {140} = {2}^{2} \cdot {5}^{1} \cdot {7}^{1} \)

我们计算 \( \left( {1 + {2}^{1} + {2}^{2}}\right) \left( {1 + {5}^{1}}\right) \left( {1 + {7}^{1}}\right) \) ，得到答案 336。

如果你想求某个特定素数的幂在阶乘 \( \left( {n!}\right) \) 中出现的次数，或者想对阶乘进行质因数分解，该怎么办？

定理 2.3.3

勒让德定理(Legendre's Theorem)使我们能够求出能整除阶乘的任意素数的最大指数。

\[ {e}_{p}\left( {n!}\right) = \mathop{\sum }\limits_{{i = 1}}^{\infty }\left\lfloor \frac{n}{{p}^{i}}\right\rfloor \]

当 \( p \) 为素数且 \( {e}_{p}\left( {n!}\right) \) 是在对 \( n \) ! 进行质因数分解时 \( p \) 的最大指数时，上述公式成立。若仍有疑问，请阅读下方示例以体会如何使用该公式。

我们只需用 \( \mathrm{n} \) 除以 \( p \) 一次，即可求出能整除 \( n \) 阶乘的素数的最高幂。每次都要向下取整(floor 函数)。然后，将 \( n \) 除以 \( {p}^{2} \) 并向下取整。继续将 \( p \) 的指数加 1，直到向下取整得到 0 为止，此时停止并将所有得到的值相加。

例 2.3.4

求能整除 156! 的 5 的最高幂。

解: \( {e}_{p}\left( {{156}!}\right) = \mathop{\sum }\limits_{{i = 1}}^{\infty }\left\lfloor \frac{156}{{5}^{i}}\right\rfloor \)

现在只需计算右侧的求和。 \( \left\lbrack \frac{156}{5}\right\rbrack + \left\lbrack \frac{156}{25}\right\rbrack + \)

\[ \left| \frac{156}{125}\right| + \left| \frac{156}{625}\right| \]

注:floor 函数即向下取整。

我们的求和结果即为 \( {31} + 6 + 1 + 0 \) ，等于 38。因此， \( {5}^{38} \) 能整除 156!。

如果我们想求能整除阶乘的非素数的最高幂，该怎么办？

要找出能整除某个阶乘的非质数的最大幂次，我们只需对该非质数进行质因数分解。然后，分别求出每个质因数能整除该阶乘的最大指数。最后，取这些指数中的最小值。然而，这里有一个陷阱:非质数也可能包含像12这样的数，而12能被2的多个幂次整除。因此，不能盲目套用这一技巧。在习题部分将给出至少有一个质因数的指数大于1的非质数的例子。

例2.3.5

求能整除180!的14的最大指数。

解:首先将14质因数分解，得到 \( 2 \cdot 7 \) 。接下来，分别求出2和7能整除180!的最大指数。我们取其中较小的一个，因为它就是“限制因素”(学过化学、了解限制反应物概念的人对此会很容易理解)。

\[ {e}_{2}\left( {{180}!}\right) = \left\lfloor \frac{180}{2}\right\rfloor + \left\lfloor \frac{180}{4}\right\rfloor + \left\lfloor \frac{180}{8}\right\rfloor + \left\lfloor \frac{180}{16}\right\rfloor + \left\lfloor \frac{180}{32}\right\rfloor + \left\lfloor \frac{180}{64}\right\rfloor + \left\lfloor \frac{180}{128}\right\rfloor + \left\lfloor \frac{180}{256}\right\rfloor . \]

该和等于 \( {90} + {45} + {22} + {11} + 5 + 2 + 1 + 0 = {176} \)

\[ {e}_{7}\left( {{180}!}\right) = \left\lfloor \frac{180}{7}\right\rfloor + \left\lfloor \frac{180}{49}\right\rfloor + \left\lfloor \frac{180}{343}\right\rfloor . \]

该和等于 \( {25} + 3 + 0 = {28} \) 。

因此，能整除180!的2的最大指数是176，而7的最大指数是28。由于我们要求的是14的最大指数，2和7的指数必须相同。若设最大指数为 \( n \) ，则 \( {14}^{n} = {2}^{n} \cdot {7}^{n} \) 。因此，为使 \( n \) 最大，我们只能选28，因为任何更大的值都无法整除180!，7将其限制在28以下。

最终答案:28

定理2.3.6

我们还知道，任意整数 \( n \) 的所有正因数的乘积为

\[ {n}^{\frac{d\left( n\right) }{2}} \]

\( d\left( n\right) \) 表示数 \( n \) 的正因数个数。

习题2.3.7——求所有正因数之和为186的正整数之和。

来源:2020 PUMAC数论

解:设该数的质因数分解为 \( {p}_{1}^{{e}_{1}} \cdot {p}_{2}^{{e}_{2}} \cdot {p}_{3}^{{e}_{3}}\ldots \)

其因数之和为 \( \left( {1 + {p}_{1} + {p}_{1}^{2}\ldots + {p}_{1}^{{e}_{1}}}\right) \left( {1 + {p}_{2} + {p}_{2}^{2}\ldots + {p}_{2}^{{e}_{2}}}\right) \left( {1 + {p}_{3} + {p}_{3}^{2}\ldots + {p}_{3}^{{e}_{3}}}\right) \ldots \)

\( {186} = 2 \cdot 3 \cdot {31} \)

现在需要列出乘积为186的数对，以确定质因数分解。2不行，因为 \( \left( {1 + {p}_{1} + {p}_{1}^{2}\ldots + {p}_{1}^{{e}_{1}}}\right) \) 不能等于2，否则 \( {p}_{1} \) 必须为1，而1不是质数。

因此，我们需要测试的数对是(6,31)和(3,62)。

\[ 6 = 1 + 5 \]

\[ {31} = 1 + 2 + 4 + 8 + {16} \]

对于这一组合，乘积为 \( 5 \cdot {2}^{4} \) ，即80。

\( 3 = 1 + 2 \)

\( {62} = 1 + {61} \)

在此情况下，我们的约数和为186的数是 \( 2 \cdot {61} \) ，即122。

于是，我们将80与122相加，得到最终答案202。

问题2.3.8——对于某个正整数 \( n \) ，数 \( {110}{n}^{3} \) 共有110个正整数约数(包括1和 \( {110}{n}^{3} \) 本身)。问:数 \( {81}{n}^{4} \) 有多少个正整数约数？

(B) 191 (C) 261 (D) 325 (E) 425

来源:2016 AMC

解答: \( {110}{n}^{3} \) 等于 \( 2 \cdot 5 \cdot {11} \cdot {n}^{3} \) 。

已知该数有110个约数。我们还知道至少有3个互不相同的质因数(因为已知2、5和11都是其约数)。

将110进行质因数分解得 \( 2 \cdot 5 \cdot {11} \) 。根据公式，求约数个数只需将各互异质因数的指数加1后相乘。

于是，我们反向推导，得到指数分别为1、4和10(由2、5、11各减1而来)。因此，可假设 \( {n}^{3} \) 为 \( {5}^{3} \cdot {11}^{9} \) 。此假设源于 \( {110}{n}^{3} \) 的质因数分解中，其互异质因数的指数应为1、4、10。

对 \( {n}^{3} \) 取立方根，得 \( n \) 等于 \( 5 \cdot {11}^{3} \) 。接下来求 \( {81}{n}^{4} \) 的约数个数。已知其等于 \( {3}^{4} \cdot {5}^{4} \cdot {11}^{12} \) 。将各指数加1得5、5、13，三者相乘得325，故选(D)。

问题2.3.9——下列数是 \( n \) 的所有约数的乘积: \( {2}^{6} \cdot {3}^{3} \)

求 \( n \) 。

来源:2015 CHMMC

解答:本题可应用公式:任意数 \( n \) 的所有约数之积为 \( {n}^{\frac{d\left( n\right) }{2}} \) ，其中 \( d\left( n\right) \) 表示约数个数。令该式等于 \( {2}^{6} \cdot {3}^{3} \) 即可。

\[ {n}^{\frac{d\left( n\right) }{2}} = {2}^{6} \cdot {3}^{3} \]

两边平方得到

\[ {n}^{d\left( n\right) } = {2}^{12} \cdot {3}^{6} \]

显然， \( n \) 的唯一素因子必须是 2 和 3(如果是其他素因子，则无法与右侧相等，因为右侧只有素因子 2 和 3)。

我们假设这里的 \( n = {2}^{a} \cdot {3}^{b}.d\left( n\right) \) 就是 \( \left( {a + 1}\right) \left( {b + 1}\right) \)

\[ {\left( {2}^{a} \cdot {3}^{b}\right) }^{\left( {a + 1}\right) \left( {b + 1}\right) } = {2}^{12} \cdot {3}^{6} \]

我们可以把 2 的指数(目前是 \( a \) )乘以 \( \left( {a + 1}\right) \left( {b + 1}\right) \) ，同样地对 3 的指数 \( b \) 也这样做。

这给出 \( {2}^{a\left( {a + 1}\right) \left( {b + 1}\right) } = {2}^{12} \)

这给出 \( {3}^{b\left( {a + 1}\right) \left( {b + 1}\right) } = {3}^{6} \)

我们可以把上面两个方程的指数对应相等，得到

\[ a\left( {a + 1}\right) \left( {b + 1}\right) = {12} \]

\[ b\left( {a + 1}\right) \left( {b + 1}\right) = 6 \]

将上面两个方程相除得到 \( \frac{a}{b} = 2 \) ，这意味着 \( a = {2b} \)

我们可以把此结果代入 \( b\left( {a + 1}\right) \left( {b + 1}\right) = 6 \) ，得到 \( b\left( {{2b} + 1}\right) \left( {b + 1}\right) = 6 \) ，而 \( b \) 显然必须为 1。这意味着 \( a \) 是 2。

既然我们已知 \( a \) 和 \( b \) 的值，就知道 \( n \) 是 \( {2}^{2} \cdot {3}^{1} \) ，即 12

问题 2.3.10:在 \( {2004}^{2004} \) 的正整数因子中，有多少个恰好能被 2004 个正整数整除？

来源:2004 AIME

解:我们首先写出 \( {2004}^{2004} \) 和 2004 的素因数分解，分别为 \( {2}^{4008} \cdot {3}^{2004} \cdot {167}^{2004} \) 和 \( {2}^{2} \cdot 3 \cdot {167} \) 。

在 \( {2004}^{2004} \) 的所有因子中，最多只能有 3 个不同的素因子(2、3、167)，如我们的素因数分解所示。

设 \( {2004}^{2004} \) 的一个因子为 \( {2}^{x} \cdot {3}^{y} \cdot {167}^{z} \) ，则它的因子个数为 \( \left( {x + 1}\right) \left( {y + 1}\right) \left( {z + 1}\right) \) 。我们令它等于 2004。

\[ \left( {x + 1}\right) \left( {y + 1}\right) \left( {z + 1}\right) = {2}^{2} \cdot 3 \cdot {167} \]

现在我们可以把每个素因子分配到数 \( x + 1, y + 1 \) 和 \( z + 1 \) 上。有两种情况:一种是 2 的两个因子都分配给其中一个数，另一种是 2 的两个因子分别分配给两个不同的数。

如果所有2的因子只整除一个数，那么有3种情况(即 \( x + 1 \) 、 \( y + 1 \) 或 \( z + 1 \) )。如果一个2的因子整除两个数，则有 \( \left( \begin{array}{l} 3 \\ 2 \end{array}\right) \) 种情况，即3种。对于质因数2，总的可能情况数为 \( 3 + 3 \) ，即6种。

现在我们拆分因子3。它只有3个去处:要么 \( x + 1 \) ，要么 \( y + 1 \) ，要么 \( z + 1 \) 。167也是如此。

我们的答案是 \( 6 \cdot 3 \cdot 3 \) ，即54。

问题2.3.11 - 设 \( n = {2}^{31}{3}^{19} \) 。有多少个 \( {n}^{2} \) 的正整数因子小于 \( n \) 但不整除 \( n \) ？

解答:1995年AIME

解答: \( {n}^{2} \) 就是 \( {2}^{62} \cdot {3}^{38} \) 。

我们注意到， \( {n}^{2} \) 的每一对因子中，一个因子小于 \( n \) ，另一个大于 \( n \) 。要验证这一点，你可以观察一些例子，并尝试几对乘积为 \( {n}^{2} \) 的因子。

然而，有一个因子没有唯一配对，即 \( n \) ，因为它与自身配对才能得到 \( {n}^{2} \) 。

因此，要找出小于 \( \mathrm{n} \) 的因子数，我们先求 \( {n}^{2} : \left( {{62} + 1}\right) \left( {{38} + 1}\right) \) 的因子总数。然后减去1以排除 \( n \) ，再除以2(因为只有一半会小于 \( n \) )，得到1228。然而，其中有些因子会整除 \( n \) (根据题意我们不想要这些)。因此，现在需要减去那些小于 \( n \) 且整除 \( n \) 的因子数。

显然， \( n \) 的所有因子都小于 \( n \) ，除了 \( n \) 本身。因此，我们求 \( n \) 的因子数并减去1。然后用1228减去该值。 \( n \) 的因子数为 \( \left( {{31} + 1}\right) \left( {{19} + 1}\right) \) ，即640。640减1得639。再用1228减去639得到 \( {1228} - {639} = \mathbf{{589}} \) 。

§2.4 阶乘与回文数

阶乘和回文数在AMC和AIME中都很常见。掌握这类问题的解题策略很重要。阶乘题通常涉及本书已出现的勒让德定理(Legendre's theorem)。解决阶乘/回文题的最佳方法就是多练习，因为相关理论并不多。

定义2.4.1

回文数是指从左到右或从右到左读都相同的数。例如，121、1441、3883、39493都是回文数，无论从左到右还是从右到左读，它们都是相同的数。

通常，解决与回文数相关的问题时，可以将其展开写出。如果未给出回文数，则可用变量表示各位数字。然后，将相同的数字配对，写出表达式。

例如，若要表示一个三位回文数，可写成aba，其中a和b为整数。 \( {aba} \) 等价于 \( a \cdot {100} + b \cdot {10} + a \cdot 1 \) ，也等价于 \( {101a} + {10b} \) 。

问题2.4.2 - 在1000到10000之间随机选取一个回文数，求它能被7整除的概率。

来源: \( {2010}\mathrm{{AMC}} \)

解答:显然这个回文数有4位，因此可表示为abba。可将其改写为 \( a \cdot {10}^{3} + b \cdot {10}^{2} + b \cdot {10}^{1} + a \cdot {10}^{0} \) ，这等价于 \( {1001a} + {110b} \) 。

接下来，我们将研究 \( a \) 和 \( b \) 这两个数，以找出该数能被7整除的概率。我们注意到 \( {1001a} \) 总能被7整除，因为1001能被7整除。因此，我们只需处理 \( {110b} \) ，它在模7下等价于 \( {5b} \) 。当 \( \mathrm{b} \) 为0或7时， \( {5b} \) 能被7整除。 \( b \) 有10种可能的数字(0到9)，其中2种满足条件，因此概率为 \( \frac{2}{10} = \frac{1}{5}\left( \mathrm{E}\right) \) 。

问题2.4.3 - 许多州采用“三个字母+三个数字”作为标准车牌格式。已知每种三字母三数字组合出现概率相同，求这种车牌至少包含一个回文(三字母或三数字从左到右与从右到左读相同)的概率为 \( \frac{m}{n} \) ，其中 \( m \) 和 \( n \) 为互质的正整数，求 \( m + n \) 。

来源:2002 AIME

解答:我们可以分别计算数字和字母出现回文的概率。对于数字，共有 \( {10}^{2} \) 个回文。这是因为三位回文可表示为aba，其中a、b为数字。第一位确定后，第三位必须与之相同。所有可能数字为 \( {10}^{3} \) ，因此概率为 \( \frac{{10}^{2}}{{10}^{3}} \) ，化简为 \( \frac{1}{10} \) 。

对于字母，共有 \( {26}^{2} \) 个回文和 \( {26}^{3} \) 种可能字符串，概率为 \( \frac{{26}^{2}}{{26}^{3}} \) ，等于 \( \frac{1}{26} \) 。

在简单相加之前，根据容斥原理(PIE)，需减去两者同时发生的概率。若你尚不熟悉此定理，请放心，后续会讲到，无需慌张。

两者同时发生的概率为 \( \frac{1}{26} \cdot \frac{1}{19} \) ，即 \( \frac{1}{260} \) 。现在计算: \( \frac{1}{26} \) \( + \frac{1}{10} - \frac{1}{260} \) ，得到 \( \frac{7}{52} \) 。将分子分母相加得 \( 7 + {52} = \mathbf{{59}} \) 。

问题2.4.4 - 回文数是指十进制下不含前导零且正反向读相同的非负整数。随机均匀选取一个6位回文数 \( n \) ，求 \( \frac{n}{11} \) 也是回文的概率。

(A) \( \frac{8}{25} \) (B) \( \frac{33}{100} \) (C) \( \frac{7}{20} \) (D) \( \frac{9}{25} \) (E) \( \frac{11}{30} \)

来源:2013 AMC

解答:解决此题最好倒推。只有将4位或5位回文数乘以11，才能得到6位回文数。

情况1:将6位回文数除以11后得到一个4位回文数，其形式为ABBA。A和B代表整数；B可以是0到9中的任意数字，而A可以是1到9中的任意数字。当我们将其乘以11时，得到的结果如下所示。

从左到右的数字依次为 \( A, A + B,{2B}, A + B, A \) ，如果没有进位的话。

然而，我们希望乘以11后得到一个6位回文数。因此，只有当 \( \mathrm{A} \) 为9且从 \( A + B \) 的求和中进位1时才可能实现。这意味着第一位数字将是1，而最后一位数字即A将直接为9。然而，由于第一位和最后一位数字不相等，这种情况是不可能的(回文数的第一位和最后一位数字必须相等)。

情况2(将6位回文数除以11后得到一个5位回文数)5位回文数的形式为ABCBA。将其乘以11，得到的结果如下所示

如果没有进位，那么从右到左的数字依次为 \( A, A + B, B + C, B + \) \( C, A + B, A \) 。我们可以立即看出这是一个6位数。最重要的是，我们不希望有任何进位，否则它将不再是回文数。你可以代入一些数字来观察这一点。

我们现在将进行一些情况分析。数字A必须至少为1。

上图展示了当数字A为1时的分类示例。其可能情况的数量即为从2到10(含)所有整数之和，共54种。

我们可以将此模式一直延伸至 \( A = 9 \) ，并发现可能性数量为 \( {54} + {52} + {49} + {45} + {40} + {34} + {27} + {19} + {10} = {330} \) 。总情况数即为形如ABCBA的五位回文数数量。数字 \( \mathrm{A}\left( {1 - 9}\right) \) 有9种选择， \( \mathrm{B} \) 和 \( \mathrm{C}\left( {0 - 9}\right) \) 各有10种选择，总数为 \( 9 \cdot {10} \cdot {10} \) ，即900。最终答案为 \( \frac{330}{900} \) ，化简后为 \( \frac{11}{30} \) 。

问题2.4.5 - 求随机选取20!的一个正因数时，该因数是2000的倍数的概率。

来源:2020 SMT

解答:我们将使用勒让德定理(Legendre's theorem)先对20!进行质因数分解。需处理小于20的质数:2,3,5,7,11,13,17和19。

\[ {20}! = {2}^{18} \cdot {3}^{8} \cdot {5}^{4} \cdot {7}^{2} \cdot {11} \cdot {13} \cdot {17} \cdot {19} \]

接着对2000进行质因数分解，得到 \( {2}^{4} \cdot {5}^{3} \)

任何2000的倍数必须满足:2的指数至少为4，5的指数至少为3。

需找出20!中满足此条件的因数数量。即2的指数可从4取到18(19种可能中的15种)，5的指数可从3取到4(5种可能中的2种)。

可将此概率表示为 \( \frac{15}{19} \cdot \frac{2}{5} \) ，计算得 \( \frac{6}{19} \)

问题2.4.6 — 已知

\( \frac{\left( {\left( {3!}\right) !}\right) !}{3!} = k \cdot n! \)

其中 \( k \) 和 \( n \) 为正整数，且 \( n \) 尽可能大，求 \( k + n \) 。

来源:2003 AIME

解答:首先计算等式左侧。3!为6，6!为720，剩余部分为 \( \frac{{720}!}{3!} \) 。

为使 \( n \) 最大化，需找出能整除表达式 \( \frac{{720}!}{3!} \) 的最大阶乘。可将 \( \frac{{720}!}{3!} \) 化简为 \( \frac{{720} \times {719}!}{3!} \) ，得到 \( {120} \cdot {719}! \) 。此即所需答案形式，且n无法大于719。因此答案为 \( {719} + {120} \) ，即839。

问题2.4.7 - 有多少个小于等于240的正整数可表示为互不相同的阶乘之和？注意0!与1!视为不同。来源:2020 HMMT

解答:小于240的阶乘有 \( 0!,1!,2!,3!,4! \) 和5!。若尝试累加0!、1!或2!，会发现部分和重复(如0!+1!等于2!)。但3!、4!或5!无此问题。

因此，3个阶乘中的每一个都可以出现或不出现于我们的求和中，这意味着每个都有2种情况(出现或不出现)。 \( 2 \cdot 2 \cdot 2 \) 就是8。

现在我们来处理 \( 0!,1! \) 和 \( 2! \) 。这3个数等价于1、1和2。我们可以全部排除，得到0；也可以把它们的各种组合相加，得到从1到4的所有整数。因此，共有5种可能的值。我们将5乘以8得到40。

然而，我们必须减去3!、4!和5!都不出现的情况，因为那样会得到数字0，而0不是正数。因此，答案是 \( {40} - 1 \) ，即39。

问题2.4.8 设 \( N \) 为乘积 \( 1!2!3!4!\cdots {99}!{100}! \) 的十进制表示右端连续0的个数。求 \( N \) 除以1000的余数。

来源:2006 AIME

解答:为了求连续0的个数，我们需要知道10能整除该数多少次。根据勒让德定理(Legendre's theorem)，我们只需把要计算最高幂次的整数分解为质因数。在此，我们把10分解为2和5。显然2的个数远多于5。因此，我们只需计算5的个数。我们将遍历所有数，用5去除并向下取整。

\[ {e}_{5}\left( {n!}\right) = \mathop{\sum }\limits_{{n = 1}}^{{100}}\left\lfloor \frac{n}{5}\right\rfloor \]

我们可以通过观察规律来求解上述表达式。前4个数1到4直接给出0。然而，当 \( n = 5 \) 到9时，我们得到1。当 \( n \) 取10到14之间的值时，我们得到2，以此类推。

从1到19，同样的值会重复5次。对于值 \( \mathrm{n} = {100} \) ，我们在求和中得到20。因此，我们只需用前 \( n \) 项求和公式求1到19的和，得到 \( \frac{{19} \cdot {20}}{2} \) ，即190。乘以5得950。现在，我们再加上来自 \( n = {100} \) 的20，得到970。

然而，还有更多的5的因子。每当25整除某个阶乘时，我们会再得到一个5的因子。因此，我们将重复这一过程，但把5换成25。 \( {e}_{25}\left( {n!}\right) = \mathop{\sum }\limits_{{n = 1}}^{{100}}\left\lfloor \frac{n}{25}\right\rfloor \)

我们再次发现规律。当 \( n \) 在0到24之间时，我们得到0。当 \( \mathrm{n} \) 在25到49之间时，每个数贡献1个25的因子。当 \( \mathrm{n} \) 在50到74之间时，每个数贡献2个25的因子。当 \( n \) 在75到99之间时，每个数贡献3个25的因子。当 \( \mathrm{n} \) 为100时，我们得到4个25的因子。我们计算得 \( \left( {{24} \cdot 0}\right) + \left( {{25} \cdot 1}\right) + \left( {{25} \cdot 2}\right) + \left( {{25} \cdot 3}\right) + \left( {1 \cdot 4}\right) \) ，即154。将970与154相加，得到该数共有1124个0。将其除以1000，最终答案为124。

§2.5 不同进制的数

问题2.5.1 设 \( n \) 为正整数， \( d \) 为数字，使得在 \( n \) 进制下数字 \( {32d} \) 的值为263，且 \( n \) 进制下的数字324等于六进制下数字 \( \underline{11}{d1} \) 的值。求 \( n + d \) 。

来源:2021 AMC

解法:为解此题，可将不同进制的数改写为代数式，并统一转换为十进制。 \( {32}{d}_{n} \) 在十进制下为 \( 3{n}^{2} + {2n} + d \) ，其值等于 263。接着将 \( {324}_{n} \) 转换为十进制，并令其等于十进制下的 \( {11d}{1}_{6} \) ，即 \( {253} + {6d} \) 。我们得到以下两个方程。

• \( 3{n}^{2} + {2n} + d = {263} \)

\[ \text{2.}3{n}^{2} + {2n} + 4 = {253} + {6d} \]

由此，可将第一个方程改写为 \( 3{n}^{2} + {2n} = {263} - d \) 。然后将其代入第二个方程，得到

\( {253} + {6d} + 4 = {253} - {6d} \)

解 \( d \) 得 \( d = 2 \) 。再将其代回第一个方程，解二次方程得 \( n = 9 \) 。因此答案即为 \( 2 + 9 \) ，也就是 \( \mathbf{{11}}\left( \mathbf{B}\right) \) 。

下一题再次说明，这类问题大多只需将不同进制的数转换为十进制即可。

问题 2.5.2 —— 数 \( {N}_{b} \) 在 \( b \) 进制下写作 123。求最小的 \( b \) ，使得 \( {N}_{b} \) 是一个正整数的立方。来源:2019 SMT

解法:本题中，我们将 \( {123}_{b} \) 转换为十进制。

我们得到 \( 1 \cdot {b}^{2} + 2 \cdot b + 3 = {b}^{2} + {2b} + 3 \) 。

进制必须至少为 4，因为该数中最大的数字是 3。

将 4 代入 \( b \) 进行验证，得到 27。由于 27 是 3 的立方，因此进制 \( b \) 为 4。

问题 2.5.3 一个有理数在八进制下写作 \( \underline{ab}.\underline{cd} \) ，所有数字均不为零；同一数在十二进制下写作 \( \underline{bb}.\underline{ba} \) 。求该数的十进制值 \( \underline{abc} \) 。

来源:2017 AIME

解法:注意到要使两数相等，整数部分必须相等，小数部分也必须相等。 \( a{b}_{8} \) 必须等于 \( b{b}_{12} \) 。同样，不同进制下的小数部分也必须相等。从小数点左侧第一位和第二位入手，我们得到

\[ {8}^{1} \cdot a + {8}^{0} \cdot b = {12}^{1} \cdot b + {12}^{0} \cdot b \]

这等价于 \( {8a} + b = {12b} + b \) ，化简得 \( {2a} = {3b} \) 。接下来分情况讨论，求出 \( a \) 、 \( b.a \) 和 \( b \) 的可能值，且它们必须严格小于 8，因为八进制数的所有数字必须小于 8( \( {ab} \) 为题中给出的八进制数)。因此可能的 (a, b) 组合为 (3,2) 和 (6,4)。我们将分别讨论这两种情况。

情况 1: \( \left( {a, b}\right) = \left( {3,2}\right) \)

我们只需验证小数部分是否相等，因为整数部分已满足条件。将 \( {ab}.{cd} \) 从八进制转换为十进制的小数部分为 \( \frac{c}{8} + \frac{d}{64} \) 。

将其与十二进制的小数部分相等，得到最终方程 \( \frac{c}{8} + \frac{d}{64} = \frac{b}{12} + \frac{a}{144} \) 。代入 \( b \) 为 2， \( a \) 为 3，化简得 \( {8c} + d = {12} \) 。

由此，唯一可能的解集 \( \operatorname{for}\left( {c, d}\right) = \left( {1,4}\right) \) 。因此，我们的 \( {abc} \) 值为321。

显然，此题只有一个可能的答案，即321；不过，我们仍看看另一解集是否可能。

情况2: \( \left( {a, b}\right) = \left( {6,4}\right) \)

我们只需检查小数部分。可将两个小数部分转换，得到方程

\( \frac{c}{8} + \frac{d}{64} = \frac{b}{12} + \frac{a}{144} \) 。代入a=6、b=4并化简，得

\( c + {8d} = {24} \) 。然而，由于 \( \mathrm{c} \) 和 \( \mathrm{d} \) 必须非零，此式无解。这意味着 \( d \) 只能取1或2。在这两种情况下， \( c \) 分别为16和8，而这是不可能的，因为 \( c \) 是八进制数的一部分，其数字必须≤7。

因此，最终答案为321。

问题2.5.4——十六进制(base-16)数使用数字0到9以及字母 \( A \) 到 \( F \) 表示10到15。在前1000个正整数中，有 \( n \) 个的十六进制表示仅含数字。求 \( n \) 的各位数字之和。

\( \textbf{(A) }{17}\;\textbf{(B) }{18}\;\textbf{(C) }{19}\;\textbf{(D) }{20}\;\textbf{(E) }{21}\; \)

来源:2015 AMC

解:先将1000转换为十六进制，得 \( 3 \cdot {16}^{2} + {14} \cdot {16}^{1} + 8 \) 。

十六进制的14对应E。由于我们要求十六进制表示中仅含数字(即不含10到15)，首位有4种可能值 \( 0 - 3 \) 。同理，其余两位各有10种可能(0到9)，且仍小于1000。因此，可能性为 \( 4 \cdot {10} \cdot {10} \) ，即400。然而，我们只考虑正整数，需减去全为0的情况。故最终答案为399，其各位数字之和为 \( \mathbf{{21}}\left( \mathbf{E}\right) \) 。

注:若需对不同进制的两数进行加减乘除，可先将所有数转换为十进制。

问题2.5.5——正整数 \( N \) 的十一进制表示为 \( \underline{a}\underline{b}\underline{c} \) ，八进制表示为 \( \underline{1}\underline{b}\underline{c}\underline{a} \) ，其中 \( a, b \) 和 \( c \) 为(未必相异)数字。求满足条件的最小 \( N \) (用十进制表示)。

来源:2020 AIME

解:将这两个分别用十一进制和八进制表示的整数转换为十进制，然后令它们相等，因为它们都等于 \( N \) 。

将 \( {abc} \) 从十一进制转为十进制，即 \( {11}^{2} \cdot a + {11} \cdot b + c = {121a} + {11b} + c \)

\( {1bca} \) 从八进制转换为十进制是 \( {8}^{3} \cdot 1 + {8}^{2} \cdot b + 8 \cdot c + a = {512} + {64b} + {8c} + a \) 。

现在我们知道了 \( {121a} + {11b} + c = {512} + {64b} + {8c} + a \)

重新排列各项得到 \( {120a} = {512} + {53b} + {7c} \)

现在我们可以利用“对于任意一个以 \( b \) 为基数的数，其所有数字必须在 0 到 \( b - 1 \) (含)之间”这一思想。由于 \( a, b, c \) 同时属于八进制和十一进制的两个数，这三个变量必须在 0 到 7(含)之间。

由于我们希望左侧(即 \( {120a} \) )等于右侧， \( a \) 的值不能为 4(因为右侧出现了 512)。它至少应为 5。假设它为 5，我们得到 \( {600} = {512} + {53b} + {7c} \) ，化简后为 \( {88} = {53b} + {7c} \)

从这里我们注意到，如果 \( b = 1 \) ，则 \( c = 5 \) 。由于 \( a = 4, b = 1, c = 5 \) 且所有这些数字都是 \( \leq 7 \) ，我们已找到解集。

我们可以把这些数字代入八进制或十一进制数，求得 \( \mathrm{N} \) 的值为 621。

问题 2.5.6——求小于 1000(十进制)且同时在十进制和五进制下均为回文数的前三大数之和(以十进制表示)。

来源:2020 PUMAC

解法:本题中，我们先将 1000 转换为五进制，得到 \( {13000}_{5} \) 。

我们知道这些数在五进制下的最大位数为 5。我们可以按五进制位数进行分情况讨论。

情况 1:五进制数有 5 位

显然，首位必须为 1，否则将超过 \( {13000}_{5} \)

我们的数为 \( {1aba1} = {626} + {130a} + {25b} \)

数字 \( a \) 必须为 0、1 或 2，因为若为 3，则该数将大于 \( {13000}_{5} \) 。

子情况 1.1: \( a \) 为 2，得到 \( {626} + {260} + {25b} \) ，即 \( {886} + {25b} \) 。

在这种情况下，将不存在任何在十进制下为回文数的数字。

子情况1.2: \( a \) 为1。这给出 \( {626} + {130} + {25b} \) 即 \( {756} + {25b} \) ，而在此情况下将没有任何有效的结果。

子情况 \( {1.3} : a \) 为0。这给出 \( {626} + {25b} \) 。然而在此情况下， \( b \) 可以是1或0，我们将得到626和656这两个可能的值。

情况2:我们的五进制数有4位。

我们的数为 \( {abba} \) 。将其在五进制下展开得到 \( {5}^{3} \cdot a + {5}^{2} \cdot b + {5}^{1} \cdot b + {5}^{0} \cdot a \) ，进而得到 \( {126a} + {30b} \) 。

由于我们知道 \( a \) 和 \( b \) 不能大于4，让我们假设 \( a \) 为4以使该数最大化。然而，我们发现此时无法形成任何回文数。类似地，对于 \( a = 3 \) ，也将不存在可能的回文数。然而，对于 \( a = 2 \) ，我们得到 \( {252} + {30b} \) 。252是一个回文数，但若我们将 \( b \) 替换为1，则得到一个更大的回文数282。

我们的3个回文数是 \( {282} + {626} + {656} \) ，即1584。

§2.6 处理个位数

许多AMC和AIME题目都要求你观察个位数。通常，个位数会以循环方式重复。掌握这类题目的唯一途径就是练习，其中并没有太多理论可言。

问题2.6.1—— \( {13}^{2003} \) 的个位数是多少？

(A)1(B)3(C)7(D)8(E)9

来源:2003年AMC 10

解答:对于本题，我们只需找出一个模式，以确定当13的指数为2003时，其个位数是多少。

13的若干次幂的个位数

\( {13}^{1} = 3 \)

\( {13}^{2} = 9 \)

\( {13}^{3} = 7 \)

\( {13}^{4} = 1 \)

\( {13}^{5} = 3 \)

\( {13}^{6} = 9 \)

\( {13}^{7} = 7 \)

\( {13}^{8} = 1 \)

显然，个位数以4为周期循环，重复模式为3,9,7,1。我们注意到，当指数除以4的余数分别为1,2,3,0时，个位数依次为3,9,7,1。由于2003除以4的余数为3，因此最终个位数为 \( \mathbf{7\left( C\right) } \) 。

问题2.6.2——对于正整数 \( n \) ，令 \( {d}_{n} \) 为 \( 1 + 2 + \cdots + n \) 的个位数。求以下式子除以某数的余数:

\[ \mathop{\sum }\limits_{{n = 1}}^{{2017}}{d}_{n} \]

除以1000。

来源:2017 AIME

解答:这是另一道需要寻找规律的题目。我们需要求出2017次求和后的个位数。我们将通过计算 \( {d}_{n} \) 的值的个位数来寻找规律。

\( {d}_{n} = \mathop{\sum }\limits_{{i = 1}}^{n}i \)

\[ {d}_{1} = \mathop{\sum }\limits_{{i = 1}}^{1}i = 1 \]

\[ {d}_{2} = \mathop{\sum }\limits_{{i = 1}}^{2}i = 3 \]

\[ {d}_{3} = \mathop{\sum }\limits_{{i = 1}}^{3}i = 6 \]

\[ {d}_{4} = \mathop{\sum }\limits_{{i = 1}}^{4}i = 0 \]

\[ {d}_{5} = \mathop{\sum }\limits_{{i = 1}}^{5}i = 5 \]

\[ {d}_{6} = \mathop{\sum }\limits_{{i = 1}}^{6}i = 1 \]

\[ {d}_{7} = \mathop{\sum }\limits_{{i = 1}}^{7}i = 8 \]

\[ {d}_{8} = \mathop{\sum }\limits_{{i = 1}}^{8}i = 6 \]

如果我们继续这一模式，就会得到一个周期为20的模式。数字在该模式中交替出现。

\[ 1,3,6,0,5,1,8,6,5,5,6,8,1,5,0,6,3,1,0,0, \]

这一循环的和为70。我们计算该循环完整重复了多少次。 \( \left\lfloor \frac{2017}{20}\right\rfloor = {100} \)

然而，在最后17次中不会形成完整循环，因此我们将逐个相加这些项以求得总和。 \( {100} \cdot {70} = {7000} + {69} \) 。总和为7069，将其除以1000后得到69。

§2.7 模运算(Modular Arithmetic)简介

人们有时会被“mod”这个词搞糊涂，现在是澄清的时候了。当你说8能被4整除时，你可以简单地说 \( 8 \equiv 0\left( {\;\operatorname{mod}\;4}\right) \) 。这仅仅意味着当8被4整除时，余数为0。例如，4、8、12、16、20、24在模4下都是0。这意味着当你把这些数都除以4时，得到的余数总是0。

\( \equiv \) 是模运算中使用的符号。它仅表示两个数同余(即被某个特定数除时余数相同)。

模运算性质

定理4.6。若 \( a, b, c, d \) 、 \( m \) 为整数且满足 \( m > 0, a \equiv b\left( {\;\operatorname{mod}\;m}\right) \) ，且

\( c \equiv d\left( {\;\operatorname{mod}\;m}\right) \) ，则

(i) \( a + c \equiv b + d\left( {\;\operatorname{mod}\;m}\right) \) ,

(ii) \( a - c \equiv b - d\left( {\;\operatorname{mod}\;m}\right) \) ，

(iii) \( {ac} \equiv {bd}\left( {\;\operatorname{mod}\;m}\right) \) 。

现在，在进入费马小定理(Fermat's Little Theorem)和欧拉φ定理(Euler's Totient Theorem)等更复杂的主题之前，我们先解决一些问题。

问题2.7.1——数 \( N \) 的九进制(base-nine)表示为 \( {27},{006},{000},{052}{}_{\text{nine }} \) 。当 \( N \) 被5除时，余数是多少？

(A) 0 (B) 1 (C) 2 (D) 3 (E) 4

来源:2021 AMC 12

解法:我们需要通过之前讨论的方法将该九进制数转换为十进制来解决此问题。下面我们将重写该数。

\[ 2 \cdot {9}^{10} + 7 \cdot {9}^{9} + 6 \cdot {9}^{6} + 5 \cdot {9}^{1} + 2 \cdot {9}^{0} \]

现在，我们将这个数对5取模(mod 5)，也就是求它除以5的余数。因为9 mod 5 就是-1，我们可以轻松地在模5下求出表达式的值。把-1代入9的位置并计算，得到 \( 2 - 7 + 6 - 5 + 2 \) ，其值为-2。由于-2不是直接的余数，我们只需给它加上5，得到 \( 3\left( D\right) \) 。

问题2.7.2 - 求 \( 9 \times {99} \times {999} \times \cdots \times \underset{{999}\text{ g’s }}{\underbrace{{99}\cdots 9}} \) 除以1000的余数。来源:2010 AIME

解答:本题中，我们尝试将各数对1000取模。9和99保持不变。然而，我们发现，无论除以999、9999还是更多类似数字，它们对1000的余数都是-1。

我们只需计算 \( 9 \cdot {99} \cdot - {1}^{997} \) ，结果为-891。只需加上1000，得到109。

问题2.7.3 - 正整数 \( a, b \) 和 \( c \) 从集合 \( \{ 1,2,3,\ldots ,{2010}\} \) 中有放回地随机独立选取。求 \( {abc} + {ab} + a \) 能被3整除的概率。

(A) \( \frac{1}{3} \) (B) \( \frac{29}{81} \) (C) \( \frac{31}{81} \) (D) \( \frac{11}{27} \) (E) \( \frac{13}{27} \)

来源:2010 AMC

解答: \( {abc} + {ab} + a \) 等价于 \( a\left( {{bc} + b + 1}\right) \) 。要么 \( a \) 能被3整除，要么 \( {bc} + b + 1 \) 能被3整除，或两者皆可。

若 \( a \) 能被3整除，则 \( b \) 和 \( c \) 可任意取值。这种情况发生的概率为 \( \frac{1}{3} \) (因为 \( \frac{1}{3} \) 是1到2010集合中能被3整除的数所占比例)。

现在考虑 \( a \) 不能被3整除的情况。此时 \( b \) 和 \( c \) 不能取所有值，因此需考虑 \( {bc} + b + 1 \) 能被3整除的情形。我们不必逐一检验大数，只需检查每个数模3的余数0、1、2即可。

若 \( b \) ≡ 0 (mod 3)，将其代入 \( {bc} + b + 1 \) 可求余数。 \( 0 \cdot c + 0 + 1 \) 恒为1 (mod 3)，故该情况不可能。

再检查 \( \mathrm{b} \) ≡ 1 (mod 3)。将其代入 \( {bc} + b + 1 \) 得 \( c + 2 \) 。当 \( c \) ≡ 1 (mod 3)时，该式可被3整除。因此，当 \( b \) ≡ 1 (mod 3)且 \( c \) ≡ 1 (mod 3)时，表达式可被3整除。

最后检查 \( \mathrm{b} \) ≡ 2 (mod 3)。将2代入 \( \mathrm{b} \) 得 \( {2c} + 3 \) ，化简为 \( {2c}{\;\operatorname{mod}\;3} \) 。仅当 \( \mathrm{c} \) ≡ 0 (mod 3)时，该式可被3整除。

由于在该子情形下 \( a \) 不能被3整除，因此发生这种情况的概率为 \( \frac{2}{3} \) 。对于每一个有效的子情形，满足 \( b \) 条件的概率为 \( \frac{1}{3} \) ，且同样的概率也适用于 \( c \) 。将满足 \( a, b \) 和 \( c \) 条件的概率相乘，得到 \( \frac{2}{27} \) 。由于有2个子情形有效，我们需要将此数乘以2，于是得到 \( \frac{4}{27} \) 。

现在我们将 \( \frac{1}{3} \) 与 \( \frac{4}{27} \) 相加，得到 \( \frac{13}{27} \) (E)。

§2.8 费马小定理(Fermat's Little Theorem)与欧拉函数(Euler's Totient Function)

这是AMC(美国数学竞赛)和AIME(美国数学邀请赛)中最重要且最常见的主题之一。

下面这个简单的例子将教你欧拉φ函数(Euler's Totient Function)。

示例 2.8.1

有多少个数与48互质？

解:互质(relatively prime)指的是48与比它小的那些数的最大公约数(GCD)仅为1。这可以通过该函数完成。如果你不了解这个函数，你很可能会通过列举1、5、7等数来逐一计数，这将耗费大量时间。然而，该函数只需我们求出48的质因数分解即可。48的质因数分解。

我们知道，质因数分解(prime factorization)仅仅是 \( {2}^{4} \cdot 3 \) 。该定理指出，我们取能整除某个数的每个质数的倒数，然后用1减去该倒数。

如果我们严格按照这些步骤操作，就会得到 \( 1 - \frac{1}{2} = \frac{1}{2} \) 和 \( 1 - \frac{1}{3} = \frac{2}{3} \) 。现在我们得到两个分数: \( \frac{1}{2} \) 和 \( \frac{2}{3} \) 。我们将这两个分数与48相乘，从而求出与48互质的数的个数。将48分别乘以 \( \frac{1}{2} \) 和 \( \frac{2}{3} \) 后，得到16，这正是我们的答案。

下面有一张关于该定理的图片，不过即使你看不懂那些符号也没关系，我们正是为此才准备了这份手打说明。用欧拉φ函数(Euler’s totient function)求某个数所得值的符号是 \( \phi \) 。例如，48的 \( \phi \) 是16。

我已将公式及其原始术语附在下面，但即使你无法理解，也无需担心，因为我们刚刚已经为你解释过了。

\[ \begin{matrix} {\varphi (n)} & = & {\varphi ({p}_{1}^{{k}_{1}})\;\varphi ({p}_{2}^{{k}_{2}})\cdots \varphi ({p}_{r}^{{k}_{r}})} \end{matrix} \]

\[ \begin{matrix} & = & {{p}_{1}^{{k}_{1} - 1}({p}_{1} - 1)\;{p}_{2}^{{k}_{2} - 1}({p}_{2} - 1)\cdots {p}_{r}^{{k}_{r} - 1}({p}_{r} - 1)} \end{matrix} \]

\[ \begin{matrix} & = & {{p}_{1}^{{k}_{1}}\left( {1 - \frac{1}{{p}_{1}}}\right) {p}_{2}^{{k}_{2}}\left( {1 - \frac{1}{{p}_{2}}}\right) \cdots {p}_{r}^{{k}_{r}}\left( {1 - \frac{1}{{p}_{r}}}\right) } \end{matrix} \]

\[ \begin{matrix} & = & {{p}_{1}^{{k}_{1}}{p}_{2}^{{k}_{2}}\cdots {p}_{r}^{{k}_{r}}\left( {1 - \frac{1}{{p}_{1}}}\right) \left( {1 - \frac{1}{{p}_{2}}}\right) \cdots \left( {1 - \frac{1}{{p}_{r}}}\right) } \end{matrix} \]

\[ \begin{matrix} & = & {n\left( {1 - \frac{1}{{p}_{1}}}\right) \left( {1 - \frac{1}{{p}_{2}}}\right) \cdots \left( {1 - \frac{1}{{p}_{r}}}\right) \;.} \end{matrix} \]

我们可以在关键模算术问题中使用欧拉函数(Euler's Totient Function)。

定理 2.8.2

欧拉函数(Euler's Totient Function):若整数a与 \( n \) 互素，则 \( {a}^{\phi \left( n\right) } \equiv 1\left( {\;\operatorname{mod}\;n}\right) \) 成立

费马小定理(Fermat's Little Theorem)与之类似，在数论问题中被广泛使用。

定理 2.8.3

费马小定理(Fermat's Little Theorem):若存在整数 a，且 p 为素数，且 a 不能被 \( p \) 整除，则 \( {a}^{p - 1} \equiv 1\left( {\;\operatorname{mod}\;p}\right) \) 。

巩固对这两个定理理解的最佳方法是做几道练习题。

问题 2.8.4 — 求最大的正整数 \( \mathrm{n} \) ，使得 \( \mathrm{n}\phi \left( n\right) \) 为完全平方数。( \( \phi \left( n\right) \) 表示与 \( n \) 互质的整数 \( k,1 \leq k \leq n \) 的个数)来源:2010 PUMAC

解答:本题中，我们将重写表达式 \( \mathrm{n}\phi \left( n\right) \) 。我们将 \( \mathrm{n} \) 写成其素因数分解的乘积。假设存在一个素因子 \( {p}_{1} \) ，其指数为 \( {e}_{1} \) 。则该素因子的 \( \phi \left( n\right) \) 就是 \( {p}_{1}^{{e}_{1}} \cdot \left( {1 - \frac{1}{{p}_{1}}}\right) \) 。

上述相乘的表达式得到 \( \left( {{p}_{1}^{{e}_{1} - 1} \cdot \left( {{p}_{1} - 1}\right) }\right. \) 。我们将它与值 \( {p}_{1}^{{e}_{1}} \) 相乘得到 \( {p}_{1}^{2{e}_{1} - 1} \cdot \left( {{p}_{1} - 1}\right) \) 。

\( \mathop{\prod }\limits_{{i = 1}}^{x}{p}_{i}^{2{e}_{i} - 1} \cdot \left( {{p}_{i} - 1}\right) \) 是表达式 \( \mathrm{n}\phi \left( n\right) .{p}_{1},{p}_{2},{p}_{3},\ldots {p}_{x} \) 的值，表示 \( n \) 的 \( x \) 个素因子。

由上述表达式可见，最大的素因子指数始终为奇数，原因是 \( 2{e}_{1} - 1 \) 总是奇数。因此，该表达式永远不可能成为完全平方数。

然而，显然 \( \mathbf{n} = 1 \) 是一个可行的答案。

问题 2.8.5 — 在区间 \( 1 \leq N \leq {2020} \) 中随机选取整数 \( N \) 。求 \( {N}^{16} \) 除以 5 余 1 的概率是多少？

(A) \( \frac{1}{5} \) (B) \( \frac{2}{5} \) (C) \( \frac{3}{5} \) (D) \( \frac{4}{5} \) (E) 1

来源:2017 AMC 10

解答:利用费马小定理(Fermat’s Little Theorem)，我们知道当 \( N \) 与 5 互质(即 \( N{\;\operatorname{mod}\;5} \) 不为 0)时， \( {N}^{4}\left( {\;\operatorname{mod}\;}\right) 5 \) 恒为 1。若将 \( {N}^{4} \) 四次方，则得到 \( {N}^{16} \equiv 1 \) ( ) mod 5。这正是我们所需，且只要 \( \mathrm{N} \) 不为 0 mod 5 就成立。因此 \( N \) 必须 ≡1,2,3 或 4 mod 5，概率为 \( \frac{4}{5} \) 。

§2.9 中国剩余定理(Chinese Remainder Theorem)

中国剩余定理(Chinese Remainder Theorem)可用于求解多个线性同余方程并合并模数。

中国剩余定理(Chinese Remainder Theorem)

• 以下方程组的解:

\( \mathrm{x} = {\mathrm{a}}_{1}{\;\operatorname{mod}\;{\mathrm{n}}_{1}} \)

\( \mathrm{x} = {\mathrm{a}}_{2}{\;\operatorname{mod}\;{\mathrm{n}}_{2}} \)

\( \mathrm{x} = {\mathrm{a}}_{\mathrm{k}}{\;\operatorname{mod}\;{\mathrm{n}}_{\mathrm{k}}} \)

其中 \( {n}_{1},{n}_{2},\ldots ,{n}_{k} \) 两两互素(relatively prime)时，解法如下:

\( \mathrm{N} = {\mathrm{n}}_{1}{\mathrm{n}}_{2}\ldots {\mathrm{n}}_{\mathrm{k}} \)

\( {\mathrm{N}}_{\mathrm{i}} = \mathrm{N}/{\mathrm{n}}_{\mathrm{i}} \)

求 \( {s}_{i} \) 使得 \( {r}_{i}{n}_{i} + {s}_{i}{N}_{i} = 1 \)

令 \( {\mathrm{e}}_{\mathrm{i}} = {\mathrm{s}}_{\mathrm{i}}{\mathrm{N}}_{\mathrm{i}} \) ，则

\( \mathrm{x} = {\sum }^{\mathrm{k}}{}_{\mathrm{i}}{\mathrm{a}}_{\mathrm{i}}{\mathrm{e}}_{\mathrm{i}}{\;\operatorname{mod}\;\mathrm{N}} \)

上图可能让人一头雾水，全是变量，是时候把它理清了。中国剩余定理(Chinese Remainder Theorem)解决的是一组线性同余式。下面的例子会把它讲清楚。

\( \mathrm{x} \equiv 1\left( {\;\operatorname{mod}\;5}\right) \)

\( \mathrm{x} \equiv 2\left( {\;\operatorname{mod}\;6}\right) \)

\( \mathrm{x} \equiv 3\left( {\;\operatorname{mod}\;7}\right) \)

首先，画一张表。如果你有 3 个线性同余式，就画一个 3×3 的表格。始终需要 3 列，而行数与表达式数量相同。第一行对应第一个表达式，第二行对应第二个，第三行对应第三个。在中间列，把除当前表达式所用除数外的所有除数相乘。例如，第一个表达式我只乘 6 和 7，而排除 5。其余两步同理。最左列按顺序写下你想要的余数，记住顺序最重要。下一步，直接用顶部的线性式，把变量依次乘以中间列的值。

中间列的值。

\( {42x} \equiv 1\left( {\;\operatorname{mod}\;5}\right) \)

\( {35x} \equiv 2\left( {\;\operatorname{mod}\;6}\right) \)

\( {30x} \equiv 3\left( {\;\operatorname{mod}\;7}\right) \)

现在我们知道，在模 5 意义下 \( {42x} \) 与 \( {2x} \) 相同，因为 40 是 5 的倍数。对所有表达式都这样做。

\( {2x} \equiv 1\left( {\;\operatorname{mod}\;5}\right) \)

\( {5x} \equiv 2\left( {\;\operatorname{mod}\;6}\right) \)

\( {2x} \equiv 3\left( {\;\operatorname{mod}\;7}\right) \)

接下来我们逐个解出每个 \( \mathrm{x} \) 项，并填入最右列。我们要找使 \( 2\mathrm{x} \equiv 1\left( {\;\operatorname{mod}\;5}\right) \) 成立的 \( \mathrm{x} \) 值，这可以通过简单试算完成。完成后，我们得到 \( \mathrm{x} \) 的值就是 3。对所有方程重复此过程，得到 3、5 和 4。

\[ 1\;6 \times 7 = {42}\;3 \]

\[ 2\;5 \times 7 = {35}\;5 \]

\[ 3\;5 \times 6 = {30}\;4 \]

最后一步，把每一行的项相乘。完成后，我们得到 \( 1 \times {42} \times 3 \) 、 \( 2 \times {35} \times 5 \) 和 \( 3 \times {30} \times 4 \) 。

然后，把这些项全部相加得到答案。相加后，我们得到 \( {126} + {350} + {360} = {836}. \)

定义 2.9.1

使用中国剩余定理时，把大除数拆成较小的除数，但要确保这些小除数两两互素。例如，要判断一个数能否被 72 整除，可以分别用 8 和 9 来处理。

中国剩余定理在 AIME 中经常出现，但在 AMC 中并不常见。最重要的思想已在上面提到:把除数拆成较小的数。很多时候，你会遇到模 10、100、1000 的情况，可分别拆成 2 和 5、4 和 25、8 和 125。

问题 2.9.2 - 设 \( N = {123456789101112}\ldots {4344} \) 是由 1 到 44 依次连接而成的 79 位数。求 \( N \) 除以 45 的余数。

\( \textbf{(A)}1\;\textbf{(B)}4\;\textbf{(C)}9\;\textbf{(D)}{18}\;\textbf{(E)}{44} \)

来源:2017 AMC

解:在此题中，我们可以使用中国剩余定理(Chinese Remainder Theorem)。将45拆分为两个不同的除数5和9，并分别处理。若 \( \mathrm{N} \) 能被45整除，则它也必须同时能被5和9整除。

直接尝试用9去除一个79位数非常困难。然而，我们可以利用整除规则。我们知道，任何数的各位数字之和对9取模的结果，与该数本身对9取模的结果相同。

\( \mathrm{N} \equiv \mathrm{N}\left( {\;\operatorname{mod}\;9}\right) \) 的各位数字之和

各位数字之和即为1到44这些数的总和，也就是 \( \frac{{44} \cdot {45}}{2} \) 。其值为990，而990对9取模为0，这意味着 \( N \) 也必须如此。

\[ \mathrm{N} \equiv 0{\;\operatorname{mod}\;9} \]

要观察除以5的余数，只需看末位数字，并将其对5取模即可。在此情况下，末位数字除以5的余数恰好为4。

\( \mathrm{N} \equiv 4{\;\operatorname{mod}\;5} \)

\( \mathrm{N} \equiv 0{\;\operatorname{mod}\;9} \)

现在利用中国剩余定理，我们得到余数为9(C)。

问题2.9.3——已知对所有正整数 \( k,{1}^{2} + {2}^{2} + {3}^{2} + \ldots + {k}^{2} = \) ， \( \frac{k\left( {k + 1}\right) \left( {{2k} + 1}\right) }{6} \) 。求最小的正整数 \( k \) ，使得 \( {1}^{2} + {2}^{2} + {3}^{2} + \ldots + {k}^{2} \) 是200的倍数。

来源:2002 AIME

解:在此题中，我们知道平方和必须能被200整除。然而，我们可以使用平方和公式，并对200取模。在直接使用公式之前，我们可以先将分母中的6提出，并对分子取模1200。

\[ k\left( {k + 1}\right) \left( {{2k} + 1}\right) \equiv \left( {\;\operatorname{mod}\;{1200}}\right) \]

现在，由于中国剩余定理，我们可以将1200拆分为3、16和25，并针对这三个除数分别写出线性同余式。

对于除以3的情况，我们分别令 \( k \) ≡0、1、2 (mod 3)进行检验，看乘积是否≡0 (mod 3)。对三种情况逐一验证后，我们发现结果总是≡0 (mod 3)，这意味着此情况无额外限制，可以继续。

\[ k\left( {k + 1}\right) \left( {{2k} + 1}\right) \equiv 0\left( {\;\operatorname{mod}\;{16}}\right) \]

对于除以16的情况，要使整个乘积能被16整除， \( k \) 必须≡0或15 (mod 16)。

\[ k\left( {k + 1}\right) \left( {{2k} + 1}\right) \equiv 0\left( {\;\operatorname{mod}\;{25}}\right) \]

对于除以25的情况，要使整个乘积能被25整除， \( \mathrm{k} \) 必须≡0或12或 \( {24}\mathrm{\;{mod}}{25} \) (mod 25)。

对模16和模25的每种可能组合应用中国剩余定理，我们得到答案为112。

问题2.9.4——设 \( {2}^{1110} \equiv n\left( {\;\operatorname{mod}\;{1111}}\right) \) ，且 \( 0 \leq n \leq {1111} \) 。计算 \( n \) 。来源:2019 BMT

解:在此题中，我们知道1111等于 \( {11} \cdot {101} \) 。我们将该模方程拆分，并分别对模11和模101求解。

\[ {2}^{1110} \equiv ?\left( {\;\operatorname{mod}\;{11}}\right) \]

\[ {2}^{1110} \equiv ?\left( {\;\operatorname{mod}\;{101}}\right) \]

在模11的方程中，根据费马小定理(Fermat’s Little Theorem)，我们知道 \( {2}^{10} \) 在模11下等于1。同时， \( {2}^{1110} \) 就是 \( {2}^{{10} \cdot {111}} \) ，因此它在模11下也必定等于1。 \( {2}^{1110} \equiv 1\left( {\;\operatorname{mod}\;{11}}\right) \)

对于模101:由费马小定理(Fermat’s Little Theorem)可知 \( {2}^{100} \equiv 1\left( {\;\operatorname{mod}\;{101}}\right) \) 。我们可将其11次方得到 \( {2}^{1100} \equiv 1\left( {\;\operatorname{mod}\;{101}}\right) \) 。于是问题简化为 \( {2}^{10} \) ，而我们知道 \( {2}^{10}\left( {\;\operatorname{mod}\;{101}}\right) \) 就是14。至此，我们已解出这两个独立方程。

\[ {2}^{1110} \equiv 1\left( {\;\operatorname{mod}\;{11}}\right) \]

\[ {2}^{1110} \equiv {14}\left( {\;\operatorname{mod}\;{101}}\right) \]

解得 \( {2}^{1110} \equiv {1024}\left( {\;\operatorname{mod}\;{1111}}\right) \) 。最终答案即为1024。

问题2.9.5——正整数 \( N \) 和 \( {N}^{2} \) 在十进制下均以相同的四位数字序列 \( {abcd} \) 结尾，其中数字 \( a \) 不为零。求三位数 \( {abc} \) 。

来源:2014 AIME

解答:我们将列出几个同余方程，并由此展开。

\( {N}^{2} \equiv \) abcd \( \left( {\;\operatorname{mod}\;{10000}}\right) \)

\( N \equiv \) abcd (mod 10000)

现在我们可以把这两个式子相减，因为它们都被同一个数——这里是10000——整除。如果你仍不明白为何可以相减，请回顾同余运算的最基础内容。

\[ {N}^{2} - N \equiv 0\left( {\;\operatorname{mod}\;{10000}}\right) \]

\[ N\left( {N - 1}\right) \equiv 0\left( {\;\operatorname{mod}\;{10000}}\right) \]

现在我们可以把10000拆成16和625。(这来自我们学过的中国剩余定理(CRT)技巧)

\[ N\left( {N - 1}\right) \equiv \left( {0{\;\operatorname{mod}\;{16}}}\right) \]

\[ N\left( {N - 1}\right) \equiv \left( {0{\;\operatorname{mod}\;{625}}}\right) \]

现在我们注意到一点: \( N \) 和 \( N - 1 \) 中只有一个是偶数，因为它们是连续整数，一个必为偶数，另一个必为奇数；两个连续整数不可能同时被2整除。同理，也只有一个能被5整除。于是有两种情况。

要么 \( N \) 被16整除而 \( N - 1 \) 被625整除，要么 \( N \) 被125整除而 \( N - 1 \) 被16整除。

我们先尝试其中一种情况，看能否得到答案。

\[ N \equiv 0\left( {\;\operatorname{mod}\;{16}}\right) \]

\( \mathrm{N} - 1 \equiv 0\left( {\;\operatorname{mod}\;{625}}\right) \)

对上述系统应用中国剩余定理(CRT)，得到答案为9376 (mod 10000)。9376代表abcd，而我们只取前三位，因此最终答案为937。

§2.10 综合题

现在该做更多题目了，因为这是巩固理解的唯一途径。

问题2.10.1——在十进制中，数2013的个位是3；而在九进制中，该数写作 \( {\left( {2676}\right) }_{9} \) ，个位是6。对于多少个正整数 \( b \) ，2013的 \( b \) 进制表示的个位是37？

(E) 18

来源:2013 AMC 10

解答:在b进制中，个位总是该数对b取模的结果。同理，最后两位是该数对 \( {b}^{2} \) 取模的结果。这里我们只关心个位，因此取2013 mod b。

\( {2013} \equiv 3\left( {\;\operatorname{mod}\;\mathrm{b}}\right) \)

\( {2010} \equiv 0\left( {\;\operatorname{mod}\;\mathrm{b}}\right) \)

由我们的方程可知， \( b \) 整除 2010。我们将先对 2010 进行质因数分解，再求其因数个数。

\[ {2010} = 2 \times 3 \times 5 \times {67} \]

因数个数等于把所有指数加 1 后相乘。

因数个数为 \( \left( {1 + 1}\right) \cdot \left( {1 + 1}\right) \cdot \left( {1 + 1}\right) \cdot \left( {1 + 1}\right) \) ，即 16。

然而，这并非最终答案。我们还需剔除若干情况。在 b 进制下，数字不能出现大于或等于 b 的数码。因此，由于 2013 的最大数码为 3，进制必须 ≥4。但 1、2、3 都是 2010 的因数，已计入我们算出的 16 中，故需减去 3，得到 13，对应选项 (C)。

问题 2.10.2 —— 求 \( {12}^{2011} + {11}^{2012} \) 除以 7 的余数。来源:2012 UNCO

解法:本题将使用费马小定理(Fermat's Little Theorem)。由于要在模 7 意义下求和并求余，已知 7 为质数。又因 7 与 12、11 均互质，可分别对它们应用费马小定理。

\( {12}^{2011} \equiv ?{\;\operatorname{mod}\;7} \)

\( {11}^{2012} \equiv \) ? mod 7

任何与 7 互质的数，其 6 次方除以 7 余 1。

\( {12}^{6} \equiv 1{\;\operatorname{mod}\;7} \)

\[ {11}^{6} \equiv 1{\;\operatorname{mod}\;7} \]

我们将利用费马小定理得到的方程进行变形，以求出大指数下的余数。

\( {\left( {12}^{6}\right) }^{335} \cdot {12} \equiv {1}^{335} \cdot {12}{\;\operatorname{mod}\;7} \)

\( {\left( {11}^{6}\right) }^{335} \cdot {11}^{2} \equiv {1}^{335} \cdot {11}^{2}{\;\operatorname{mod}\;7} \)

化简两式后分别得模 7 余 5 与 2，相加再取模 7，最终答案为 0。

问题 2.10.3 —— 设整数 \( n \) 的最小三个正真因数为 \( {d}_{1} < {d}_{2} < {d}_{3} \) ，使得 \( {d}_{1} + {d}_{2} + {d}_{3} = {57} \) 。求所有可能的 \( {d}_{2} \) 值之和。来源:2021 PUMAC

解法:因 \( {d}_{1},{d}_{2},{d}_{3} \) 是 \( n \) 的最小因数，显然最小者为 1，故 \( {d}_{1} \) 为 1。

代入得 \( 1 + {d}_{2} + {d}_{3} = {57} \) 。

两边同时减 1 得 \( {d}_{2} + {d}_{3} = {56} \)

假设最小因数为两个质数(显然质数最小，因为不会出现 15 这种最小因数，而 15 还有更小的质因数 3 和 5)。

\( {d}_{2} = p \) 与 \( {d}_{3} = q \) ( \( p \) 与 \( q \) 为质数)

\( p + q = {56} \) (我们需要找出和为56的素数对)

(p, q)可以是 \( \left( {3,{53}}\right) ,\left( {{13},{43}}\right) ,\left( {{19},{37}}\right) \)

我们还有另一种情况: \( {d}_{2} = p \) 且 \( {d}_{3} = {p}^{2} \) 。代入后得到 \( p + {p}^{2} = {56} \)

检验素数可知7对 \( p \) 成立。

\( {d}_{2} \) 的可能取值为3、13、19和7，这些值的和为42。

问题2.10.4——求所有正整数 \( a \) ，使得 \( a < {100} \) 且 \( {a}^{3} + {23} \) 能被24整除。

来源:2018 UNM-PNM

解答:这是又一个需要运用模运算技巧的问题。 \( {a}^{3} + {23} \equiv 0\left( {\;\operatorname{mod}\;{24}}\right) \)

我们可以将24从左侧减去，得到

\( {a}^{3} - 1 \equiv 0\left( {\;\operatorname{mod}\;{24}}\right) \)

把1移到右侧，得到

\( {a}^{3} \equiv 1\left( {\;\operatorname{mod}\;{24}}\right) \)

接下来，我们可以利用中国剩余定理(Chinese remainder theorem)的技巧，将除数24拆分为互质的较小因子。我们选用8和3。

\( {a}^{3} \equiv 1\left( {\;\operatorname{mod}\;3}\right) \)

\( {a}^{3} \equiv 1\left( {\;\operatorname{mod}\;8}\right) \)

现在，由于3和8都是较小的数，我们将分别检验它们的所有可能余数。我们将这些余数立方，观察哪些余数为1。

显然， \( a \) 必须 ≡1 (mod 3)。

我们看到 \( a \) 必须模8余1，因为只有这种情况才能使 \( {a}^{3} \) 除以8的余数为1。

\( a \equiv 1\left( {\;\operatorname{mod}\;3}\right) \)

\( a \equiv 1\left( {\;\operatorname{mod}\;8}\right) \)

两个方程的解都是 \( a \equiv 1\left( {\;\operatorname{mod}\;{24}}\right) \) 。小于100的解就是1、25、49、74和99。

问题2.10.5——从集合 \( \{ {11},{13},{15},{17},{19}\} \) 中随机选取一个数 \( m \) ，再从 \( \{ {1999},{2000},{2001},\ldots ,{2018}\} \) 中随机选取一个数 \( n \) 。 \( {m}^{n} \) 的个位数字为1的概率是多少？

(C) \( \frac{3}{10} \) (D) \( \frac{7}{20} \) (E) \( \frac{2}{5} \)

来源:2018 AMC 10

解答:本题只涉及个位数字。因此，对于所有 \( \mathrm{m} \) ，我们只需关注其个位数字，因为这是一个模10的问题。我们可以把所有底数取模10，从而将集合从 \( \{ {11},{13},{15},{17},{19}\} \) 变为 \( \{ 1,3,5,7,9\} \) 。现在，利用这个新集合，我们可以分别处理每个数字，先从1开始。

1的任何次方个位数字始终为1。因此，这里有20种情况，因为从1999到2018的所有指数都满足。

现在处理3。我们寻找3的幂的个位数字的周期。 \( {3}^{1} = 3 \)

\( {3}^{2} = 9 \)

\( {3}^{3} = {27} \equiv 7{\;\operatorname{mod}\;{10}} \)

\( {3}^{4} = {81} \equiv 1{\;\operatorname{mod}\;{10}} \)

\( {3}^{5} = {243} \equiv 3{\;\operatorname{mod}\;{10}} \)

\( {3}^{6} = {729} \equiv 9{\;\operatorname{mod}\;{10}} \)

我们看到个位数字以4为周期循环。因此，这种情况有5个指数满足。

现在处理5。5的任何次方个位数字始终为5，因此这种情况有0种。

现在处理7。

\( {7}^{1} = 7 \)

\( {7}^{2} = {49} \equiv 9{\;\operatorname{mod}\;{10}} \)

\( {7}^{3} = {343} \equiv 3{\;\operatorname{mod}\;{10}} \)

\( {7}^{4} = {2401} \equiv 1{\;\operatorname{mod}\;{10}} \)

\( {7}^{5} = {16807} \equiv 7{\;\operatorname{mod}\;{10}} \)

\( {7}^{6} = {117649} \equiv 9{\;\operatorname{mod}\;{10}} \)

这种情况同样以4为周期循环。因此，这种情况有5个指数满足。

现在处理9。我们采用与3和7相同的方法，再次得到5。

满足条件的总情况数为 \( {20} + 5 + 0 + 5 + 5 \) ，即40。总情况数为 \( 5 \times {20} \) ，即100。 \( {40}/{100} \) 化简为 \( \frac{2}{5} \) (E)。

问题2.10.6——求所有满足 \( \operatorname{lcm}\left( {{2n},{n}^{2}}\right) \) \( = {14n} - {24} \) 的正整数 \( \mathrm{n} \) 之和。

来源:2015 PUMaC

解:我们将尝试化简 \( \operatorname{lcm}\left( {{2n},{n}^{2}}\right) \) 。由于 \( n \) 在两边都出现，可以将其提出，于是最小公倍数等价于 \( \mathrm{n} \cdot \operatorname{lcm}\left( {2, n}\right) \) 。现在有两种情况: \( \mathrm{n} \) 可以是奇数或偶数。

情况1: \( n \) 为奇数

若 \( n \) 为奇数，则最小公倍数必为 \( 2\mathrm{n} \) 。原因在于 \( n \) 与2之间没有公因数，因此可直接相乘。然而，我们不能简单地把 \( {2n} \) 与 \( {14n} - {24} \) 等同，而必须把求得的最小公倍数再乘以 \( n \) ，因为最初我们把它提了出来。

\(2{n}^{2} = {14n} - {24}\)

两边除以2，移项并因式分解得

\( \left( {n - 3}\right) \left( {n - 4}\right) = 0 \)

\( n \) 必须等于3或4。然而，只有3成立，因为在此情况下我们假设 \( \mathrm{n} \) 为奇数，故必须舍去4。

情况2: \( n \) 为偶数

若 \( n \) 为偶数，则 \( \operatorname{lcm}\left( {2, n}\right) \) 必为 \( n \) 。原因在于 \( n \) 已能被2整除，因此无需像第一种情况那样再乘以2。现在我们将 \( n \) 乘以 \( n \) ，因为最初我们把它提了出来。

\( {n}^{2} = {14}\mathrm{n} - {24} \)

移项并因式分解得 \( \left( {n - 2}\right) (n - {120} = 0 \) \( n \) 必须等于2或12。在此情况下二者均为偶数，因此都成立。我们将所有解 \( 3 + 2 + {12} \) 相加得17。

问题2.10.7——Albert有一大袋糖果，想全部分给朋友。起初，他把糖果平均分给20位朋友和自己，发现余5颗。Ante到来后，他们再次平均分配，这次余3颗。若袋中糖果超过500颗，则袋中最少有多少颗糖果？来源:2012 PUMAC

解:这道题看起来复杂，实则非常简单。我们将问题用数学语言表述。设糖果总数为 \( n \) 。当糖果分给20位朋友和他本人(共21人)时，余5颗，可写为 \( \mathrm{n} \equiv 5\left( {\;\operatorname{mod}\;{21}}\right) \)

又有一人加入后，共22人，此时余3颗。 \( \mathrm{n} \equiv \left( {3{\;\operatorname{mod}\;{22}}}\right) \)

我们可用中国剩余定理联立这两个同余式，得到 \( \mathrm{n} \equiv {47}\left( {\;\operatorname{mod}\;{462}}\right) \)

因答案需大于500，故将462加47得509。

问题2.10.8——有多少个整数 \( \mathrm{x} \) 使得 \( \frac{{x}^{2} - 6}{x - 6} \) 为正整数？

解:我们将代数技巧应用于本题。首先用长除法对该分式进行除法，得到 \( \mathrm{x} + 6 + \frac{30}{x - 6} \) 。

只要 \( x - 6 \) 能整除30，该式即为整数。我们列出30的所有因数，并找出使 \( x - 6 \) 整除30的 \( x \) 值。

30的因数有1、2、3、5、6、10、15和30。需要注意的是， \( x - 6 \) 不必等于正因数，它可以是同一个因数的负数！

到目前为止， \( x - 6 \) 的可能取值为 \( 1,2,3,5,6,{10},{15},{30}, - 1, - 2, - 3, - 5, - 6 \) 、 \( - {10}, - {15} \) 和-30。

使 \( x - 6 \) 等于这些值的对应 \( x \) ，只需把所有数都加6即可得到

\( 7,8,9,{11},{12},{16},{21},{36},5,4,3,1,0, - 4, - 9 \) 和-24。

然而，代入这些 \( x \) 的值未必能让整个表达式 \( \mathrm{x} + 6 \) \( + \frac{30}{x - 6} \) 为正。只有前8个值能使整个项为正，因此答案是8。

问题2.10.9——有多少个正整数 \( \mathrm{n} \) 满足 \( \mathrm{n} \leq {2012} \) ，且 \( \mathrm{n} \) 与2012的最大公约数(gcd)为素数？来源:2012 PUMAC

解答:我们将2012进行素因数分解得到 \( {2}^{2} \cdot {503} \) 。本题中两数的gcd只能是2或503，因为它们是2012仅有的不同素因数。

情况1: \( n \) 与2012的gcd为2

任何偶数的 \( n \) 都会与2012有gcd=2，除非它能被4和503整除。小于2012且能被2(但不能被4)和503整除的唯一偶数是1006。此外，我们还需减去所有4的倍数。因此共有 \( \frac{2012}{4} \) 个 \( \mathrm{n} \) ，但要去掉1006，所以最终为502。

情况1: \( \mathrm{n} \) 与2012的gcd为503

此时n必须能被503整除但不能被2整除，否则gcd将变成1006。这里 \( \mathrm{n} \) 只有两种可能:503和1509，共2种情况。

最终答案是 \( {52} + 2 \) ，即54。

问题2.10.10——设 \( N \) 是36的最大整数倍数，其所有数字均为偶数且各位数字互不相同。求 \( N \) 除以1000的余数。

来源:2010 AIME

解答:本题中，由于已知数字为偶数，各位数字只能取0、2、4、6、8。且数字不能重复，因此我们只需在这5个数字中选取且不重复。为了最大化数值，应将最大数字放在最左，最小数字放在最右，得到86420。

接下来需检查其能否被36整除。显然该数不能被9整除，因为各位数字之和不能被9整除。因此需去掉一个数字，使各位数字之和变为9或18。经检验，只需去掉数字2即可使各位数字之和能被9整除。去掉后得到8640，该数显然能被36整除，故除以1000后最终答案为640。

问题2.10.11——存在正整数 \( x \) 和 \( y \) 满足以下方程组

\[ {\log }_{10}x + 2{\log }_{10}\left( {\gcd \left( {x, y}\right) }\right) = {60} \]

\[ {\log }_{10}y + 2{\log }_{10}\left( {\operatorname{lcm}\left( {x, y}\right) }\right) = {570}. \]

设 \( m \) 为 \( x \) 的质因数分解中(不必互异)的质因子个数，设 \( n \) 为 \( y \) 的质因数分解中(不必互异)的质因子个数。求 \( {3m} + {2n} \) 。

来源:2019 AIME 1

解答:本题中，我们需要找到一种方法简化代数方程，以消去lcm和gcd。我们记得曾学过一条规则

\[ a \cdot b = \operatorname{lcm}\left( {a, b}\right) \cdot \gcd \left( {a, b}\right) . \]

为了得到与上述类似的结果，我们将把两个方程相加(而非相乘)得到

\[ {\log }_{10}x + 2{\log }_{10}\left( {\gcd \left( {x, y}\right) }\right) + {\log }_{10}y + 2{\log }_{10}\left( {\operatorname{lcm}\left( {x, y}\right) }\right) = {630} \]

利用对数法则，我们得到

\[ \log \left( {xy}\right) + 2\left( {\log \left( {\gcd \left( {x, y}\right) \cdot \operatorname{lcm}\left( {x, y}\right) }\right) }\right) = {630} \]

利用规则 \( a \cdot b = \operatorname{lcm}\left( {a, b}\right) \cdot \gcd \left( {a, b}\right) \) ，并化简，我们得到

\( {\log }_{10}{xy} = {210} \)

解出xy，我们得到 \( {10}^{210} \)

然而，现在我们卡住了。我们将假设 \( \mathrm{x} \) 和 \( \mathrm{y} \) 都是 \( {10}.\mathrm{x} \) 的幂，且 \( {10}.\mathrm{x} \) 小于 \( \mathrm{y} \) ，而 \( \mathrm{x} \) 为 \( {10}^{a} \) ， \( \mathrm{y} \) 为 \( {10}^{b} \) 。

我们将此代回最初给出的方程。

\[ {\log }_{10}{10}^{a} + 2{\log }_{10}\left( {\gcd \left( {{10}^{a},{10}^{b}}\right) }\right) = {60} \]

由于我们已知 \( x \) 小于 \( y \) ，如前所述，最大公约数即为 \( {10}^{a} \) 。

\[ \mathrm{a} + 2\mathrm{a} = {60} \]

\[ a = {20} \]

既然我们已经得到 \( a \) 的值，即 \( x \) 的指数，我们可以迅速发现 \( b \) 为190，因为 \( {xy} = {10}^{210} \) 。

现在我们需要求出 \( x \) 和 \( y \) 中不必互异的质因子个数。由于 \( x \) 为 \( {2}^{20} \cdot {5}^{20} \) ，而 \( y \) 为 \( {2}^{190} \cdot {5}^{190}, x \) ，前者有40个不同质因子，后者有380个。

将此代入 \( {3m} + {2n} \) ，得到答案880。

问题2.10.12——正整数 \( n \) 具有如下性质: \( {n64} \) 是一个正完全立方数。假设 \( n \) 能被37整除。 \( n \) 的最小可能值是多少？

来源:2018 SMT

解:既然我们知道 \( n \) 能被37整除，不妨设 \( n = {37a} \) ，其中 \( a \) 也是正整数。

现在我们知道 \( {37a} - {64} \) 是一个完全立方数。设这个立方数为 \( {x}^{3} \) 。

\[ n = {37a} - {64} = {x}^{3} \]

\[ n = {37a} = {x}^{3} + {64} \]

回忆 \( {x}^{3} + {y}^{3} = \left( {x + y}\right) \left( {{x}^{2} - {xy} + {y}^{2}}\right) \) 这一事实，我们就能对 \( {x}^{3} + {64} \) 进行因式分解。

\[ {37a} = \left( {x + 4}\right) \left( {{x}^{2} - {4x} + {16}}\right) \]

由于37是质数，它只能整除 \( x + 4 \) 或 \( {x}^{2} - {4x} + {16} \) 。

若它整除 \( x + 4 \) ，则 \( x \) 必为33。

现在，在第二种情形下，我们假设37整除 \( {x}^{2} - {4x} + {16} \) 。

若直接设该值等于 \( {x}^{2} - {4x} + {16} \) ，我们可以在求解前将其整理为 \( {x}^{2} - {4x} - {21} = 0 \) 。

这可以分解为 \( \left( {x + 3}\right) \left( {x - 7}\right) = 0 \) ，从而得出 \( x \) 应为7。将其代入 \( n = {37a} = {x}^{3} + {64} \) ，得到 \( n = {7}^{3} + {64} \) ，即407。

问题2.10.13——求所有八位正整数的个数，这些数既是9的倍数，又各位数字互不相同。

来源:2018 HMMT

解:本题中，我们有0到9共10个可用数字，其总和为45。因此，若要组成一个含8个不同数字的数，就必须从0到9中去掉2个数字。

由于该八位数要能被9整除，其8个数字之和必须能被9整除，故去掉的2个数字之和也应是9的倍数。唯一可行的数字对为 \( \left( {0,9}\right) ,\left( {1,8}\right) ,\left( {2,7}\right) ,\left( {3,6}\right) \) 以及(4,5)。

若去掉0和9，则这8个数字的排列方式共有8!(8的阶乘)种。

对于其余4对数字，0有7个可放位置(除首位外)，其余7个数字有7!种排列方式。

这意味着共有 \( 7 \cdot 7! \) 种方式，再乘以4，因为有4对数字。

\( 8! + {28} \cdot 7! = {36} \cdot 7! \) ，即181440。

问题2.10.14——最小的正整数 \( n \) 是多少，使得2016 \( n \) 是一个完全立方数？

来源:2018 HMMT

解答:本题中，我们首先对2016进行质因数分解，得到 \( {2}^{5} \cdot {3}^{2} \cdot 7 \) 。

要使其成为完全立方数，所有指数都应能被3整除。为此，我们需再乘一个2，使指数变为6；对3也做同样处理。对于7，我们将2016乘以 \( {7}^{2} \) ，使指数变为3。

因此， \( n \) 等于 \( 2 \cdot 3 \cdot {7}^{2} \) ，即294。

问题2.10.15—— \( {2022}^{{2022}^{2022}} \) 的最后两位数字是什么？

来源:2022 SMT

解答:求最后两位数字等价于求该数模100的值。利用中国剩余定理(Chinese Remainder Theorem)，可将100拆分为4和25，分别求该数模4和模25的值。

\[ {2022}^{{2022}^{2022}} \equiv ?{\;\operatorname{mod}\;4} \]

\[ {2022}^{{2022}^{2022}} \equiv ?{\;\operatorname{mod}\;{25}} \]

显然 \( {2022}^{{2022}^{2022}} \equiv 0{\;\operatorname{mod}\;4} \) ，因为2022能被2整除，且指数非常高。

对于模25的方程，我们可以使用欧拉函数(Euler’s Totient function)，并已知 \( {2022}^{20} \equiv 1 \) mod 25。

然而，以2022为底的指数是 \( {2022}^{2022} \) ，因此可将该指数模20。我们需将其拆分为模4和模5，以便使用中国剩余定理。

\( {2022}^{2022} \equiv 0{\;\operatorname{mod}\;4} \)

\( {2022}^{2022} \equiv {2}^{2022}{\;\operatorname{mod}\;5} \)

显然，该表达式在模5下为4，我们可以用个位数规律的方法求出。

由于已知 \( {2022}^{2022} \equiv 0{\;\operatorname{mod}\;4} \) 和 \( {2022}^{2022} \equiv 4{\;\operatorname{mod}\;5} \) ，可运用中国剩余定理得出 \( {2022}^{2022} \equiv 4{\;\operatorname{mod}\;{20}} \) 。

由此可知 \( {2022}^{{2022}^{2022}} \equiv {2022}^{4} \equiv {\left( -3\right) }^{4}{\;\operatorname{mod}\;{25}} \) 。

现在我们得到 \( {81} \equiv 6{\;\operatorname{mod}\;{25}} \) 。

由于已知

\( {2022}^{{2022}^{2022}} \equiv 0{\;\operatorname{mod}\;4} \)

\( {2022}^{{2022}^{2022}} \equiv 6{\;\operatorname{mod}\;{25}} \)

由此可知，我们表达式的最后两位数字是56。

问题2.10.16——数字 \( H, M \) 和 \( C \) 满足以下关系，其中 \( {ABC} \) 表示以 \( A, B \) 和 \( C \) 为十进制数字的数。

\( \bar{H} \times \bar{H} = \bar{M} \times \bar{C} + 1 \)

\( \overline{HH} \times \bar{H} = \overline{MC} \times \bar{C} + 1 \)

\( \overline{HHH} \times \bar{H} = \overline{MCC} \times \bar{C} + 1 \)

求 \( \overline{HMC} \) 。

来源:2011 CHMMC

解答:本题中，可将 \( \overline{HH} \) 展开为 \( {10H} + H \) ，即 \( {11H} \) 。可将 \( \overline{HHH} \) 展开为 \( {100H} + {10H} + H \) ，即 \( {111H} \) 。

\[ \overline{MC} = {10M} + C \]

\[ \overline{MCC} = {100M} + {10C} + C = {100M} + {11C} \]

可将这三个方程转化为

\( {H}^{2} = {MC} + 1 \)

\( {11}{H}^{2} = {10MC} + {C}^{2} + 1 \)

\( {111}{H}^{2} = {100MC} + {11}{C}^{2} + 1 \)

将第一个方程乘以11并与第二个方程相等，可得

\( {10MC} + {C}^{2} + 1 = {11MC} + {11} \)

整理并因式分解该方程得 \( C\left( {C - M}\right) = {10} \)

由此，可代入 \( C \) 的可能值，因其必须整除10。唯一可能的值为1、2、5

逐一验证可知 \( C \) 必为5，代入该方程得 \( M = 2 \) 。再将其代入 \( {H}^{2} = {MC} + 1 \) ，得 \( H = 4 \) 。

这些数字表明我们的数 \( \overline{HMC} \) 为435。

问题2.10.17——给定 \( k \geq 1 \) ，令 \( {p}_{k} \) 表示第 \( k \) 小的素数。若 \( N \) 为满足 \( {abcd} = \) \( \mathop{\prod }\limits_{{k = 1}}^{{2023}}{p}_{k} \) 且 \( a < b \) 和 \( c < d \) 的正整数有序四元组(a, b, c, d)的个数，求 \( N{\;\operatorname{mod}\;\left( {1000}\right) } \)

来源:2022 PUMAC

解答:本题中，我们将分别处理 \( {ab} \) 和 \( {cd} \) 。根据abcd的2023个素因子，我们最多可将1到2022个素因子分配给 \( {ab} \) ，其余则分配给 \( {cd} \) 。选择 \( i \) 个素因子的方式数为 \( \left( \begin{matrix} {2023} \\ i \end{matrix}\right) \) 。

设 \( i \) 个素因子分配给 \( {ab} \) ，而 \( {2023} - i \) 个分配给 \( {cd} \) 。

由此，我们有 \( {2}^{i} \) 种方式将 \( i \) 个素因子分配给 \( {ab} \) ，以及 \( {2}^{{2023} - i} \) 种方式将 \( {2023} - i \) 个素因子分配给 \( {cd} \) 。然而，需满足 \( a < b \) 和 \( c < d \) 的条件。对于 \( a \) 和 \( b \) 的每一对乘积等于 \( i \) 个素因子的因子，由于已知有 \( {2}^{i} \) 种分配方式，需除以2以确保较小者为 \( a \) 。

采用该策略，我们得到

\( \mathop{\sum }\limits_{{i = 1}}^{{2022}}\left( \begin{matrix} {2023} \\ i \end{matrix}\right) \cdot \frac{{2}^{i}}{2} \cdot \frac{{2}^{{2023} - i}}{2} \)

该求和式变为 \( \mathop{\sum }\limits_{{i = 1}}^{{2022}}\left( \begin{matrix} {2023} \\ i \end{matrix}\right) \cdot {2}^{2021} \)

化简后得到 \( {2}^{2021}\left( {\left( \begin{matrix} {2023} \\ 1 \end{matrix}\right) + \left( \begin{matrix} {2023} \\ 2 \end{matrix}\right) \ldots + \left( \begin{matrix} {2023} \\ {2022} \end{matrix}\right) }\right) \)

\( \mathop{\sum }\limits_{{x = 0}}^{{2023}}\left( \begin{matrix} {2023} \\ x \end{matrix}\right) = {2}^{2023} \) (这是你在组合数学部分将学到的恒等式)

然而，我们必须从中减去 \( \left( \begin{matrix} {2023} \\ 1 \end{matrix}\right) \) 和 \( \left( \begin{matrix} {2023} \\ {2023} \end{matrix}\right) \) ，才能得到 \( {2}^{2023} - 2 \)

我们将该表达式乘以 \( {2}^{2021} \) ，得到 \( {2}^{2021}\left( {{2}^{2023} - 2}\right) \)

该表达式可改写为 \( {2}^{2022}\left( {{2}^{2022} - 1}\right) \)

现在我们使用中国剩余定理(Chinese Remainder Theorem)，因为我们想求其模1000的值。我们可以分别求解模8和模125。

\( {2}^{2022}\left( {{2}^{2022} - 1}\right) \equiv 0{\;\operatorname{mod}\;8} \) (因为 \( {2}^{3} \) 整除 \( {2}^{2022} \)

\( {2}^{2022}\left( {{2}^{2022} - 1}\right) \equiv ?{\;\operatorname{mod}\;{125}} \)

利用欧拉定理(Euler's Totient Theorem)可知125的欧拉函数值(totient)为100，从而得到 \( {2}^{100} \equiv 1{\;\operatorname{mod}\;{125}} \) 。利用该结果并化简表达式，可得模1000的余数为112。