# Explore Diophantine Equations

> Solve Diophantine equations (integer-only solutions) including linear, quadratic, and Pell equations. Covers the extended Euclidean algorithm, descent methods, and existence proofs. Use when finding all integer solutions to ax + by = c, solving Pell's equation, generating Pythagorean triples, proving no integer solutions exist via modular constraints, or finding the fundamental solution from which all others are generated.

- Skill: `pjt222/explore-diophantine-equations-7` (Agent Skill)
- Install (CLI): `npx get-skill add pjt222/explore-diophantine-equations-7`
- Raw SKILL.md: https://api.skillmd.com/api/skills/pjt222/explore-diophantine-equations-7/raw
- Safety review: pending (external: skill-scanner PASS, skillspector PASS)
- Works with: Claude Code, Claude.ai, OpenAI Codex
- Category: Coding & Dev Tools
- License: MIT
- Author: pjt222 (https://skillmd.com/u/pjt222)
- Updated: 2026-09-21
- Page: https://skillmd.com/skills/pjt222/explore-diophantine-equations-7

---


# 探丟番圖方程

解丟番圖方程——僅求整數解之多項式方程。分方程之類、測可解性、尋特解與通解、生解族。涵線性方程、Pell 方程、畢氏三元組與一般二次型。

## 適用時機

- 尋線性方程 ax + by = c 之所有整數解
- 解 Pell 方程 x^2 - Dy^2 = 1（或 = -1）
- 生畢氏三元組或他參數化整數族
- 藉模約束證所予方程無整數解
- 測一般二次丟番圖方程之可解性
- 尋他皆自之生之基本解

## 輸入

- **必要**：待解之丟番圖方程（顯式，如 3x + 5y = 17 或 x^2 - 7y^2 = 1）
- **選擇性**：求所有解、僅一特解、或證不存
- **選擇性**：變元範圍之約束（如唯正整數）
- **選擇性**：是否以參數式表通解
- **選擇性**：所偏好之證技（構造、下降、模阻）

## 步驟

### 步驟一：分方程類

定丟番圖方程之結構以擇合適之解法。

1. **線性**：ax + by = c，a、b、c 為予之整數，x、y 為未知。
   - 解法：擴展歐幾里得算法。

2. **Pell 方程**：x^2 - Dy^2 = 1（或 = -1、或 = N），D 為正非平方整數。
   - 解法：sqrt(D) 之連分數展開。

3. **畢氏**：x^2 + y^2 = z^2。
   - 解法：參數族 x = m^2 - n^2、y = 2mn、z = m^2 + n^2。

4. **一般二次**：ax^2 + bxy + cy^2 + dx + ey + f = 0。
   - 解法：完全平方、化至 Pell 或更簡形，或施模約束。

5. **高階或特殊**：Fermat 型（x^n + y^n = z^n，n > 2）、平方和等。
   - 解法：模阻、下降或已知不可能結果。

記分類與所擇之法。

**預期：** 精確分類，附已識之解策。

**失敗時：** 若方程不配標準型，試代或轉以化至已知形。如 x^2 + y^2 + z^2 = n 可藉 Legendre 三平方和定理。若無顯之化，施模約束（步驟四）以測阻。

### 步驟二：解線性丟番圖方程（若類為線性）

解 ax + by = c 求整數 x、y。

1. **以歐幾里得算法算 g = gcd(a, b)**。

2. **測可解**：解存當且僅當 g | c。
   - 若 g 不整除 c，證不存：「因 gcd(a, b) = g 而 g 不整除 c，故方程 ax + by = c 無整數解。」
   - 若無解則止。

3. **簡**：除以 g 得 (a/g)x + (b/g)y = c/g，其中 gcd(a/g, b/g) = 1。

4. **以擴展歐幾里得算法尋特解**：
   - 由回代表 1 = (a/g)*s + (b/g)*t。
   - 乘以 c/g：(c/g) = (a/g)*(s*c/g) + (b/g)*(t*c/g)。
   - 特解：x0 = s * (c/g)、y0 = t * (c/g)。

5. **書通解**：
   - x = x0 + (b/g)*k
   - y = y0 - (a/g)*k
   - 於所有整數 k。

6. **施約束**（若需正解）：
   - 解 x0 + (b/g)*k > 0 與 y0 - (a/g)*k > 0 求 k。
   - 報有效 k 值之範圍或述無正解存。

**例（15x + 21y = 39）：**
```text
gcd(15, 21) = 3. Does 3 | 39? Yes.
Simplify: 5x + 7y = 13.
Extended Euclidean: 1 = 3*5 - 2*7.
Multiply by 13: 13 = 39*5 - 26*7.
Particular: x0 = 39, y0 = -26.
General: x = 39 + 7k, y = -26 - 5k, k in Z.
Check (k=0): 5*39 + 7*(-26) = 195 - 182 = 13. Correct.
```

**預期：** 以整數 k 參數化之通解族，附特解之驗。

**失敗時：** 若特解誤，逐步再檢擴展歐幾里得之回代。最常之誤為符號誤。驗：a * x0 + b * y0 當確等於 c（非僅某模之下）。

### 步驟三：解 Pell 方程（若類為 Pell）

解 x^2 - Dy^2 = 1，D 為正非平方整數。

1. **驗 D 非完全平方**：若 D = k^2，則 x^2 - k^2*y^2 = (x - ky)(x + ky) = 1，迫 x - ky = x + ky = +/-1，得 y = 0、x = +/-1（瑣）。方程唯於非平方 D 方有趣。

2. **算 sqrt(D) 之連分數展開**：
   - 初：a0 = floor(sqrt(D))、m0 = 0、d0 = 1。
   - 迭：m_{i+1} = d_i * a_i - m_i、d_{i+1} = (D - m_{i+1}^2) / d_i、a_{i+1} = floor((a0 + m_{i+1}) / d_{i+1})。
   - 續至 a_i 之序重（展開於 a0 後週期）。
   - 記週期長 r。

3. **自收斂子抽基本解**：
   - 算連分數之收斂子 p_i / q_i。
   - 收斂子 p_{r-1} / q_{r-1}（首週期之末）予基本解：
     - 若 r 偶：(x1, y1) = (p_{r-1}, q_{r-1}) 解 x^2 - Dy^2 = 1。
     - 若 r 奇：(p_{r-1}, q_{r-1}) 解 x^2 - Dy^2 = -1（負 Pell 方程）。則 (p_{2r-1}, q_{2r-1}) 解正方程。

4. **自基本解 (x1, y1) 生他解**：
   - 遞推：x_{n+1} + y_{n+1} * sqrt(D) = (x1 + y1 * sqrt(D))^{n+1}。
   - 等價：x_{n+1} = x1 * x_n + D * y1 * y_n、y_{n+1} = x1 * y_n + y1 * x_n。

5. **呈**基本解與生諸解之遞推。

**小 D 之基本解：**

| D  | (x1, y1) | D  | (x1, y1)   | D  | (x1, y1)   |
|---|---|---|---|---|---|
| 2  | (3, 2)   | 7  | (8, 3)      | 13 | (649, 180)  |
| 3  | (2, 1)   | 8  | (3, 1)      | 14 | (15, 4)     |
| 5  | (9, 4)   | 10 | (19, 6)     | 15 | (4, 1)      |
| 6  | (5, 2)   | 11 | (10, 3)     | 17 | (33, 8)     |

**預期：** 基本解 (x1, y1) 以代入驗，及生所有正解之遞推。

**失敗時：** 若連分數算不收於週期，檢迭公式。週期長 r 可大（如 D = 61 有 r = 11 且基本解 (1766319049, 226153980)）。於大 D，用計算工具而非手算。

### 步驟四：施模約束以證存/不存（若類為一般二次或高階）

證方程無整數解，以示模阻。

1. **擇模數 m**（典型 m = 2、3、4、5、7、8 或 16）。

2. **列所有餘**：算左式 mod m 於變元之所有可能餘。

3. **察是否有組合得所需之右式 mod m**。
   - 若無組合合，則方程無解（模阻）。

4. **常阻**：
   - **mod 4 之平方**：n^2 = 0 或 1 (mod 4)。故 x^2 + y^2 = c 若 c = 3 (mod 4) 則無解。
   - **mod 8 之平方**：n^2 = 0、1 或 4 (mod 8)。故 x^2 + y^2 + z^2 = c 若 c = 7 (mod 8) 則無解。
   - **mod 9 之立方**：n^3 = 0、1 或 8 (mod 9)。故 x^3 + y^3 + z^3 = c 於某 c mod 9 可阻。

5. **若未尋阻**，模法不能證不存。解或存或不存；試構造法或下降。

**二次剩餘參考：**

| Mod | 平方（剩餘）               |
|---|---|
| 3   | {0, 1}                    |
| 4   | {0, 1}                    |
| 5   | {0, 1, 4}                |
| 7   | {0, 1, 2, 4}             |
| 8   | {0, 1, 4}                |
| 11  | {0, 1, 3, 4, 5, 9}       |
| 13  | {0, 1, 3, 4, 9, 10, 12}  |
| 16  | {0, 1, 4, 9}             |

**預期：** 或以模阻證不存，或述所測之模未尋阻。

**失敗時：** 若模法不決，試無窮下降：假解存，推一嚴格更小之解，反復至與正性矛盾。此技於證 x^4 + y^4 = z^2 無非瑣解為古典。

### 步驟五：自基本解生解族

以基本解與整數參數表所有解。

1. **線性方程**：族為 x = x0 + (b/g)*k、y = y0 - (a/g)*k（自步驟二）。

2. **Pell 方程**：以步驟三之遞推生首數解：
   ```text
   (x1, y1), (x2, y2), (x3, y3), ...
   ```
   列至少 3-5 解為合理性檢。

3. **畢氏三元組**：自參數 m > n > 0、gcd(m, n) = 1、m - n 奇生原三元組：
   - a = m^2 - n^2、b = 2mn、c = m^2 + n^2。
   - 所有原三元組皆此生（至換 a 與 b）。

4. **一般族**：若可，以參數式表解。若方程定 genus 0 之曲線，有有理參數化。若 genus >= 1，或有有限解（genus >= 2 之 Faltings 定理）。

5. **驗**至少 3 族員以代入原方程。

**例（Pell，D = 2）：**
```text
Fundamental: (x1, y1) = (3, 2). Check: 9 - 2*4 = 1. Correct.
(x2, y2) = (3*3 + 2*2*2, 3*2 + 2*3) = (17, 12). Check: 289 - 2*144 = 1.
(x3, y3) = (3*17 + 2*2*12, 3*12 + 2*17) = (99, 70). Check: 9801 - 2*4900 = 1.
```

**預期：** 所有解之參數或遞歸述，至少 3 解已驗。

**失敗時：** 若所生之解驗敗，則基本解或遞推公式誤。於 Pell 方程，自連分數再推基本解。於線性方程，再檢擴展歐幾里得之算。

## 驗證

- [ ] 方程已按類正分（線性、Pell、畢氏、一般二次、高階）
- [ ] 線性方程：解前已檢 gcd(a, b) | c
- [ ] 擴展歐幾里得之回代已驗：a*x0 + b*y0 = c 確等
- [ ] 通解含所有解（以整數 k 或遞推參數化）
- [ ] Pell：施連分數法前 D 已驗為非平方
- [ ] Pell：基本解以直算滿足 x1^2 - D*y1^2 = 1
- [ ] 模阻證列所有餘組合，非僅一些
- [ ] 任解族之至少 3 員以代入驗
- [ ] 約束（正整數、有界範圍）於尋通解後施
- [ ] 不存之宣以 gcd 條件或模阻證

## 常見陷阱

- **假 gcd | c 之方程皆有正解**：通解 x = x0 + (b/g)*k 含負值。正解即於方程於所有整數可解時亦或不存。

- **混 x^2 - Dy^2 = 1 與 x^2 - Dy^2 = -1**：負 Pell 方程唯於連分數週期長為奇時有解。施正方程公式於負方程標致誤結。

- **忘 Pell 方程之瑣解**：(x, y) = (1, 0) 恒滿足 x^2 - Dy^2 = 1，然於生非瑣解無用。基本解為 y > 0 之*最小*解。

- **模阻不全**：僅檢 mod 2 或 mod 4 或漏高模所見之阻。若首數模示無阻，試 mod 8、9、16 或二次型之判別式。

- **連分數週期之差一**：收斂子索引須謹追。基本解自 p_{r-1}/q_{r-1} 而非 p_r/q_r，r 為週期長。

- **下降無基情**：以下降證不存時，必示下降終於矛盾（如 x = 0 與 x > 0 矛盾）。無此基情則論不全。

- **誤施費馬大定理**：x^n + y^n = z^n 於 n > 2 無非瑣整數解（Wiles, 1995），然此不適於異係之方程如 2x^3 + 3y^3 = z^3。

## 相關技能

- `analyze-prime-numbers` — 分解與 gcd 算為丟番圖解之前置
- `solve-modular-arithmetic` — 線性同餘 ax = c (mod b) 等價於線性丟番圖方程
- `derive-theoretical-result` — 證丟番圖不可能結果之形式推導技

