Explore Diophantine Equations

---
name: explore-diophantine-equations
description: >
  Diophantische Gleichungen (nur ganzzahlige Loesungen) einschliesslich linearer,
  quadratischer und Pell-Gleichungen loesen. Umfasst den erweiterten Euklidischen
  Algorithmus, Abstiegsmethoden und Existenzbeweise. Verwenden beim Finden aller
  ganzzahligen Loesungen von ax + by = c, beim Loesen der Pell-Gleichung, beim
  Generieren Pythagoreischer Tripel, beim Beweisen, dass keine ganzzahligen
  Loesungen existieren ueber modulare Einschraenkungen, oder beim Finden der
  Fundamentalloesung, aus der alle anderen erzeugt werden.
license: MIT
allowed-tools: Read Bash
metadata:
  author: Philipp Thoss
  version: "1.0"
  domain: number-theory
  complexity: advanced
  language: multi
  tags: number-theory, diophantine, integer-solutions, pell-equation, euclidean
  locale: de
  source_locale: en
  source_commit: 33b561c9
  fence_basis_commit: 33b561c9
  translator: claude
  translation_date: "2026-03-17"
---

# Diophantische Gleichungen erkunden

Diophantische Gleichungen loesen -- Polynomgleichungen, bei denen nur ganzzahlige Loesungen gesucht werden. Die Gleichung nach Typ klassifizieren, auf Loesbarkeit testen, partikulaere und allgemeine Loesungen finden und Loesungsfamilien erzeugen. Umfasst lineare Gleichungen, Pell-Gleichungen, Pythagoreische Tripel und allgemeine quadratische Formen.

## Wann verwenden

- Alle ganzzahligen Loesungen einer linearen Gleichung ax + by = c finden
- Die Pell-Gleichung x^2 - Dy^2 = 1 (oder = -1) loesen
- Pythagoreische Tripel oder andere parametrische ganzzahlige Familien erzeugen
- Beweisen, dass eine gegebene Gleichung keine ganzzahligen Loesungen hat (ueber modulare Einschraenkungen)
- Loesbarkeit einer allgemeinen quadratischen diophantischen Gleichung testen
- Die Fundamentalloesung finden, aus der alle anderen erzeugt werden

## Eingaben

- **Erforderlich**: Die zu loesende diophantische Gleichung (in expliziter Form, z.B. 3x + 5y = 17 oder x^2 - 7y^2 = 1)
- **Optional**: Ob alle Loesungen gefunden, nur eine partikulaere Loesung bestimmt oder Nichtexistenz bewiesen werden soll
- **Optional**: Einschraenkungen fuer Variablenbereiche (z.B. nur positive ganze Zahlen)
- **Optional**: Ob die allgemeine Loesung parametrisch ausgedrueckt werden soll
- **Optional**: Bevorzugte Beweistechnik (konstruktiv, Abstieg, modulare Obstruktion)

## Vorgehensweise

### Schritt 1: Gleichungstyp klassifizieren

Die Struktur der diophantischen Gleichung bestimmen, um die geeignete Loesungsmethode auszuwaehlen.

1. **Linear**: ax + by = c wobei a, b, c gegebene ganze Zahlen und x, y Unbekannte sind.
   - Loesungsmethode: Erweiterter Euklidischer Algorithmus.

2. **Pell-Gleichung**: x^2 - Dy^2 = 1 (oder = -1, oder = N) wobei D eine positive nicht-quadratische ganze Zahl ist.
   - Loesungsmethode: Kettenbruchentwicklung von sqrt(D).

3. **Pythagoreisch**: x^2 + y^2 = z^2.
   - Loesungsmethode: Parametrische Familie x = m^2 - n^2, y = 2mn, z = m^2 + n^2.

4. **Allgemein quadratisch**: ax^2 + bxy + cy^2 + dx + ey + f = 0.
   - Loesungsmethode: Quadratische Ergaenzung, auf Pell oder einfachere Form reduzieren, oder modulare Einschraenkungen anwenden.

5. **Hoehere Ordnung oder speziell**: Fermat-Typ (x^n + y^n = z^n fuer n > 2), Quadratsummen oder andere.
   - Loesungsmethode: Modulare Obstruktion, Abstieg oder bekannte Unmoeglichkeitsergebnisse.

Klassifikation und gewaehlte Methode festhalten.

**Erwartet:** Eine praezise Klassifikation mit identifizierter Loesungsstrategie.

**Bei Fehler:** Wenn die Gleichung keinem Standardtyp entspricht, Substitution oder Transformation versuchen, um sie auf eine bekannte Form zu reduzieren. Zum Beispiel kann x^2 + y^2 + z^2 = n ueber Legendres Drei-Quadrate-Theorem angegangen werden. Wenn keine Reduktion erkennbar ist, modulare Einschraenkungen (Schritt 4) zur Pruefung auf Obstruktionen anwenden.

### Schritt 2: Lineare diophantische Gleichungen loesen (wenn Typ = linear)

ax + by = c fuer ganzzahlige x, y loesen.

1. **g = ggT(a, b) berechnen** mit dem Euklidischen Algorithmus.

2. **Loesbarkeit testen**: Loesungen existieren genau dann, wenn g | c.
   - Wenn g nicht c teilt, Nichtexistenz beweisen: "Da ggT(a, b) = g und g nicht c teilt, hat die Gleichung ax + by = c keine ganzzahligen Loesungen."
   - Stoppen, wenn keine Loesung existiert.

3. **Vereinfachen**: Durch g teilen um (a/g)x + (b/g)y = c/g zu erhalten, wobei nun ggT(a/g, b/g) = 1.

4. **Partikulaere Loesung finden** mit dem erweiterten Euklidischen Algorithmus:
   - 1 = (a/g)*s + (b/g)*t ueber Rueckwaertssubstitution ausdruecken.
   - Mit c/g multiplizieren: (c/g) = (a/g)*(s*c/g) + (b/g)*(t*c/g).
   - Partikulaere Loesung: x0 = s * (c/g), y0 = t * (c/g).

5. **Allgemeine Loesung aufschreiben**:
   - x = x0 + (b/g)*k
   - y = y0 - (a/g)*k
   - fuer alle ganzen Zahlen k.

6. **Einschraenkungen anwenden** (wenn positive Loesungen erforderlich):
   - x0 + (b/g)*k > 0 und y0 - (a/g)*k > 0 nach k loesen.
   - Den Bereich gueltiger k-Werte angeben oder feststellen, dass keine positive Loesung existiert.

**Beispiel (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.
```

**Erwartet:** Die allgemeine Loesungsfamilie (x, y) parametrisiert durch eine ganze Zahl k, mit Verifikation der partikulaeren Loesung.

**Bei Fehler:** Wenn die partikulaere Loesung falsch ist, die erweiterte Euklidische Rueckwaertssubstitution Schritt fuer Schritt nochmals pruefen. Der haeufigste Fehler ist ein Vorzeichenfehler. Verifizieren: a * x0 + b * y0 muss exakt c ergeben (nicht nur modulo etwas).

### Schritt 3: Pell-Gleichungen loesen (wenn Typ = Pell)

x^2 - Dy^2 = 1 loesen, wobei D eine positive nicht-quadratische ganze Zahl ist.

1. **Verifizieren, dass D kein perfektes Quadrat ist**: Falls D = k^2, dann x^2 - k^2*y^2 = (x - ky)(x + ky) = 1, was x - ky = x + ky = +/-1 erzwingt und y = 0, x = +/-1 ergibt (trivial). Die Gleichung ist nur fuer nicht-quadratisches D interessant.

2. **Kettenbruchentwicklung von sqrt(D) berechnen**:
   - Initialisieren: a0 = floor(sqrt(D)), m0 = 0, d0 = 1.
   - Iterieren: 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}).
   - Fortfahren bis sich die Folge der a_i wiederholt (die Entwicklung ist nach a0 periodisch).
   - Periodenlaenge r festhalten.

3. **Fundamentalloesung aus den Konvergenten extrahieren**:
   - Die Konvergenten p_i / q_i des Kettenbruchs berechnen.
   - Die Konvergente p_{r-1} / q_{r-1} (am Ende der ersten Periode) liefert die Fundamentalloesung:
     - Wenn r gerade: (x1, y1) = (p_{r-1}, q_{r-1}) loest x^2 - Dy^2 = 1.
     - Wenn r ungerade: (p_{r-1}, q_{r-1}) loest x^2 - Dy^2 = -1 (die negative Pell-Gleichung). Dann loest (p_{2r-1}, q_{2r-1}) die positive Gleichung.

4. **Weitere Loesungen erzeugen** aus der Fundamentalloesung (x1, y1):
   - Die Rekursion: x_{n+1} + y_{n+1} * sqrt(D) = (x1 + y1 * sqrt(D))^{n+1}.
   - Aequivalent: x_{n+1} = x1 * x_n + D * y1 * y_n, y_{n+1} = x1 * y_n + y1 * x_n.

5. Die Fundamentalloesung und die Rekursion zur Erzeugung aller Loesungen **praesentieren**.

**Fundamentalloesungen fuer kleine 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)     |

**Erwartet:** Die Fundamentalloesung (x1, y1) durch Einsetzen verifiziert, plus die Rekursion zur Erzeugung aller positiven Loesungen.

**Bei Fehler:** Wenn die Kettenbruchberechnung nicht zu einer Periode konvergiert, die Iterationsformel pruefen. Die Periodenlaenge r kann gross sein (z.B. hat D = 61 r = 11 und die Fundamentalloesung (1766319049, 226153980)). Fuer grosse D Rechenwerkzeuge anstatt manueller Berechnung verwenden.

### Schritt 4: Modulare Einschraenkungen fuer Existenz/Nichtexistenz anwenden (wenn Typ = allgemein quadratisch oder hoeher)

Beweisen, dass eine Gleichung keine ganzzahligen Loesungen hat, indem eine modulare Obstruktion gezeigt wird.

1. **Einen Modul m waehlen** (typischerweise m = 2, 3, 4, 5, 7, 8 oder 16).

2. **Alle Reste aufzaehlen**: Die linke Seite modulo m fuer alle moeglichen Reste der Variablen berechnen.

3. **Pruefen, ob irgendeine Kombination die erforderliche rechte Seite modulo m ergibt**.
   - Wenn keine Kombination funktioniert, hat die Gleichung keine Loesung (modulare Obstruktion).

4. **Haeufige Obstruktionen**:
   - **Quadrate mod 4**: n^2 = 0 oder 1 (mod 4). Also hat x^2 + y^2 = c keine Loesung wenn c = 3 (mod 4).
   - **Quadrate mod 8**: n^2 = 0, 1 oder 4 (mod 8). Also hat x^2 + y^2 + z^2 = c keine Loesung wenn c = 7 (mod 8).
   - **Kuben mod 9**: n^3 = 0, 1 oder 8 (mod 9). Also kann x^3 + y^3 + z^3 = c fuer bestimmte c mod 9 obstruiert sein.

5. **Wenn keine Obstruktion gefunden wird**, kann ein modularer Ansatz die Nichtexistenz nicht beweisen. Loesungen koennen existieren oder nicht; konstruktive Methoden oder Abstieg versuchen.

**Referenz quadratischer Reste:**

| Mod | Quadrate (Reste)           |
|---|---|
| 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}             |

**Erwartet:** Entweder ein Beweis der Nichtexistenz ueber modulare Obstruktion oder eine Feststellung, dass bei den getesteten Modulen keine Obstruktion gefunden wurde.

**Bei Fehler:** Wenn modulare Methoden ergebnislos sind, den unendlichen Abstieg versuchen: eine Loesung annehmen, eine strikt kleinere Loesung ableiten und wiederholen, bis ein Widerspruch zur Positivitaet erreicht wird. Diese Technik ist klassisch fuer den Beweis, dass x^4 + y^4 = z^2 keine nicht-trivialen Loesungen hat.

### Schritt 5: Loesungsfamilien aus der Fundamentalloesung erzeugen

Alle Loesungen in Bezug auf die Fundamentalloesung und ganzzahlige Parameter ausdruecken.

1. **Fuer lineare Gleichungen**: Die Familie ist x = x0 + (b/g)*k, y = y0 - (a/g)*k (aus Schritt 2).

2. **Fuer Pell-Gleichungen**: Die Rekursion aus Schritt 3 verwenden, um die ersten Loesungen zu erzeugen:
   ```text
   (x1, y1), (x2, y2), (x3, y3), ...
   ```
   Mindestens 3-5 Loesungen als Plausibilitaetspruefung auflisten.

3. **Fuer Pythagoreische Tripel**: Primitive Tripel aus Parametern m > n > 0, ggT(m, n) = 1, m - n ungerade erzeugen:
   - a = m^2 - n^2, b = 2mn, c = m^2 + n^2.
   - Alle primitiven Tripel entstehen so (bis auf Vertauschung von a und b).

4. **Fuer allgemeine Familien**: Loesungen wenn moeglich in parametrischer Form ausdruecken. Wenn die Gleichung eine Kurve vom Geschlecht 0 definiert, existiert eine rationale Parametrisierung. Bei Geschlecht >= 1 kann es endlich viele Loesungen geben (Satz von Faltings fuer Geschlecht >= 2).

5. Mindestens 3 Mitglieder der Familie durch Einsetzen in die Originalgleichung **verifizieren**.

**Beispiel (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.
```

**Erwartet:** Eine parametrische oder rekursive Beschreibung aller Loesungen, mit mindestens 3 verifizierten Loesungen.

**Bei Fehler:** Wenn erzeugte Loesungen die Verifikation nicht bestehen, ist die Fundamentalloesung oder die Rekursionsformel falsch. Fuer Pell-Gleichungen die Fundamentalloesung aus dem Kettenbruch neu ableiten. Fuer lineare Gleichungen die erweiterte Euklidische Berechnung nochmals pruefen.

## Validierung

- [ ] Gleichung ist korrekt nach Typ klassifiziert (linear, Pell, Pythagoreisch, allgemein quadratisch, hoehere Ordnung)
- [ ] Fuer lineare Gleichungen: ggT(a, b) | c wird vor dem Loesen geprueft
- [ ] Erweiterte Euklidische Rueckwaertssubstitution ist verifiziert: a*x0 + b*y0 = c exakt
- [ ] Allgemeine Loesung umfasst alle Loesungen (parametrisiert durch ganze Zahl k oder Rekursion)
- [ ] Fuer Pell: D ist als nicht-quadratisch verifiziert vor Anwendung der Kettenbruchmethode
- [ ] Fuer Pell: Fundamentalloesung erfuellt x1^2 - D*y1^2 = 1 durch direkte Berechnung
- [ ] Beweise modularer Obstruktion zaehlen alle Restkombinationen auf, nicht nur einige
- [ ] Mindestens 3 Mitglieder jeder Loesungsfamilie sind durch Einsetzen verifiziert
- [ ] Einschraenkungen (positive ganze Zahlen, begrenzter Bereich) werden nach Finden der allgemeinen Loesung angewendet
- [ ] Nichtexistenz-Behauptungen sind entweder durch ggT-Bedingung oder modulare Obstruktion gerechtfertigt

## Haeufige Stolperfallen

- **Annahme, dass alle Gleichungen mit ggT | c positive Loesungen haben**: Die allgemeine Loesung x = x0 + (b/g)*k schliesst negative Werte ein. Positive Loesungen existieren moeglicherweise nicht, selbst wenn die Gleichung ueber allen ganzen Zahlen loesbar ist.

- **Verwechslung von x^2 - Dy^2 = 1 mit x^2 - Dy^2 = -1**: Die negative Pell-Gleichung hat nur Loesungen, wenn die Kettenbruch-Periodenlaenge ungerade ist. Die Formel der positiven Gleichung auf ein negatives Gleichungsziel anzuwenden ergibt ein falsches Ergebnis.

- **Triviale Loesung der Pell-Gleichung vergessen**: (x, y) = (1, 0) erfuellt immer x^2 - Dy^2 = 1, ist aber nicht nuetzlich zur Erzeugung nicht-trivialer Loesungen. Die Fundamentalloesung ist die *kleinste* Loesung mit y > 0.

- **Unvollstaendige modulare Obstruktion**: Nur mod 2 oder mod 4 zu pruefen kann Obstruktionen uebersehen, die bei hoeheren Modulen sichtbar sind. Wenn die ersten Modulen keine Obstruktion zeigen, mod 8, 9, 16 oder die Diskriminante der quadratischen Form versuchen.

- **Off-by-one in der Kettenbruchperiode**: Die Konvergentenindizes muessen sorgfaeltig verfolgt werden. Die Fundamentalloesung kommt von p_{r-1}/q_{r-1} wobei r die Periodenlaenge ist, nicht von p_r/q_r.

- **Unendlicher Abstieg ohne Basisfall**: Beim Abstieg zum Beweis der Nichtexistenz muss gezeigt werden, dass der Abstieg bei einem Widerspruch terminiert (z.B. x = 0 widerspricht x > 0). Ohne diesen Basisfall ist das Argument unvollstaendig.

- **Fermats Letzten Satz falsch anwenden**: x^n + y^n = z^n hat keine nicht-trivialen ganzzahligen Loesungen fuer n > 2 (Wiles, 1995), aber dies gilt nicht fuer Gleichungen mit verschiedenen Koeffizienten wie 2x^3 + 3y^3 = z^3.

## Verwandte Skills

- `analyze-prime-numbers` -- Faktorisierung und ggT-Berechnung sind Voraussetzungen fuer diophantisches Loesen
- `solve-modular-arithmetic` -- Lineare Kongruenzen ax = c (mod b) sind aequivalent zu linearen diophantischen Gleichungen
- `derive-theoretical-result` -- Formale Ableitungstechniken zum Beweis diophantischer Unmoeglichkeitsergebnisse