diophantische gleichung lösen 35k+3l=1

Question

 

Hi,

mein Professor meinte in seinen Folien, dass man für den Chinesischen Restsatz Diophantische Gleichungen lösen muss. Er hat bei diesem Schritt nur das Ergebnis hingeschrieben (k1=2). Das bezieht sich jetzt auf 35k Kongruent 1(mod3). 

Wenn ich aber versuche diesen Ausdruck in eine Diophantische Gleichung umzuwandeln und das dann zu lösen, dann erhalte ich nur -1 und 12. Habe ich da einen Denkfehler eingebaut oder woran loegt das jetzt? :D

Wie kommt der auf die 2?

EDIT: Ich hoffe ihr kennt dieses Verfahren, ich beginne mit den Startwerten 1 und 0 und arbeite mich dann hoch.

Comments

Kommentar in Antwort umgewandelt.

Answer 1

Eine lineare Kongruenz ax ≡ b mod m hat d = ggT(a, m) Lösungen, wenn d ein Teiler von b ist.
35x ≡ 1 mod 3 hat eine Lösung, denn d = ggT(35, 3) = 1 und 1|1.
Die Lösung lässt sich hier glücklicherweise schnell durch Probieren finden
35·0 mod 3 = 0 ≠ 1
35·1 mod 3 = 2 ≠ 1
35·2 mod 3 = 1
Also ist x = 2 die einzige Lösung.

Wir hatten mal einen Algorithmus hergeleitet, wie man Lösungsmengen linearer Kongruenzen berechnet. Das führt zu der Gleichung(wie in deiner Mitschrift) 35s + 3t = 1 die man erst lösen muss, um daraus die Lösungsmenge zu bekommen. Die Diophantische Gleichung 35s + 3t = 1 können wir mit Hilfe des erweiterten Euklidischen Algorithmus lösen.

35s + 3t = 1
s,t = ?

35 = 11·3 + 2
3 = 1·2 + 1
2 = 2·1 + 0

2 = 35 - 11·3
1 = 3 - 1·2

1 = 3 - 1·(35 - 11·3)
1 = -1·35 + 12·3
s = -1, t = 12

x₀ = (s·d / b) mod (m / d)
x_i = x₀ + i·m / d für alle 1 <= i <= d-1

x₀ = -1·1 / 1 mod 3
x₀ = -1 mod 3
x₀ = 2

Grüße

Comments

Super! Willst Du nicht doch nochmal über eine YouTube-Karriere nachdenken ? :-)

---

Nööööööööööööööö

---

Hi,

achso funktioniert das :D Uns wurde nur dieses Tabellenverfahren gezeigt mit dem man dann auf die Lösungsmenge kommt, wie man dann aber z.B auf diese zwei kommen würde, wurde uns nie gezeigt.. Ohne deine Antwort wüsste ich das wahrscheinlich immer noch nicht :)

Hab jetzt einen besseren Durchblick, vielen Dank :)

---

Hab jetzt einen besseren Durchblick, vielen Dank :)
Gerne! :-)

Uns wurde nur dieses Tabellenverfahren gezeigt

Siehst du, das kenne ich widerum nicht. Wir hatten 'bloß' den Algorithmus hergeleitet

0. Eingabe: ax ≡ b mod m mit ggT(a,m) = d und d|b Ausgabe: Alle d Lösungen
1. Bestimme ganzzahlige s,t von a/d*s + m/d*t = 1
2. Setze x₀ = s*b/d mod m/d
3. Setze x_i = x₀ + i*m/d für alle 1<=i<=d-1, die Lösungen sind x₀, ... , x_d-1

Grüße

---

Mir hat das aber trotzdem geholfen. Kann man nichts machen mit der Tabelle, ist ein wenig aufwendiger hilft aber dabei den Überblick ein wenig zu behalten, gerade wenn man das alles zum ersten mal macht. 

Wir dürfen einen Zettel mit in die Klausur nehmen, vielleicht landet die Tabelle ja da drauf als kleine Randnotiz :D