Restsatz

04.04.2013, 20:53

Ccenter

Restsatz

Nabend,
ich bin gerade am nachbereiten der Klausur und habe auf zwei Aufgaben keine Antworten finden können.

1. Nennen sie ein System aus zwei Kongruenzen ohne Lösung.
Diese Aufgabe bezieht sich auf den Chinesischen Restatz. Die Frage ist also, unter welchen Modulo es kein x geben kann, welches für die gegebenen Modulo zutrifft. Ich habe allerdings keine Idee wann dies der Fall sein kann.

2. Zeichnen sie die Äquivalenzklassen [3,4], [0,0], [1,1] in ein Koordinatensystem.
-> So bei dieser Aufgabe liegen Äquivalenzklassen vor. Mein Problem ist nur, es gibt ja keine gegebene Relation. Wie soll ich also die anderen Vertreter der Klasse ausfindig machen?

05.04.2013, 09:21

watcher

Auf diesen Beitrag antworten »

Nmorgen,

1) Beispiele finden sich unter den moduli n,m auf die der chinesische Restsatz nicht angewandt werden kann.

2) Hier wäre die vollständige Aufgabenstellung nützlich. So lässt sich in der tat nichts sagen.

06.04.2013, 16:52

Ccenter

Auf diesen Beitrag antworten »

OK, schonmal danke.
Zu Punkt 1, also dem Chinesischen Restsatz: Es war ja absolut nichts gegeben. Es gilt also allgemein ein System zu zeigen, für den der Satz nicht angewendet werden kann. Und hier fehlt mir das Wissen: Wann ist dies der Fall? Es wird doch sicherlich eine Einschränkung geben?
Ich kann mich an etwas erinnern wie, dass die Moduli nicht teilerfremd sein dürfen aber in diesem Fall gab es irgend ein Workaround dafür.
Demnach: Wann lässt sich der Satz nicht anwenden?

06.04.2013, 17:29

watcher

Auf diesen Beitrag antworten »

Wie jeder Satz hat der chin. Restsatz auch Voraussetzungen, wie lauten sie.
Bzw. Genauer, was verstehst du unter dem chin. Restsatz (gibt ein paar Varianten davon)

08.04.2013, 10:39

Ccenter

Auf diesen Beitrag antworten »

Es liegen mehrere Moduli vor und mehrere b1-bn.
Nun soll anhand des chinesischen Restsatz eine einzige Zahl gefunden werden, welche zusammen mit den b1-bn das gleiche Ergebnis für die jeweiligen Moduli liefert.

Die Aufgabenstellung ist dann, ein System anzugeben, bei dem kein x mit dem Restsatz ermittelt werden kann. Das heißt ich kann meine b1-bn und meine Moduli frei wählen, damit der Restsatz kein sinnvolles Ergebnis liefert. Aber ich kenne keinen Fall, in dem der Restsatz kein Ergebnis finden kann.

08.04.2013, 11:09

watcher

Auf diesen Beitrag antworten »

$\begin{eqnarray*} x \equiv 1 \mod 2<br /> x\equiv 0 \mod 4 \end{eqnarray*}$

08.04.2013, 20:17

Ccenter

Auf diesen Beitrag antworten »

Danke aber gegen welche Regel wurde nun bewusst verstoßen, welche Begründung steht dahinter?

08.04.2013, 20:37

HAL 9000

Auf diesen Beitrag antworten »

Aus $\begin{eqnarray*} x\equiv a\bmod n \end{eqnarray*}$ folgt $\begin{eqnarray*} x\equiv a\bmod m \end{eqnarray*}$ für jeden Teiler $\begin{eqnarray*} m \end{eqnarray*}$ von $\begin{eqnarray*} n \end{eqnarray*}$ .

Insbesondere muss also für $\begin{eqnarray*} x \end{eqnarray*}$ mit $\begin{eqnarray*} x\equiv 0\bmod 4 \end{eqnarray*}$ auch notwendig $\begin{eqnarray*} x\equiv 0\bmod 2 \end{eqnarray*}$ gelten - was offenbar nicht simultan zur anderen Kongruenz $\begin{eqnarray*} x\equiv 1\bmod 2 \end{eqnarray*}$ gelten kann!

Allgemein ist für die Lösbarkeit eines Kongruenzsystem

$\begin{eqnarray*} x\equiv a_i\bmod m_i \end{eqnarray*}$

die Bedingung $\begin{eqnarray*} a_i\equiv a_j\bmod \operatorname{ggT}(m_i,m_j) \end{eqnarray*}$ für alle Indexpaare $\begin{eqnarray*} (i,j) \end{eqnarray*}$ notwendig und hinreichend.

10.04.2013, 18:56

Ccenter

Auf diesen Beitrag antworten »

Vielen Dank aber das verstehe ich noch nicht so richtig, könntest du das nochmal anders formulieren?

Die Mod's dürfen also nur Vielfache vom ggT aller m's sein?

10.04.2013, 19:29

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von Ccenter
Die Mod's dürfen also nur Vielfache vom ggT aller m's sein?

Wieso "Mod's" ??? Ok, wenn du es nicht so mit Formeln hast:

Die $\begin{eqnarray*} a_i \end{eqnarray*}$ sind die gewünschten Reste; die Bedingung $\begin{eqnarray*} a_i\equiv a_j\bmod \operatorname{ggT}(m_i,m_j) \end{eqnarray*}$ ist lediglich relevant für Indizes $\begin{eqnarray*} i\neq j \end{eqnarray*}$ , wo $\begin{eqnarray*} m_i \end{eqnarray*}$ und $\begin{eqnarray*} m_j \end{eqnarray*}$ nicht teilerfremd sind. Verbal kann man das allenfalls so noch formulieren, dass $\begin{eqnarray*} (a_i-a_j) \end{eqnarray*}$ durch den größten gemeinsamen Teiler von $\begin{eqnarray*} m_i \end{eqnarray*}$ und $\begin{eqnarray*} m_j \end{eqnarray*}$ teilbar sein muss:

Denn wenn $\begin{eqnarray*} g=\operatorname{ggT}(m_i,m_j) \end{eqnarray*}$ ist, so folgt mit derselben Argumentation wie am Anfang meines ersten Beitrages oben, dass

1) aus $\begin{eqnarray*} x\equiv a_i\bmod m_i \end{eqnarray*}$ die Bedingung $\begin{eqnarray*} x\equiv a_i\bmod g \end{eqnarray*}$ folgt,

2) aus $\begin{eqnarray*} x\equiv a_j\bmod m_j \end{eqnarray*}$ auch die Bedingung $\begin{eqnarray*} x\equiv a_j\bmod g \end{eqnarray*}$ folgt.

Wenn es also eine Lösung des Gleichungssystems geben soll, dann folgt aus 1)2) zwingend, dass $\begin{eqnarray*} a_i\equiv a_j\bmod g \end{eqnarray*}$ gilt. Insofern ist schon mal klar, dass die genannte Bedingung notwendig zur Lösung des Kongruenzsystems ist. Dass es auch hinreichend ist, wäre noch zu klären.

Neue Frage »

Antworten »

Restsatz

Verwandte Themen