Mathematik online lernen im Mathe-Forum. Nachhilfe online

Startseite » Forum » Modulo-Gleichungssysteme

Modulo-Gleichungssysteme

Universität / Fachhochschule

Tags: Gleichungssystem, modulo

Helpneeder

00:54 Uhr, 15.07.2017

Hallo zusammen,

kann mir jemand verraten, wie man Aufgaben folgender Art löst?

Es sind alle

x \in ℤ

zu bestimmen, die folgendes Gleichungssystem lösen:

x = 2 mod 4

x = 6 mod 7

x = 3 mod 9

Nach meiner Auffassung der Modulo-Rechnung, ergeben sich hier für

x

jeweils drei verschiedene Ergebnisse (nämlich

2, 6

und

3),

aber ich schätze mal, hier ist eine formale Definition zu verwenden, die etwas anders funktioniert.
Im Zusammenhang mit solchen Aufgaben habe ich auch schon was vom chinesischen Restsatz gehört, von dem ich eine formale Beschreibung habe, aber nicht wirklich weiß, wie er praktisch funktioniert.
Kann mir jemand sagen, wie ich das mache?

DrBoogie aktiv_icon

01:07 Uhr, 15.07.2017

Wie man mit dem chinesischen Restsatz die Lösung findet, steht sogar in Wikipedia:
http://www.onlinemathe.de/forum/Modulo-Gleichungssysteme, unter "Finden einer Lösung".
Konkret hier:
finde

r_{1}, s_{1}

, so dass

4 r_{1} + 63 s_{1} = 1

,
finde

r_{2}, s_{2}

, so dass

7 r_{2} + 36 s_{2} = 1

,
finde

r_{3}, s_{3}

, so dass

9 r_{3} + 28 s_{3} = 1

,
dann wird die Zahl

2 \cdot 63 s_{1} + 6 \cdot 36 s_{2} + 3 \cdot 28 s_{3}

eine Lösung.
Ein Möglichkeit mit

s_{1} = - 1

s_{2} = 1

s_{3} = 1

, also das Ergebnis wird

- 126 + 216 + 84 = 174

.
Alle andere Lösungen

x

erfüllen

x = 174

mod

4 \cdot 7 \cdot 9

Helpneeder

02:42 Uhr, 15.07.2017

Okay, das bedeutet, ich benötige den euklidischen Algorithmus.
Ich versuche es mal Schritt für Schritt und streng nach Wikipedia aufzuschreiben:

M = 4 \cdot 7 \cdot 9 = 252

M_{1} = 252 : 4 = 7 \cdot 9 = 63

M_{2} = 252 : 7 = 4 \cdot 9 = 36

M_{3} = 252 : 4 = 4 \cdot 7 = 28

Jetzt suche ich

r_{1}, r_{2}, r_{3}, s_{1}, s_{2}, s_{3},

sodass:

4 r_{1} + 63 s_{1} = 1

7 r_{2} + 36 s_{2} = 1

9 r_{3} + 28 s_{3} = 1

Ich schreibe mal alles hin:

63 = 4 \cdot 15 + 3

4 = 3 \cdot 1 + 1

3 = 1 \cdot 3 + 0

Also:

1 = 4 - 3 \cdot 1 = 4 - (63 - 4 \cdot 15) \cdot 1

= 4 - (63 \cdot 1 - 4 \cdot 15) = 4 \cdot 16 + 63 \cdot - 1

\Rightarrow r_{1} = 16

und

s_{1} = - 1

\Rightarrow e_{1} = s_{1} \cdot 63 = - 63

36 = 7 \cdot 5 + 1

7 = 1 \cdot 7 + 0

Also:

1 = 36 - (7 \cdot 5)

\Rightarrow r_{2} = - 5

und

s_{2} = 1

\Rightarrow e_{2} = s_{2} \cdot 36 = 36

28 = 9 \cdot 3 + 1

9 = 1 \cdot 9 + 0

Also:

1 = 28 - (9 \cdot 3)

\Rightarrow r_{1} = - 3

und

s_{3} = 1

\Rightarrow e_{3} = s_{3} \cdot 28 = 28

Dann erhalte ich die Lösung

x = 2 \cdot e_{1} + 6 \cdot e_{2} + 3 \cdot e_{3} = - 126 + 216 + 84 = 174

Okay, damit habe ich das gleiche Ergebnis erhalten und besser verstanden wie's funktioniert.
Um das zu festigen, schaue ich mir mal noch ein paar Beispiele an.

Wenn ich nun ein Gleichungssystem habe wie das Folgende:

x = 5 mod 6

3 x = - 1 mod 14

Ändert das etwas an meinem Vorgehen?

Ansonsten würde ich ja so herangehen:

M = 6 \cdot 14 = 84

M_{1} = 14

M_{2} = 6

Dann suche ich vermutlich

r_{1}, r_{2}, s_{1}, s_{2},

sodass:

1 = 6 r_{1} + 14 s_{1}

3 = 14 r_{2} + 6 s_{2}

Wie komme ich jetzt durch den euklidischen Algorithmus auf diese Darstellungen von 1 und 3?

Alles, was ich herausbekomme, ist ja:

14 = 6 \cdot 2 + 2

6 = 2 \cdot 3 + 0

DrBoogie aktiv_icon

07:52 Uhr, 15.07.2017

"Ändert das etwas an meinem Vorgehen?"

Ja,

6

und

14

sind nicht teilerfremd.
Lies in Wikipedia unter "allgemeiner Fall".

Helpneeder

14:06 Uhr, 15.07.2017

Hm, ich bin nicht so ganz sicher, wie ich mit dem

3 x

zu verfahren habe.

Wenn man das mal außer Acht lässt, würde ja gelten, es gibt eine Lösung, wenn:

- 1 = 5 mod

ggT(14,

6) = 5 mod 2

Ist das korrekt?

Im Beispiel von Wikipedia wurde nun zusammengefasst

x = 1 mod

kgV
Allerdings habe ich anstelle von

1

in meinem Beispiel ja einmal 5 und einmal

- 1

.
Wie kann ich das GLeichungssystem dann unter dem kgV zusammenfassen?

Oder erhalte ich ein neues Gleichungssystem

x = - 1 mod

kgV(14,

6)

3 x = 5 mod

kgV(14,

6)

Diese Frage wurde automatisch geschlossen, da der Fragesteller kein Interesse mehr an der Frage gezeigt hat.

1380487

1380469

	Status: nicht eingeloggt	Noch nicht registriert?