Aufgabe 33 (b)

Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.

Aufgabe 33 (b)
Folgendes Kongruenzsystem soll man lösen:

19x ≡ 103 mod 900
10x ≡ 511 mod 841

Weiss jemand wie man dieses System löst?

Ich versteh nicht, wie man mit der 19 und der 10 vor dem x umgeht. Wenn ich diese Zahlen ignorier, komm ich natürlich auf ein Ergebnis. Multiplizier ich das aber mit 19 bzw. 10 stimmts nicht mehr. Diverse andere Varianten beim rumrechnen haben mich dem Ziel leider auch nicht näher gebracht.

lg Caro.

re
Multipliziers mal mit 19x10=190 :wink:
Dann müsste es eigentlich stimmen.
Achja: Ab Donnerstag wieder zusammen lernen?


Zwecks Donnerstag: ja, gern, schreib mir einfach durch, ab wann.

Zwecks Aufgabe: so ganz versteh ich das immer noch nicht, aber des kannst mir ja dann am Donnerstag zeigen :smiley:

Euch viel Glück bzw. Energie morgen bei der Prüfung.


wie lautet denn die Aufgabe genau?

also
19x ≡ 103 mod 900
kann ich lösen, da wäre x = 337.

ebenso die andere Gleichung, hab ich aber noch nicht gemacht.
Aber beide zusammen ist ne interessante Frage.


Lösung sollte sein:

x = 58837 mod 756900


Yep, hab ich auch.


@langermatze und emeran:

leider bin ich immer noch nicht weiter. Mag einer von euch beiden hier den Weg zu eurer Lösung beschreiben? Muss ich die Gleichung mit irgendwas multiplizieren oder ein neues Kongruenzsystem aufstellen? Ich steh vor einem großen Rätsel :-/ (Also wie man ein solches System löst, weiß ich schon, aber eben nicht, wenn vor dem x noch eine Zahl steht).

Vielen Dank schon mal :slight_smile:


Ich bin zwar weder noch, aber ich bin trotzdem mal so frei: :wink:

19x = 103 mod 900
10x = 511 mod 841

Wenn das mod nicht da wäre, würdest du als erstes die obere Gleichung durch 19 teilen und die untere durch 10. Hier das Gleiche, nur halt mit dem Inversen modulo 900 bzw. 841 multiplizieren. Also:
Erweiterten Euklid auf 841 und 10 und auf 900 und 19. Das gibt:
1841 - 84 * 10 = 1 und -8900 + 379 * 19
also ist das Inverse zu 19 mod 900 = 379 und das Inverse zu 10 mod 841 = -84 = 757.
Das liefert uns:
x = 379 * 103 mod 900
x = -84 * 511 mod 841
ausgerechnet und reduziert:
x = 337 mod 900
x = 808 mod 841

Und jetzt halt fröhlich den chinesischen Restsatz anwenden, was dann das obige Ergebnis liefern sollte.
Viel Spaß beim Rechnen…


Oh, super. Vielen Dank :smiley:

Endlich hab ichs verstanden.


Und das is Stoff vom 1. Semester gewesen ?