🔢 数论基础

在 AIME 中，整除理论的应用比 AMC 更加深入。除了基本的整除定义外，还需要掌握最大公约数（GCD）和最小公倍数（LCM）的性质，以及它们之间的关系。

In AIME, the application of divisibility theory is more advanced than in AMC. Besides the basic definition of divisibility, you need to master the properties of Greatest Common Divisor (GCD) and Least Common Multiple (LCM), as well as their relationship.

重要性质：

• 如果 d | a 且 d | b，则 d | (ma + nb)，其中 m, n 为整数 If d | a and d | b, then d | (ma + nb) for integers m, n
• gcd(a, b) = gcd(a, b - a) Euclidean algorithm property
• 如果 gcd(a, b) = 1，则称 a 和 b 互质 If gcd(a, b) = 1, a and b are called coprime

例题 1 Example 1

质数是数论的基础概念。在 AIME 中，经常需要利用质数的性质、质因数分解以及与质数相关的定理（如费马小定理、欧拉定理等）来解决问题。

Primes are the fundamental concept in number theory. In AIME, you often need to use properties of primes, prime factorization, and theorems related to primes (such as Fermat's Little Theorem, Euler's Theorem, etc.) to solve problems.

质因数分解的应用：

• 求一个数的因数个数：(a₁+1)(a₂+1)...(a_k+1)
• 求一个数的因数之和：∏(p_i^(a_i+1)-1)/(p_i-1)
• 判断一个数是否为完全平方数：所有指数 a_i 都是偶数

例题 2 Example 2

同余是数论中的重要概念，在 AIME 中有广泛应用。掌握同余的基本性质和运算规则，是解决复杂数论问题的关键。

Congruence is an important concept in number theory and has wide applications in AIME. Mastering the basic properties and operation rules of congruence is key to solving complex number theory problems.

同余的基本性质：

• 自反性：a ≡ a (mod m)
• 对称性：若 a ≡ b (mod m)，则 b ≡ a (mod m)
• 传递性：若 a ≡ b (mod m) 且 b ≡ c (mod m)，则 a ≡ c (mod m)
• 若 a ≡ b (mod m) 且 c ≡ d (mod m)，则 a + c ≡ b + d (mod m)
• 若 a ≡ b (mod m) 且 c ≡ d (mod m)，则 ac ≡ bd (mod m)

例题 3 Example 3