Explore Diophantine Equations
Solve Diophantine equations — polynomial w/ integer-only solutions. Classify by type, test solvability, find particular + general, generate families. Linear, Pell, Pythagorean, general quadratic.
Use When
- All integer solutions ax + by = c
- Pell's x^2 - Dy^2 = 1 (or = -1)
- Pythagorean triples or parametric families
- Prove no integer solutions (modular constraints)
- Test solvability general quadratic Diophantine
- Fundamental solution from which all others generate
In
- Required: Equation explicit form (e.g., 3x + 5y = 17 or x^2 - 7y^2 = 1)
- Optional: Find all solutions, 1 particular, or prove non-existence
- Optional: Constraints (positive integers only)
- Optional: Express general parametrically
- Optional: Proof technique (constructive, descent, modular obstruction)
Do
Step 1: Classify
Determine structure → select method.
Linear: ax + by = c (a, b, c integers, x, y unknown).
- Method: Extended Euclidean.
Pell: x^2 - Dy^2 = 1 (or -1, or N) (D positive non-square).
- Method: Continued fraction of sqrt(D).
Pythagorean: x^2 + y^2 = z^2.
- Method: Parametric x = m^2 - n^2, y = 2mn, z = m^2 + n^2.
General quadratic: ax^2 + bxy + cy^2 + dx + ey + f = 0.
- Method: Complete square, reduce to Pell or simpler, or modular constraints.
Higher-order/special: Fermat-type (x^n + y^n = z^n, n > 2), sum of squares, other.
- Method: Modular obstruction, descent, known impossibility.
Record classification + method.
→ Precise classification + strategy.
If err: no standard type → try substitution/transformation to known form. x^2 + y^2 + z^2 = n via Legendre's 3-square. No reduction → modular (Step 4).
Step 2: Linear Diophantine (if linear)
Solve ax + by = c for integer x, y.
Compute g = gcd(a, b) via Euclidean.
Test: Solutions iff g | c.
- g !| c → prove non-existence: "gcd(a, b) = g, g doesn't divide c → no integer solutions."
- Stop.
Simplify: Divide by g → (a/g)x + (b/g)y = c/g, gcd(a/g, b/g) = 1.
Particular via extended Euclidean:
- 1 = (a/g)*s + (b/g)*t via back-substitution.
- Multiply c/g: (c/g) = (a/g)(sc/g) + (b/g)(tc/g).
- Particular: x0 = s * (c/g), y0 = t * (c/g).
General:
- x = x0 + (b/g)*k
- y = y0 - (a/g)*k
- All integers k.
Apply constraints (positive solutions):
- Solve x0 + (b/g)*k > 0 + y0 - (a/g)*k > 0 for k.
- Range valid k or state no positive.
Example (15x + 21y = 39):
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.
→ General family (x, y) parameterized by k + verified particular.
If err: particular wrong → re-check extended Euclidean back-sub step-by-step. Common: sign mistake. Verify: a * x0 + b * y0 = c exactly (not modulo).
Step 3: Pell (if Pell)
Solve x^2 - Dy^2 = 1 (D positive non-square).
Verify D non-square: D = k^2 → x^2 - k^2*y^2 = (x - ky)(x + ky) = 1 → x - ky = x + ky = ±1 → y = 0, x = ±1 (trivial). Only interesting non-square D.
Continued fraction sqrt(D):
- Init: a0 = floor(sqrt(D)), m0 = 0, d0 = 1.
- Iterate: 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}).
- Until sequence a_i repeats (periodic after a0).
- Record period r.
Fundamental from convergents:
- Compute p_i / q_i.
- p_{r-1} / q_{r-1} (end of 1st period) → fundamental:
- r even: (x1, y1) = (p_{r-1}, q_{r-1}) solves x^2 - Dy^2 = 1.
- r odd: (p_{r-1}, q_{r-1}) solves x^2 - Dy^2 = -1 (negative Pell). (p_{2r-1}, q_{2r-1}) solves positive.
Further solutions from (x1, y1):
- Recurrence: x_{n+1} + y_{n+1} * sqrt(D) = (x1 + y1 * sqrt(D))^{n+1}.
- Equiv: x_{n+1} = x1 * x_n + D * y1 * y_n, y_{n+1} = x1 * y_n + y1 * x_n.
Present fundamental + recurrence.
Fundamentals small 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) |
→ Fundamental (x1, y1) verified by substitution + recurrence.
If err: continued fraction no converge to period → check iteration. Period r can be large (D = 61 → r = 11, fundamental (1766319049, 226153980)). Large D → computational tools not manual.
Step 4: Modular Constraints (general quadratic/higher)
Prove no integer solutions via modular obstruction.
Choose modulus m (typ 2, 3, 4, 5, 7, 8, 16).
Enumerate residues: Compute LHS mod m for all possible var residues.
Check combination gives RHS mod m.
- None works → no solution (obstruction).
Common obstructions:
- Squares mod 4: n^2 = 0 or 1 (mod 4). x^2 + y^2 = c no solution if c = 3 (mod 4).
- Squares mod 8: n^2 = 0, 1, 4 (mod 8). x^2 + y^2 + z^2 = c no solution if c = 7 (mod 8).
- Cubes mod 9: n^3 = 0, 1, 8 (mod 9). x^3 + y^3 + z^3 = c may obstruct certain c mod 9.
No obstruction found → modular can't prove non-existence. Solutions may or may not → constructive or descent.
Quadratic residues ref:
| Mod |
Squares (residues) |
| 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} |
→ Proof non-existence or statement no obstruction at tested moduli.
If err: modular inconclusive → infinite descent: assume solution, derive strictly smaller, repeat → contradict positivity. Classic for x^4 + y^4 = z^2 no non-trivial.
Step 5: Generate Families
Express all solutions via fundamental + integer params.
Linear: x = x0 + (b/g)*k, y = y0 - (a/g)*k (Step 2).
Pell: Recurrence Step 3 → first several:
(x1, y1), (x2, y2), (x3, y3), ...
List ≥3-5 as sanity check.
Pythagorean: Primitive triples from m > n > 0, gcd(m, n) = 1, m - n odd:
- a = m^2 - n^2, b = 2mn, c = m^2 + n^2.
- All primitives arise (up to swap a, b).
General: Parametric if possible. Curve genus 0 → rational parametrization. Genus ≥1 → may be finitely many (Faltings for genus ≥ 2).
Verify ≥3 family members by substitution.
Example (Pell, D = 2):
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.
→ Parametric/recursive all solutions + ≥3 verified.
If err: generated fail verification → fundamental or recurrence wrong. Pell → re-derive fundamental from continued fraction. Linear → re-check extended Euclidean.
Check
Traps
- Assume gcd | c → positive solutions: General x = x0 + (b/g)*k includes negatives. Positive may not exist even solvable over integers.
- Confuse x^2 - Dy^2 = 1 vs -1: Negative Pell has solutions only when continued fraction period odd. Applying positive formula to negative target → wrong.
- Forget trivial Pell: (x, y) = (1, 0) always satisfies x^2 - Dy^2 = 1 but useless generating non-trivial. Fundamental = smallest w/ y > 0.
- Incomplete modular obstruction: Only mod 2/4 may miss higher. First few no obstruction → try 8, 9, 16, or discriminant.
- Off-by-one continued fraction period: Convergent indices tracked. Fundamental from p_{r-1}/q_{r-1} where r = period, not p_r/q_r.
- Descent w/o base case: Must show descent terminates contradiction (x = 0 contradicts x > 0). Without base → incomplete.
- Fermat's Last Thm wrong: x^n + y^n = z^n no non-trivial for n > 2 (Wiles, 1995), but not applies diff coefficients like 2x^3 + 3y^3 = z^3.
→
analyze-prime-numbers — Factorization + gcd prereqs
solve-modular-arithmetic — Linear congruences ax = c (mod b) equiv to linear Diophantine
derive-theoretical-result — Formal derivation for Diophantine impossibility
1---2name: explore-diophantine-equations-103description: 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.4license: MIT5---67# Explore Diophantine Equations89Solve Diophantine equations — polynomial w/ integer-only solutions. Classify by type, test solvability, find particular + general, generate families. Linear, Pell, Pythagorean, general quadratic.1011## Use When1213- All integer solutions ax + by = c14- Pell's x^2 - Dy^2 = 1 (or = -1)15- Pythagorean triples or parametric families16- Prove no integer solutions (modular constraints)17- Test solvability general quadratic Diophantine18- Fundamental solution from which all others generate1920## In2122- **Required**: Equation explicit form (e.g., 3x + 5y = 17 or x^2 - 7y^2 = 1)23- **Optional**: Find all solutions, 1 particular, or prove non-existence24- **Optional**: Constraints (positive integers only)25- **Optional**: Express general parametrically26- **Optional**: Proof technique (constructive, descent, modular obstruction)2728## Do2930### Step 1: Classify3132Determine structure → select method.33341. **Linear**: ax + by = c (a, b, c integers, x, y unknown).35 - Method: Extended Euclidean.36372. **Pell**: x^2 - Dy^2 = 1 (or -1, or N) (D positive non-square).38 - Method: Continued fraction of sqrt(D).39403. **Pythagorean**: x^2 + y^2 = z^2.41 - Method: Parametric x = m^2 - n^2, y = 2mn, z = m^2 + n^2.42434. **General quadratic**: ax^2 + bxy + cy^2 + dx + ey + f = 0.44 - Method: Complete square, reduce to Pell or simpler, or modular constraints.45465. **Higher-order/special**: Fermat-type (x^n + y^n = z^n, n > 2), sum of squares, other.47 - Method: Modular obstruction, descent, known impossibility.4849Record classification + method.5051→ Precise classification + strategy.5253If err: no standard type → try substitution/transformation to known form. x^2 + y^2 + z^2 = n via Legendre's 3-square. No reduction → modular (Step 4).5455### Step 2: Linear Diophantine (if linear)5657Solve ax + by = c for integer x, y.58591. **Compute g = gcd(a, b)** via Euclidean.60612. **Test**: Solutions iff g | c.62 - g !| c → prove non-existence: "gcd(a, b) = g, g doesn't divide c → no integer solutions."63 - Stop.64653. **Simplify**: Divide by g → (a/g)x + (b/g)y = c/g, gcd(a/g, b/g) = 1.66674. **Particular via extended Euclidean**:68 - 1 = (a/g)*s + (b/g)*t via back-substitution.69 - Multiply c/g: (c/g) = (a/g)*(s*c/g) + (b/g)*(t*c/g).70 - Particular: x0 = s * (c/g), y0 = t * (c/g).71725. **General**:73 - x = x0 + (b/g)*k74 - y = y0 - (a/g)*k75 - All integers k.76776. **Apply constraints** (positive solutions):78 - Solve x0 + (b/g)*k > 0 + y0 - (a/g)*k > 0 for k.79 - Range valid k or state no positive.8081**Example (15x + 21y = 39):**82```text83gcd(15, 21) = 3. Does 3 | 39? Yes.84Simplify: 5x + 7y = 13.85Extended Euclidean: 1 = 3*5 - 2*7.86Multiply by 13: 13 = 39*5 - 26*7.87Particular: x0 = 39, y0 = -26.88General: x = 39 + 7k, y = -26 - 5k, k in Z.89Check (k=0): 5*39 + 7*(-26) = 195 - 182 = 13. Correct.90```9192→ General family (x, y) parameterized by k + verified particular.9394If err: particular wrong → re-check extended Euclidean back-sub step-by-step. Common: sign mistake. Verify: a * x0 + b * y0 = c exactly (not modulo).9596### Step 3: Pell (if Pell)9798Solve x^2 - Dy^2 = 1 (D positive non-square).991001. **Verify D non-square**: D = k^2 → x^2 - k^2*y^2 = (x - ky)(x + ky) = 1 → x - ky = x + ky = ±1 → y = 0, x = ±1 (trivial). Only interesting non-square D.1011022. **Continued fraction sqrt(D)**:103 - Init: a0 = floor(sqrt(D)), m0 = 0, d0 = 1.104 - Iterate: 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}).105 - Until sequence a_i repeats (periodic after a0).106 - Record period r.1071083. **Fundamental from convergents**:109 - Compute p_i / q_i.110 - p_{r-1} / q_{r-1} (end of 1st period) → fundamental:111 - r even: (x1, y1) = (p_{r-1}, q_{r-1}) solves x^2 - Dy^2 = 1.112 - r odd: (p_{r-1}, q_{r-1}) solves x^2 - Dy^2 = -1 (negative Pell). (p_{2r-1}, q_{2r-1}) solves positive.1131144. **Further solutions** from (x1, y1):115 - Recurrence: x_{n+1} + y_{n+1} * sqrt(D) = (x1 + y1 * sqrt(D))^{n+1}.116 - Equiv: x_{n+1} = x1 * x_n + D * y1 * y_n, y_{n+1} = x1 * y_n + y1 * x_n.1171185. **Present** fundamental + recurrence.119120**Fundamentals small D:**121122| D | (x1, y1) | D | (x1, y1) | D | (x1, y1) |123|---|---|---|---|---|---|124| 2 | (3, 2) | 7 | (8, 3) | 13 | (649, 180) |125| 3 | (2, 1) | 8 | (3, 1) | 14 | (15, 4) |126| 5 | (9, 4) | 10 | (19, 6) | 15 | (4, 1) |127| 6 | (5, 2) | 11 | (10, 3) | 17 | (33, 8) |128129→ Fundamental (x1, y1) verified by substitution + recurrence.130131If err: continued fraction no converge to period → check iteration. Period r can be large (D = 61 → r = 11, fundamental (1766319049, 226153980)). Large D → computational tools not manual.132133### Step 4: Modular Constraints (general quadratic/higher)134135Prove no integer solutions via modular obstruction.1361371. **Choose modulus m** (typ 2, 3, 4, 5, 7, 8, 16).1381392. **Enumerate residues**: Compute LHS mod m for all possible var residues.1401413. **Check combination gives RHS mod m**.142 - None works → no solution (obstruction).1431444. **Common obstructions**:145 - **Squares mod 4**: n^2 = 0 or 1 (mod 4). x^2 + y^2 = c no solution if c = 3 (mod 4).146 - **Squares mod 8**: n^2 = 0, 1, 4 (mod 8). x^2 + y^2 + z^2 = c no solution if c = 7 (mod 8).147 - **Cubes mod 9**: n^3 = 0, 1, 8 (mod 9). x^3 + y^3 + z^3 = c may obstruct certain c mod 9.1481495. **No obstruction found** → modular can't prove non-existence. Solutions may or may not → constructive or descent.150151**Quadratic residues ref:**152153| Mod | Squares (residues) |154|---|---|155| 3 | {0, 1} |156| 4 | {0, 1} |157| 5 | {0, 1, 4} |158| 7 | {0, 1, 2, 4} |159| 8 | {0, 1, 4} |160| 11 | {0, 1, 3, 4, 5, 9} |161| 13 | {0, 1, 3, 4, 9, 10, 12} |162| 16 | {0, 1, 4, 9} |163164→ Proof non-existence or statement no obstruction at tested moduli.165166If err: modular inconclusive → infinite descent: assume solution, derive strictly smaller, repeat → contradict positivity. Classic for x^4 + y^4 = z^2 no non-trivial.167168### Step 5: Generate Families169170Express all solutions via fundamental + integer params.1711721. **Linear**: x = x0 + (b/g)*k, y = y0 - (a/g)*k (Step 2).1731742. **Pell**: Recurrence Step 3 → first several:175 ```text176 (x1, y1), (x2, y2), (x3, y3), ...177 ```178 List ≥3-5 as sanity check.1791803. **Pythagorean**: Primitive triples from m > n > 0, gcd(m, n) = 1, m - n odd:181 - a = m^2 - n^2, b = 2mn, c = m^2 + n^2.182 - All primitives arise (up to swap a, b).1831844. **General**: Parametric if possible. Curve genus 0 → rational parametrization. Genus ≥1 → may be finitely many (Faltings for genus ≥ 2).1851865. **Verify** ≥3 family members by substitution.187188**Example (Pell, D = 2):**189```text190Fundamental: (x1, y1) = (3, 2). Check: 9 - 2*4 = 1. Correct.191(x2, y2) = (3*3 + 2*2*2, 3*2 + 2*3) = (17, 12). Check: 289 - 2*144 = 1.192(x3, y3) = (3*17 + 2*2*12, 3*12 + 2*17) = (99, 70). Check: 9801 - 2*4900 = 1.193```194195→ Parametric/recursive all solutions + ≥3 verified.196197If err: generated fail verification → fundamental or recurrence wrong. Pell → re-derive fundamental from continued fraction. Linear → re-check extended Euclidean.198199## Check200201- [ ] Correctly classified (linear, Pell, Pythagorean, general quadratic, higher-order)202- [ ] Linear: gcd(a, b) | c checked before solve203- [ ] Extended Euclidean back-sub verified: a*x0 + b*y0 = c exactly204- [ ] General includes all (parameterized k or recurrence)205- [ ] Pell: D verified non-square before continued fraction206- [ ] Pell: fundamental satisfies x1^2 - D*y1^2 = 1 direct computation207- [ ] Modular obstruction proofs enumerate all residues208- [ ] ≥3 family members verified substitution209- [ ] Constraints applied after general210- [ ] Non-existence claims justified by gcd or modular211212## Traps213214- **Assume gcd | c → positive solutions**: General x = x0 + (b/g)*k includes negatives. Positive may not exist even solvable over integers.215- **Confuse x^2 - Dy^2 = 1 vs -1**: Negative Pell has solutions only when continued fraction period odd. Applying positive formula to negative target → wrong.216- **Forget trivial Pell**: (x, y) = (1, 0) always satisfies x^2 - Dy^2 = 1 but useless generating non-trivial. Fundamental = *smallest* w/ y > 0.217- **Incomplete modular obstruction**: Only mod 2/4 may miss higher. First few no obstruction → try 8, 9, 16, or discriminant.218- **Off-by-one continued fraction period**: Convergent indices tracked. Fundamental from p_{r-1}/q_{r-1} where r = period, not p_r/q_r.219- **Descent w/o base case**: Must show descent terminates contradiction (x = 0 contradicts x > 0). Without base → incomplete.220- **Fermat's Last Thm wrong**: x^n + y^n = z^n no non-trivial for n > 2 (Wiles, 1995), but not applies diff coefficients like 2x^3 + 3y^3 = z^3.221222## →223224- `analyze-prime-numbers` — Factorization + gcd prereqs225- `solve-modular-arithmetic` — Linear congruences ax = c (mod b) equiv to linear Diophantine226- `derive-theoretical-result` — Formal derivation for Diophantine impossibility