Mathematik online lernen im Mathe-Forum. Nachhilfe online

Startseite » Forum » chinesischer Restsatz

chinesischer Restsatz

Universität / Fachhochschule

Elementare Zahlentheorie

Tags: chinesischer Restsatz, Elementare Zahlentheorie

kennedy aktiv_icon

14:12 Uhr, 03.05.2015

Hallo,

x \equiv 1 m o d 5

x \equiv 6 m o d 7

x \equiv 3 m o d 11

diese Aufgabe habe ich gelöst und wollte fragen ob meine Lösung von

x = 146

richtig ist?

Als Rechenweg habe ich:

x = 1 * 7 * 11 x_{1} + 6 * 5 * 11 x_{2} + 3 * 5 * 7 x_{3}

also

(7 * 11) x_{1} \equiv 1 m o d 5

daraus folgt

x_{1} = 3

(5 * 11) x_{2} \equiv 1 m o d 7

daraus folgt

x_{2} = 6

(5 * 7) x_{3} \equiv 1 m o d 11

daraus folgt

x_{3} = 6

oben eingesetzt

x = 2841 m o d 385

das ist gleich

x = 146

bei b) bin ich mir nicht sicher wie ich argumentieren kann bzw ob ich überhaupt argumentieren kann.

x \equiv 13 m o d 30

x \equiv 28 m o d 105

x \equiv 28 m o d 385

ich weiß jetzt nicht was eine vollständige Lösung dafür wäre, aber ich vermute, dass es nicht lösbar ist, denn 30,105,385 sind nicht teilerfremd, wäre das richtig? und reicht es?

LG

Für alle, die mir helfen möchten (automatisch von OnlineMathe generiert):
"Ich möchte die Lösung in Zusammenarbeit mit anderen erstellen."

Kasiaw aktiv_icon

15:06 Uhr, 03.05.2015

Hi,

kenne ein anderes Vorgehen unter dem chinesischen Restsatz, aber deine erste Lösung ist richtig, wobei das nur eine Lösung ist. Die Lösungsmenge ist

146 \cdot 385 \cdot n

mit

n \in ℕ

b

ist aber auch lösbar. Die Begründung dass die drei Zahlen teilerfremd erschließt sich mir nicht, da bei a doch auch drei Primzahlen gegeben sind.

Hast du versucht den chinesischen Restsatz anzuwenden? Ich erhalte als Ergebnis für

x = 160573 \cdot n \cdot 1212750

mit

n \in ℕ

Setzt du diese Zahl in deine drei Kogruenzgleichungen ein, dann klappt das auch.

kennedy aktiv_icon

15:15 Uhr, 03.05.2015

Hallo, danke für deine Antwort,

habe mal ein Online calculator gefunden, der hat mir

x = 84525

als Lösung gegeben zwar ohne Rechenschritte, aber wäre das auch richtig? Ich versuche mal nachher die Rechenschritte aufzuschreiben, bzw ich werde es mal versuchen.

LG

Kasiaw aktiv_icon

15:22 Uhr, 03.05.2015

Hmmm... wenn ich

84525

in die erste Kongruenzgleichung einsetze, dann müsste doch gelten:

84525 \equiv 13 mod 30

Aber

84525 : 30 = 2817

Rest

15 \neq 13

Also kann das nicht stimmen. Hast du dich vllt im Rechner vertippt?

kennedy aktiv_icon

15:37 Uhr, 03.05.2015

hmmm eigentlich nicht,

http://davidwees.com/chineseremaindertheorem/ das ist der calculator.

LG

Kasiaw aktiv_icon

15:43 Uhr, 03.05.2015

Tatsächlich... Das kann ich leider nicht erklären..

Am besten du verwendest den chinesischen Restsatz mal selbst, dann solltest du auf dasselbe Ergebnis kommen.

kennedy aktiv_icon

15:48 Uhr, 03.05.2015

hmmm trotzdem irgendwas stimmt bei dieser Aufgabe nicht.

ich habe

x = 13 * 105 * 385 x_{1} + 28 * 30 * 105 x_{2} + 28 * 30 * 385 x_{3}

also

(105 * 385) x_{1} \equiv 1 m o d 30

daraus folgt

40425 x_{1} \equiv 1 m o d 30

daraus folgt

15 x_{1} \equiv 1 m o d 30

diese Gleichung ist nicht lösbar.

dann habe ich als zweite Kongruenz.

(30 * 105) x_{2} \equiv 1 m o d 385

daraus folgt

11550 x_{2} \equiv 1 m o d 385

und daraus folgt

70 x_{2} \equiv 1 m o d 385

und das ist auch nicht lösbar.
Als nächstes habe ich

(30 * 385) x_{3} \equiv 1 m o d 105

daraus folgt

0 x_{2} \equiv 1 m o d 105

Kasiaw aktiv_icon

15:58 Uhr, 03.05.2015

wie verwendet ihr denn den chinesischen Restsatz?

Ich kenne es so: Sei

x \equiv a mod n

x \equiv b mod m

dann ist dies lösbar, wenn

a \equiv b mod d

wahr ist mit d=ggT(n,m)

Bestimmst du die Bezout Koeffizienten, dann erhälst du ja:

d =

yn+zm

Und dann ist eine Lösung:

x \equiv a - y \cdot n \cdot \frac{a - b}{d} mod \frac{n \cdot m}{d}

Wendest du dieses Verfahren zweimal an, kommst du auch auf meine Lösung. Oder kennt ihr das anders?

kennedy aktiv_icon

16:04 Uhr, 03.05.2015

um ehrlich zu sein ich habe es von hier : www.youtube.com/watch?v=S_Dfw7J9EBE ^^

ich weiß nicht, wie wir es in der Vorlesung gemacht haben, da ich krank war.

LG

Kasiaw aktiv_icon

16:09 Uhr, 03.05.2015

Ok.
Also, den chinesischen Restsatz verwendest du so wie ich es im letzten Beitrag geschrieben habe.

Sind dir Bezout Koeffizienten bekannt? Denn die brauchst du. In dem Restsatz ist es das

y

und das

z

.

Um den Restsatz anzuwenden, darf vor dem

x

kein Koeffizient (außer die

1)

stehen. Auch dafür gibt es Verfahren. Bei deiner Aufgabe brauchst du dich aber darum nicht zu kümmern.

Wenn du weißt wie man die Bezout Koeffizienten ermittelt, dann musst du nur noch stumpf alles in den Restsatz einsetzen (beachte dabei, dass

n

betraglich kleiner sein muss als

m)

Hilft das?

kennedy aktiv_icon

16:14 Uhr, 03.05.2015

Jein,nicht ganz. Aber ich versuche es mal gleich danke.
Noch eine kurze Frage du hast ja oben, eine formel hingeschrieben, die war aberfür zwei Kongruenzen wie sieht die denn für drei Kongruenzen aus?

Und ich weiß was mein Fehler die ganze Zeit war...wenn modulos nicht teilerfremd sind, dann darf man halt dieses Standardverfahren nicht anwenden.. das wusste ich nicht ^^ sry.

Kasiaw aktiv_icon

16:19 Uhr, 03.05.2015

Genau, es geht immer nur mit 2. Dann bekommst du aber ja ein Ergebnis raus mit

x \equiv

irgendwas

mod

irgendwas
Dieses Ergebnis nimmst du dann zusammen mit der 3. Kongruenzgleichung und wendest das nochmal an. So kannst du also beliebig viele Gleichungen betrachten.

Ich schick dir mal meine Aufzeichnungen, vllt hilft es, beim nachrechnen. Auf der zweiten Seite hab ich einfach nur den erweiterten euklidischen Algorithmus verwendet, weil die Bezout Koeffizienten nihct direkt ersichtlich waren