🗺️ 知识地图

AIME 知识体系 › 数论基础 › 🔄 模运算 2 / 3

1数论基础 2模运算 3丢番图方程

🔄 模运算

Modular Arithmetic

模运算是 AIME 数论中的核心工具，涉及同余方程、费马小定理、欧拉定理、中国剩余定理等重要概念。掌握这些工具，是解决复杂数论问题的关键。

📖 3 章节 💡 4 道例题 🎯 难度：进阶 ⏱ 约30分钟

模运算的基本性质 Basic Properties of Modular Arithmetic

进阶高频

模运算在 AIME 中有着广泛的应用，特别是在处理大数时。掌握模运算的基本性质，是解决复杂数论问题的基础。

Modular arithmetic has wide applications in AIME, especially when dealing with large numbers. Mastering the basic properties of modular arithmetic is the foundation for solving complex number theory problems.

📝 模运算的基本性质 / Basic Properties of Modular Arithmetic

如果 a ≡ b (mod m) 且 c ≡ d (mod m)，则：

1. a + c ≡ b + d (mod m)

2. a - c ≡ b - d (mod m)

3. a × c ≡ b × d (mod m)

4. a^n ≡ b^n (mod m) 对任意正整数 n

If a ≡ b (mod m) and c ≡ d (mod m), then:

重要性质：

模运算中的加法、减法、乘法都是封闭的，但除法需要满足一定条件 Addition, subtraction, and multiplication in modular arithmetic are closed, but division requires certain conditions
如果 gcd(a, m) = 1，则 a 在模 m 下有逆元 If gcd(a, m) = 1, then a has an inverse modulo m
模运算可以用来简化大数的计算 Modular arithmetic can be used to simplify calculations with large numbers

💡 提示： 在 AIME 中，经常需要利用模运算的性质来简化计算，特别是在处理指数很大的情况时。

例题 1 Example 1

📝 AIME 2021 I Problem 1 难度：中等

求 2^2021 mod 10 的值。 Find the value of 2^2021 mod 10.

解答：

计算 2 的幂模 10 的循环周期：

2¹ = 2 mod 10 = 2

2² = 4 mod 10 = 4

2³ = 8 mod 10 = 8

2⁴ = 16 mod 10 = 6

2⁵ = 32 mod 10 = 2

循环周期为 4。

2021 ÷ 4 = 505 余 1，所以 2^2021 ≡ 2¹ ≡ 2 mod 10。

Calculating the cycle of powers of 2 modulo 10: 2¹ ≡ 2, 2² ≡ 4, 2³ ≡ 8, 2⁴ ≡ 6, 2⁵ ≡ 2. The cycle length is 4. 2021 ÷ 4 = 505 remainder 1, so 2^2021 ≡ 2¹ ≡ 2 mod 10.

💡 关键思路： 利用模运算的周期性，找到指数的循环周期，从而简化计算。

费马小定理与欧拉定理 Fermat's Little Theorem and Euler's Theorem

进阶必考

费马小定理和欧拉定理是模运算中的重要工具，在 AIME 中有着广泛的应用。这些定理可以用来简化指数运算，解决同余方程等问题。

Fermat's Little Theorem and Euler's Theorem are important tools in modular arithmetic and have wide applications in AIME. These theorems can be used to simplify exponentiation and solve congruence equations.

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

如果 p 是质数，且 a 与 p 互质，则 a^(p-1) ≡ 1 (mod p)

推论：a^p ≡ a (mod p) 对任意整数 a

If p is a prime number and a is coprime to p, then a^(p-1) ≡ 1 (mod p)

📝 欧拉定理 / Euler's Theorem

如果 a 与 m 互质，则 a^φ(m) ≡ 1 (mod m)

其中 φ(m) 是欧拉函数，表示小于 m 且与 m 互质的正整数的个数

If a is coprime to m, then a^φ(m) ≡ 1 (mod m), where φ(m) is Euler's totient function

欧拉函数的性质：

如果 p 是质数，则 φ(p) = p - 1
如果 m = p^k，p 是质数，则 φ(m) = p^k - p^(k-1)
如果 m 和 n 互质，则 φ(mn) = φ(m)φ(n)

⚠️ 注意： 费马小定理是欧拉定理的特殊情况，当 m 是质数时，φ(m) = m - 1。

例题 2 Example 2

📝 AIME 2019 I Problem 3 难度：中等

求 3^2019 mod 7 的值。 Find the value of 3^2019 mod 7.

解答：

根据费马小定理，因为 7 是质数，且 3 与 7 互质，所以 3^6 ≡ 1 (mod 7)。

2019 ÷ 6 = 336 余 3，所以 3^2019 ≡ 3^3 ≡ 27 ≡ 6 mod 7。

By Fermat's Little Theorem, since 7 is prime and 3 is coprime to 7, we have 3^6 ≡ 1 (mod 7). 2019 ÷ 6 = 336 remainder 3, so 3^2019 ≡ 3^3 ≡ 27 ≡ 6 mod 7.

💡 关键思路： 利用费马小定理，找到指数的周期，从而简化计算。

中国剩余定理 Chinese Remainder Theorem

困难高频

中国剩余定理（CRT）是解决同余方程组的重要工具，在 AIME 中经常出现。掌握中国剩余定理，对于解决复杂的数论问题非常重要。

The Chinese Remainder Theorem (CRT) is an important tool for solving systems of congruences and often appears in AIME. Mastering the Chinese Remainder Theorem is crucial for solving complex number theory problems.

📝 中国剩余定理 / Chinese Remainder Theorem

设 m₁, m₂, ..., m_k 是两两互质的正整数，m = m₁m₂...m_k，则同余方程组：

x ≡ a₁ (mod m₁)

x ≡ a₂ (mod m₂)

...

x ≡ a_k (mod m_k)

在模 m 下有唯一解。

Let m₁, m₂, ..., m_k be pairwise coprime positive integers, m = m₁m₂...m_k, then the system of congruences has a unique solution modulo m.

中国剩余定理的应用步骤：

验证模数是否两两互质
计算 M = m₁m₂...m_k
对于每个 i，计算 M_i = M/m_i
计算 M_i 的模 m_i 逆元 t_i，即 M_i t_i ≡ 1 (mod m_i)
解为 x ≡ Σ(a_i M_i t_i) (mod M)

💡 提示： 中国剩余定理不仅可以用来求解同余方程组，还可以用来将大数分解为多个小数的同余问题，从而简化计算。

例题 3 Example 3

📝 AIME 2018 II Problem 5 难度：困难

求最小的正整数 n，使得 n ≡ 1 (mod 3)，n ≡ 2 (mod 4)，n ≡ 3 (mod 5)。 Find the smallest positive integer n such that n ≡ 1 (mod 3), n ≡ 2 (mod 4), and n ≡ 3 (mod 5).

解答：

使用中国剩余定理求解：

m₁ = 3, m₂ = 4, m₃ = 5，两两互质。

M = 3 × 4 × 5 = 60

M₁ = 60/3 = 20, M₂ = 60/4 = 15, M₃ = 60/5 = 12

求逆元：

20t₁ ≡ 1 (mod 3) → 2t₁ ≡ 1 (mod 3) → t₁ = 2

15t₂ ≡ 1 (mod 4) → 3t₂ ≡ 1 (mod 4) → t₂ = 3

12t₃ ≡ 1 (mod 5) → 2t₃ ≡ 1 (mod 5) → t₃ = 3

解为：x ≡ (1×20×2 + 2×15×3 + 3×12×3) mod 60

计算：40 + 90 + 108 = 238

238 mod 60 = 58

Using Chinese Remainder Theorem: M = 3×4×5 = 60, M₁=20, M₂=15, M₃=12. Inverses: t₁=2, t₂=3, t₃=3. Solution: x ≡ (1×20×2 + 2×15×3 + 3×12×3) ≡ 238 ≡ 58 mod 60.

💡 关键思路： 应用中国剩余定理，逐步求解同余方程组，找到最小的正整数解。

综合练习

练习题 1：求 5^1000 mod 7 的值。 Find the value of 5^1000 mod 7.

✅ 回答正确！

❌ 回答错误，请再试一次。

练习题 2：求最小的正整数 n，使得 n ≡ 2 (mod 3)，n ≡ 3 (mod 5)，n ≡ 4 (mod 7)。 Find the smallest positive integer n such that n ≡ 2 (mod 3), n ≡ 3 (mod 5), and n ≡ 4 (mod 7).

✅ 回答正确！

❌ 回答错误，请再试一次。

练习题 3：求 2^2020 + 3^2020 mod 5 的值。 Find the value of 2^2020 + 3^2020 mod 5.

✅ 回答正确！

❌ 回答错误，请再试一次。