Mathematik online lernen im Mathe-Forum. Nachhilfe online

Startseite » Forum » Chinesischer Restsatz

Chinesischer Restsatz

Universität / Fachhochschule

Elementare Zahlentheorie

Tags: Elementare Zahlentheorie

juli175 aktiv_icon

13:38 Uhr, 26.03.2013

Hey.

Ich habe ein Problem mit dem Chinesischen Restsatz.
Wenn die

mod

teilerfremd sind verstehe ich es.
Aber bei der Aufgabe, kann ich nicht mal den Anfang!
Hoffe ihr könnt mir weiterhelfen..

x = - 1 mod 10

x = 4 mod 15

x = 7 mod 8

.

Danke! :-)

Liebe Grüße,

juli175

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.)

michaL aktiv_icon

14:06 Uhr, 26.03.2013

Hallo,

ok, ich mache das mal, wie ich mir das selbst mal hergeleitet hab.

Gegeben sind also die drei Kongruenzen
(i)

x \equiv - 1 \equiv 9

mod 10
(ii)

x \equiv 4

mod 15
(iii)

x \equiv 7

mod 8

Bearbeiten wir erst einmal die beiden ersten Kongruenzen (i) und (ii):
Wenn diese beiden Kongruenzen eine simultane Lösung

x

haben, dann gilt für

x

x = 10 k + 9

einerseits und

x = 15 l + 4

andererseits für geeignete ganze Zahlen

k, l

.
Damit habe ich doch folgendes:

10 k + 9 = 15 l + 4 \overset{}{\Leftrightarrow} 9 - 4 = 15 l - 10 k \overset{}{\Leftrightarrow} 5 \cdot 1 = 5 \cdot 3 l - 5 \cdot 2 k

bzw.

1 = 3 l - 2 k

, woraus ich die Lösung

l = 1

k = 1

ablesen kann.
Wenn du dein bisheriges Wissen einordnen möchtest, so hattest du bisher auf linker Seite eine 1 (teilerfremde Moduln). Damit geht es immer. Aber allgemeiner ausgedrückt, funktionert ein Zusammenfassen zweier Kongruenzen genau dann, wenn die linke Differenz (9-4) ein Teiler des ggT der beiden Moduln (ggT(10,15)=5) ist. Was dahinter steckt, ist die Möglichkeit, so zu teilen, wie ich es gemacht hab!
Insbesondere lassen sich also die beiden ersten Kongruenzen zu

x \equiv 19

mod kgV(10,15)=30 zusammenfassen.

So, vielleicht kannst du die beiden Äquivalenzen

x \equiv 19

mod 30

x \equiv 7

mod 8
zusammenfassen?

Mfg Michael

juli175 aktiv_icon

14:26 Uhr, 26.03.2013

Danke für deine Antwort, klingt ganz logisch.
Ich hab in der Zwischenzeit auch rum probiert und habe es ein bisschen anders gemacht.

x = - 1 mod 10

ist ja das gleiche wie

x = 9 mod 10

.
Irgendwo haben wir in der Vorlesung das dann einfach wegfallen lassen, da es ja letztlich das gleiche wie

x = 7 mod 8

ist.

Daher habe ich mit

x = 7 mod 8

und

x = 4 mod 15

weitergerechnet.

- \to 15 x = 1 mod 8 - \to x = 7

und

8 x = 1 mod 5 - \to x = 2

7 \cdot 15 \cdot 7 + 4 \cdot 8 \cdot 2

= 799

799 mod 120 (120

da,

8 \cdot 15)

= 79 mod 120

Ganz logisch finde ich es jedoch nicht, warum ich die eine Gleichung einfach wegfallen lassen kann!
Hast du darauf eine Antwort?

michaL aktiv_icon

14:35 Uhr, 26.03.2013

Hallo,

Glück gehabt, dass die Primteiler von 10 sämtlich in 8 und 15 enthalten sind! Wenn nicht, dürfte man nicht einfach fortlassen!

Was du machen kannst, ist auf einfache Weise die beiden Kongruenzen

x \equiv - 1

mod 10 und

x \equiv - 1

mod 8 zusammenfassen zu

x \equiv - 1

mod kgV(8,10)=40

Das geht quasi ohne große Rechnung.

Mfg Michael

PS: wikipedia stellt die Sache in hinreichendem Maße genau dar!

juli175 aktiv_icon

11:23 Uhr, 27.03.2013

Ah, oke, danke.
Ich glaub solangsam hab ichs. ;-)

Aber nochmal ne Frage zu dem "wegfallen lassen".

Wenn ich jetzt das System

x = - 1 mod 5

x = - 1 mod 8

x = 5 mod 9

x = 5 mod 6

habe, hätte ich einfach umgeformt zu

x = 4 mod 5

x = 7 mod 8

x = 5 mod 9

x = 5 mod 6

.

Da ja nun

4 mod 5

und

5 mod 6

(eig auch

7 mod 8)

das gleiche ist,
habe ich

5 mod 6

wegfallen lassen, da dann ggT(5,8,9)=

1 (

teilerfremd ).

Kann ich das wirklich belieblig entscheiden, was wegfällt?
Und darf ich immer nur eine Lösung wegfallen lassen oder auch mehrere?

Ich habs auf meine Weise^mal ausgerechnet und komme auf

119 mod 360

. Müsste passen.

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

1084072

1083954

	Status: nicht eingeloggt	Noch nicht registriert?