🔍 数论进阶

Advanced Number Theory

模运算、同余、进制转换、完全平方数是 AMC 10 中高频出现的数论考点。掌握这些技巧，能让你在面对看似复杂的问题时迅速找到突破口。

📚 4 章节 💡 5 道例题 ✏️ 8 道练习 🎯 难度：进阶 ⏱ 约45分钟

模运算 Modular Arithmetic

必考进阶

1.1 同余的定义 Definition of Congruence

若整数 a 和 b 除以正整数 n 的余数相同，则称 a 和 b 模 n 同余，记作：

📝 同余记号 / Congruence Notation

a ≡ b (mod n) ⇔ n | (a − b)

a is congruent to b modulo n if and only if n divides (a − b).

举例：17 ≡ 2 (mod 5)，因为 17 − 2 = 15 = 3 × 5。23 ≡ 3 (mod 10)，因为 23 − 3 = 20 = 2 × 10。

1.2 同余运算 Congruence Arithmetic

同余关系保持加、减、乘运算：

📝 同余运算规则

若 a ≡ b (mod n) 且 c ≡ d (mod n)，则：

a + c ≡ b + d (mod n)

a − c ≡ b − d (mod n)

a × c ≡ b × d (mod n)

a^k ≡ b^k (mod n)

💡 邓老师提示：除法不能直接传递同余！比如 6 ≡ 0 (mod 6)，但 6/2 = 3 ≠ 0/2 (mod 6)。同余中做除法需要特殊处理。

1.3 费马小定理 Fermat's Little Theorem

📝 费马小定理 / Fermat's Little Theorem

若 p 为质数且 gcd(a, p) = 1，则 a^p−1 ≡ 1 (mod p)

If p is prime and gcd(a,p)=1, then a^(p−1) ≡ 1 (mod p).

推论：a^p ≡ a (mod p)，对任意整数 a 和质数 p 成立。

应用示例：求 7¹⁰⁰ mod 5。注意 5 是质数，gcd(7,5)=1，所以 7⁴ ≡ 1 (mod 5)。100 = 4 × 25，因此 7¹⁰⁰ ≡ 1²⁵ = 1 (mod 5)。

💡 邓老师提示：费马小定理在 AMC 10 中是求大指数幂的余数的利器。特别适合求 a^大数 mod p（p为质数）类型的问题。

整除进阶 Advanced Divisibility

高频中等

2.1 GCD 与 LCM GCD and LCM

📝 关键关系 / Key Relationship

gcd(a, b) × lcm(a, b) = |a × b|

The product of GCD and LCM equals the product of the two numbers.

GCD（最大公约数）的性质：

gcd(a, b) = gcd(b, a mod b)（欧几里得算法的基础）
gcd(a, 0) = |a|
若 d = gcd(a, b)，则 gcd(a/d, b/d) = 1（互质）

2.2 欧几里得算法 Euclidean Algorithm

📝 欧几里得算法 / Euclidean Algorithm

gcd(a, b) = gcd(b, a mod b)，反复取余直到余数为 0

示例：gcd(252, 198)

252 = 1 × 198 + 54

198 = 3 × 54 + 36

54 = 1 × 36 + 18

36 = 2 × 18 + 0

gcd(252, 198) = 18

💡 邓老师提示：欧几里得算法在 AMC 中偶尔直接考，更常见的是利用 gcd×lcm = ab 的关系来求 lcm 或某个数。

2.3 完全平方数 Perfect Squares

完全平方数是某个整数的平方。AMC 10 中常考的性质：

完全平方数的个位只能是 0, 1, 4, 5, 6, 9
完全平方数 mod 4 只能是 0 或 1
完全平方数 mod 3 只能是 0 或 1
相邻两个完全平方数之差是连续奇数：1, 3, 5, 7, 9, ...
若 n² 的末位是 6，则 n 的末位一定是 4 或 6

⚠️ 注意：判断一个数是否为完全平方数，除了看末位，还可以检查它的质因数分解中每个质数的指数是否都是偶数。

数的表示 Number Representations

中等必考

3.1 进制转换 Base Conversion

十进制转 k 进制：反复除以 k，记录余数，倒序排列。

📝 示例：将 42 转换为二进制

42 ÷ 2 = 21 余 0

21 ÷ 2 = 10 余 1

10 ÷ 2 = 5 余 0

5 ÷ 2 = 2 余 1

2 ÷ 2 = 1 余 0

1 ÷ 2 = 0 余 1

42₁₀ = 101010₂

k 进制转十进制：各位数字 × k^位权，然后求和。

📝 示例：将 101010₂ 转换为十进制

1×2⁵ + 0×2⁴ + 1×2³ + 0×2² + 1×2¹ + 0×2⁰ = 32 + 0 + 8 + 0 + 2 + 0 = 42

💡 邓老师提示：AMC 10 常考"某数在 k 进制下的各位数字之和"类型的问题。转换后直接求和即可。也可以先转十进制再求各位之和验证。

数论应用 Number Theory Applications

进阶

4.1 尾数规律 Last Digit Patterns

大数幂的个位数（尾数）呈现周期性规律：

底数尾数	幂次的尾数周期	Last digit cycle
0, 1, 5, 6	周期为 1（恒不变）	Always the same
2	2, 4, 8, 6（周期 4）	2, 4, 8, 6
3	3, 9, 7, 1（周期 4）	3, 9, 7, 1
4	4, 6（周期 2）	4, 6
7	7, 9, 3, 1（周期 4）	7, 9, 3, 1
8	8, 4, 2, 6（周期 4）	8, 4, 2, 6
9	9, 1（周期 2）	9, 1

4.2 中国剩余定理简介 Chinese Remainder Theorem (CRT)

当已知一个数除以几个互质的数各自的余数时，可以用 CRT 求出这个数。

基本思路：从最大的模开始，列出满足条件的数列，逐步筛选同时满足其他条件的数。

📝 示例

N 除以 3 余 2，除以 5 余 3

满足"除以 5 余 3"的数：3, 8, 13, 18, ...

检验除以 3 的余数：8÷3=2余2 ✓

最小 N = 8

例题精讲 Worked Examples

5 题含历年真题

📌 例题 1 费马小定理

求 7¹⁰⁰ 除以 5 的余数。What is the remainder when 7¹⁰⁰ is divided by 5?

解题思路：费马小定理

5 是质数，gcd(7,5)=1。
由费马小定理：7⁴ ≡ 1 (mod 5)
7¹⁰⁰ = (7⁴)²⁵ ≡ 1²⁵ = 1 (mod 5)
余数为 1。
By Fermat's Little Theorem: 7⁴ ≡ 1 (mod 5). So 7¹⁰⁰ = (7⁴)²⁵ ≡ 1²⁵ = 1 (mod 5).

📌 例题 2 欧几里得算法

gcd(252, 198) 等于多少？What is gcd(252, 198)?

解题思路：辗转相除

252 = 1 × 198 + 54
198 = 3 × 54 + 36
54 = 1 × 36 + 18
36 = 2 × 18 + 0
gcd(252, 198) = 18。
252 = 1(198)+54, 198=3(54)+36, 54=1(36)+18, 36=2(18)+0. So gcd=18.

📌 例题 3 进制转换

将十进制数 2026 转换为五进制，其各位数字之和是多少？Convert 2026 from base 10 to base 5. What is the sum of its digits?

解题思路：反复除以5

2026 ÷ 5 = 405 余 1
405 ÷ 5 = 81 余 0
81 ÷ 5 = 16 余 1
16 ÷ 5 = 3 余 1
3 ÷ 5 = 0 余 3
五进制：31011。各位数字之和 = 3+1+0+1+1 = 6。
2026 in base 5 is 31011. Sum of digits = 3+1+0+1+1 = 6.

📌 例题 4 中国剩余定理

一个正整数除以 3 余 2，除以 5 余 3，除以 7 余 1。满足条件的最小正整数是多少？A positive integer leaves remainders 2, 3, and 1 when divided by 3, 5, and 7. Find the smallest such number.

解题思路：逐步筛选

除以 7 余 1：1, 8, 15, 22, 29, ...
检验除以 5 余 3：8÷5=1余3 ✓
检验除以 3 余 2：8÷3=2余2 ✓
最小正整数为 8。
Numbers ≡ 1 (mod 7): 1, 8, 15... Check: 8 mod 5 = 3 ✓, 8 mod 3 = 2 ✓. Answer: 8.

📌 例题 5 完全平方数

有多少个三位数是完全平方数？How many three-digit numbers are perfect squares?

解题思路：确定范围

三位数范围：100 ≤ n² ≤ 999
10² = 100，31² = 961，32² = 1024 > 999
从 10 到 31，共 31 − 10 + 1 = 22 个。
Three-digit perfect squares: 10²=100 through 31²=961. Count = 31−10+1 = 22.

巩固练习 Practice Problems

8 题提交即判

第1题 3⁵⁰ 除以 7 的余数是多少？ What is 3⁵⁰ mod 7?

第2题 gcd(48, 36) × lcm(48, 36) 等于多少？ What is gcd(48, 36) × lcm(48, 36)?

第3题将十进制数 100 转换为三进制，其各位数字之和是多少？ Convert 100 to base 3. What is the digit sum?

第4题 7²⁰²⁶ 的个位数是多少？ What is the last digit of 7²⁰²⁶?

第5题一个数除以 4 余 1，除以 5 余 2，除以 6 余 3。满足条件的最小正整数是多少？ A number leaves remainders 1, 2, 3 when divided by 4, 5, 6. Find the smallest such number.

第6题下列哪个数不可能是完全平方数的个位数字？ Which digit CANNOT be the last digit of a perfect square?

第7题若 gcd(a, b) = 6 且 lcm(a, b) = 60，则 a + b 的最小值是多少？ If gcd(a, b) = 6 and lcm(a, b) = 60, what is the minimum of a + b?

第8题求 lcm(12, 18, 30) 的值。 Find lcm(12, 18, 30).

⬅ 上一页代数方程与函数 / Algebra 下一页 ➡ 平面几何进阶 / Geometry