Mathematik online lernen im Mathe-Forum. Nachhilfe online
Startseite » Forum » Kongruenzsystem lösen

Kongruenzsystem lösen

Universität / Fachhochschule

Tags: Kongruenzsystem

 
Antworten Neue Frage stellen Im Forum suchen
Neue Frage
math-welt

math-welt aktiv_icon

12:55 Uhr, 27.11.2021

Antworten
Finden sie das kleinste positive xZ, das das folgende Kongruenzsystem erfüllt
(mit Rechenweg)

3xmod7=4

5xmod8=6

xmod9=5


kann mir bitte jemand die Lösungsweg etwas ausführlich erklären.

Für alle, die mir helfen möchten (automatisch von OnlineMathe generiert):
"Ich bräuchte bitte einen kompletten Lösungsweg." (setzt voraus, dass der Fragesteller alle seine Lösungsversuche zur Frage hinzufügt und sich aktiv an der Problemlösung beteiligt.)
Antwort
DrBoogie

DrBoogie aktiv_icon

13:49 Uhr, 27.11.2021

Antworten
Ich würde es zuerst mal so umformen:

3x=4 mod 7 <=> x=4/3=45=6 mod 7 (hier wurde benutzt, dass 53=1 mod 7)

und

5x=6 mod 8 <=> x=6/5=65=6 mod 8 (hier wurde benutzt, dass 55=1 mod 8

Also haben jetzt das System

x=6 mod 7
x=6 mod 8
x=5 mod 9

Das weitere Vorgehen ist hier erklärt:
de.wikipedia.org/wiki/Chinesischer_Restsatz

Konkret.

1. Suchen r1, s1, so dass 7r1+89s1=1. Mit dem erweiterten euklidischen Algorithmus kommt man hier auf r1=31, s1=-3.

2. Suchen r2, s2, so dass 8r2+79s2=1. Mit dem erweiterten euklidischen Algorithmus kommt man hier auf r2=8, s2=-1.

3. Suchen r3, s3, so dass 9r3+87s3=1. Mit dem erweiterten euklidischen Algorithmus kommt man hier auf r3=25, s3=-4.

Wenn du zu faul bist, um es selbst zu rechnen, hier ist der Rechner:
www.arndt-bruenner.de/mathe/scripts/erweitertereuklid.htm

Jetzt also haben e1=-372=-216, e2=-163=-63 und e3=-456=-224.
Damit x=-6216+-663-5224=-2794 ist eine Lösung. Sie ist nicht positiv, aber x+k789 ist für jedes k ebenfalls eine Lösung.
Also suchen k so, dass -2794+504k möglichst klein, aber noch positiv ist. Mit k=6 bekommen x1=230 die kleinste positive Lösung.




math-welt

math-welt aktiv_icon

14:02 Uhr, 27.11.2021

Antworten
Danke DrBoogie für die ausführliche Erklärung.


“3x=4 mod7 x=4/3=4⋅5=6 mod7 (hier wurde benutzt, dass 5⋅3=1 mod 7)”

jedoch diesen Teil von dem Umformen habe ich nicht ganz verstanden

x=43=45, wie 43 ist zu 45 geworden?

Antwort
HAL9000

HAL9000 aktiv_icon

14:03 Uhr, 27.11.2021

Antworten
Wobei man bei der manuellen Rechnung im konkreten Datenfall auch gelegentlich ein paar Abkürzungen nehmen kann:

So kann man beispielsweise hier die ersten beiden Kongruenzen gleich zu x6 mod 56 zusammenfassen, und damit einen Schritt dann beim Chinesischen Restsatz einsparen.

Antwort
DrBoogie

DrBoogie aktiv_icon

14:20 Uhr, 27.11.2021

Antworten
"jedoch diesen Teil von dem Umformen habe ich nicht ganz verstanden"

13 ist modulo 7 dasselbe wie 5, denn 35=1 mod 7.
Modulo-Rechnung funktioniert halt bisschen anders als "normale".
Frage beantwortet
math-welt

math-welt aktiv_icon

14:35 Uhr, 27.11.2021

Antworten
jetzt ist klar geworden DrBoogie. Danke