线性丢番图方程是最基本的丢番图方程类型，形如 ax + by = c，其中 a、b、c 是整数，x、y 是整数未知数。在 AIME 中，经常需要求解线性丢番图方程的整数解。
Linear Diophantine equations are the most basic type of Diophantine equations, in the form ax + by = c, where a, b, c are integers, and x, y are integer unknowns. In AIME, we often need to find integer solutions to linear Diophantine equations.
求解线性丢番图方程的步骤：
- 计算 d = gcd(a, b)，检查 d 是否整除 c
- 使用扩展欧几里得算法找到一组特解 (x₀, y₀)
- 所有解的形式为：x = x₀ + (b/d)t, y = y₀ - (a/d)t，其中 t 是整数
例题 1 Example 1
首先，计算 gcd(3, 5) = 1，1 整除 2020，所以方程有解。
使用扩展欧几里得算法找到一组特解：
5 = 3 × 1 + 2
3 = 2 × 1 + 1
2 = 1 × 2 + 0
回代得：1 = 3 - 2 × 1 = 3 - (5 - 3 × 1) × 1 = 2 × 3 - 1 × 5
所以 2020 = 2020 × 1 = 2020 × (2 × 3 - 1 × 5) = 4040 × 3 - 2020 × 5
特解为 x₀ = 4040, y₀ = -2020
通解为 x = 4040 - 5t, y = -2020 + 3t
要求正整数解，所以：
4040 - 5t > 0 → t < 808
-2020 + 3t > 0 → t > 2020/3 ≈ 673.33
所以 t 的取值范围是 674 ≤ t ≤ 807，共 807 - 674 + 1 = 134 个解。
First, gcd(3, 5) = 1, which divides 2020, so solutions exist. Using extended Euclidean algorithm, we find a particular solution: 2020 = 4040 × 3 - 2020 × 5. General solution: x = 4040 - 5t, y = -2020 + 3t. For positive solutions: 674 ≤ t ≤ 807, total 134 solutions.
佩尔方程是形如 x² - Dy² = 1 的二次不定方程，其中 D 是正整数且不是完全平方数。佩尔方程在 AIME 中偶尔出现，需要掌握其基本解法。
Pell's equation is a type of quadratic Diophantine equation in the form x² - Dy² = 1, where D is a positive integer that is not a perfect square. Pell's equation occasionally appears in AIME, and its basic solution method needs to be mastered.
求解佩尔方程的步骤：
- 验证 D 是否为非平方正整数
- 使用连分数法或试算法找到基本解 (x₁, y₁)
- 通过基本解生成所有解
例题 2 Example 2
通过试算法寻找最小正整数解：
当 y=1 时，x² = 1 + 2×1 = 3，不是平方数
当 y=2 时，x² = 1 + 2×4 = 9，x=3，符合条件
所以最小正整数解是 (3, 2)。
By trial method: For y=1, x²=3 (not a square); for y=2, x²=9 (x=3). So the smallest positive integer solution is (3, 2).
勾股数是指满足 a² + b² = c² 的正整数三元组 (a, b, c)。勾股数在 AIME 中经常出现，需要掌握其性质和生成方法。
Pythagorean triples are sets of three positive integers (a, b, c) that satisfy a² + b² = c². Pythagorean triples often appear in AIME, and their properties and generation methods need to be mastered.
勾股数的性质：
- 本原勾股数中，必有一个数是 3 的倍数，一个数是 4 的倍数，一个数是 5 的倍数
- 所有勾股数都是本原勾股数的倍数
- 勾股数可以无限生成
例题 3 Example 3
根据勾股数的定义，我们需要满足：
n² + (n+1)² = (n+2)²
展开得：n² + n² + 2n + 1 = n² + 4n + 4
化简得：n² - 2n - 3 = 0
解得：n = 3 或 n = -1（舍去负数解）
验证：3² + 4² = 9 + 16 = 25 = 5²，符合条件。
By the definition of Pythagorean triple: n² + (n+1)² = (n+2)². Expanding and simplifying: n² - 2n - 3 = 0. Solving: n=3. Verification: 3² + 4² = 5², which is correct.