Mathematik online lernen im Mathe-Forum. Nachhilfe online

Startseite » Forum » Kongruenzsystem lösen

Kongruenzsystem lösen

Universität / Fachhochschule

Tags: Kongruenzsystem

math-welt aktiv_icon

12:55 Uhr, 27.11.2021

Finden sie das kleinste positive $x$ ∈ $Z,$ das das folgende Kongruenzsystem erfüllt
(mit Rechenweg)

$3 x mod 7 = 4$

$5 x mod 8 = 6$

$x mod 9 = 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.)

DrBoogie aktiv_icon

13:49 Uhr, 27.11.2021

Ich würde es zuerst mal so umformen:

$3 x = 4$ mod $7$ <=> $x = 4 / 3 = 4 \cdot 5 = 6$ mod $7$ (hier wurde benutzt, dass $5 \cdot 3 = 1$ mod $7$ )

und

$5 x = 6$ mod $8$ <=> $x = 6 / 5 = 6 \cdot 5 = 6$ mod $8$ (hier wurde benutzt, dass $5 \cdot 5 = 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 $r_{1}$ , $s_{1}$ , so dass $7 r_{1} + 8 \cdot 9 s_{1} = 1$ . Mit dem erweiterten euklidischen Algorithmus kommt man hier auf $r_{1} = 31$ , $s_{1} = - 3$ .

2. Suchen $r_{2}$ , $s_{2}$ , so dass $8 r_{2} + 7 \cdot 9 s_{2} = 1$ . Mit dem erweiterten euklidischen Algorithmus kommt man hier auf $r_{2} = 8$ , $s_{2} = - 1$ .

3. Suchen $r_{3}$ , $s_{3}$ , so dass $9 r_{3} + 8 \cdot 7 s_{3} = 1$ . Mit dem erweiterten euklidischen Algorithmus kommt man hier auf $r_{3} = 25$ , $s_{3} = - 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 $e_{1} = - 3 \cdot 72 = - 216$ , $e_{2} = - 1 \cdot 63 = - 63$ und $e_{3} = - 4 \cdot 56 = - 224$ .
Damit $x = - 6 \cdot 216 + - 6 \cdot 63 - 5 \cdot 224 = - 2794$ ist eine Lösung. Sie ist nicht positiv, aber $x + k \cdot 7 \cdot 8 \cdot 9$ ist für jedes $k$ ebenfalls eine Lösung.
Also suchen $k$ so, dass $- 2794 + 504 k$ möglichst klein, aber noch positiv ist. Mit $k = 6$ bekommen $x_{1} = 230$ die kleinste positive Lösung.

math-welt aktiv_icon

14:02 Uhr, 27.11.2021

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

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

jedoch diesen Teil von dem Umformen habe ich nicht ganz verstanden

$x = \frac{4}{3} = 4 \cdot 5,$ wie $\frac{4}{3}$ ist zu $4 \cdot 5$ geworden?

HAL9000

14:03 Uhr, 27.11.2021

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 $x \equiv 6 mod 56$ zusammenfassen, und damit einen Schritt dann beim Chinesischen Restsatz einsparen.

DrBoogie aktiv_icon

14:20 Uhr, 27.11.2021

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

$\frac{1}{3}$ ist modulo $7$ dasselbe wie $5$ , denn $3 \cdot 5 = 1$ mod $7$ .
Modulo-Rechnung funktioniert halt bisschen anders als "normale".

math-welt aktiv_icon

14:35 Uhr, 27.11.2021

jetzt ist klar geworden DrBoogie. Danke

1545790

1545778

	Status: nicht eingeloggt	Noch nicht registriert?