Chinesischer Restsatz - nicht teilerfremde moduln

13.04.2016, 10:03	Alex13	Auf diesen Beitrag antworten »
Chinesischer Restsatz - nicht teilerfremde moduln Liebe Mathe-Community, ich komme bei einer Aufgabe zu dem Chinesischen Restsatz nicht weiter und würde mich über ein wenig Hilfe freuen. Mir ist klar wie man eine Aufgabe mit paarweise teilerfremden moduln berechnet aber die Aufgabe an der ich derzeit sitze hat nicht teilerfremde moduln und ist meiner Ansicht doch mit dem Chinesischen Restsatz lösbar. Allerdings komme ich nicht weiter. Die Aufgabe ist: $\begin{eqnarray} x \equiv 7 \end{eqnarray}$ mod 10 $\begin{eqnarray} x \equiv 5 \end{eqnarray}$ mod 8 Offenbar sind die moduln nicht paarweise teilerfremd denn ggT(8,10) = 2. In diesem Fall existiert eine Lösung zu dem System wenn für $\begin{eqnarray} i \neq j: a_i \equiv a_j \end{eqnarray}$ mod ggT(8,10). Als erstes Faktorisiere ich in diesem Fall die moduln um das zu lösende Gleichungssystem aufzustellen. $\begin{eqnarray} 10 = 2 5 \end{eqnarray}$ $\begin{eqnarray} 8 = 2^3 \end{eqnarray}$ Neues Gleichungssystem ist also: $\begin{eqnarray} x = 1 \end{eqnarray}$ mod 2 $\begin{eqnarray} x = 2 \end{eqnarray}$ mod 5 $\begin{eqnarray} x = 5 \end{eqnarray}$ mod 8 Schritt 2: Gesamt Modul berechnen: 258 = 80 = m Schritt 3: $\begin{eqnarray} b_1 = \frac{80}{2} = 40 \end{eqnarray}$ $\begin{eqnarray} b_2 = \frac{80}{5} = 16 \end{eqnarray}$ $\begin{eqnarray} b_3 = \frac{80}{8} = 10 \end{eqnarray}$ Schritt 4: An dieser Stelle suche ich ein $\begin{eqnarray} x_i \end{eqnarray}$ das die u.a. Gleichung erfüllt. Dieses $\begin{eqnarray} x_i \end{eqnarray}$ kann es hier aber gar nicht geben da 40x mod 2 immer 0 ergibt. $\begin{eqnarray} b_1 x_1 \equiv 1 \end{eqnarray*}$ mod 2 Was habe ich falsch gemacht? Gruß Alex
13.04.2016, 11:30	tatmas	Auf diesen Beitrag antworten »
Hallo, dein neues Gleichungssystem ist richtig. Allerdings ist die erste Gleichung bereits durch die dritte erfüllt, kann also weggelassen werden. Dann kann man auch eure Variante des chin. Restsatzes verwenden. Und was du falsch machst ist ganz einfach: Du ignorierst dass Voraussetzungen eines Satzes nicht erfüllt sind. Denn dann gilt der Satz schlicht nicht und "richtige" Ergebnisse wären schlicht Zufall.
13.04.2016, 13:07	Alex13	Auf diesen Beitrag antworten »
Hi tatmas, danke für die Hilfe. Mir ist allerdings nicht ganz klar welche Voraussetzungen ich ignoriert habe. Gruß Alex
13.04.2016, 18:03	tatmas	Auf diesen Beitrag antworten »
Deine Moduln sind nicht teilerfremd. Die Teilerfremdheit der Moduln ist explizite Vorauusstzung in fast allen Varianten des chin. Restsatzes.
21.03.2018, 19:35	Hosenschlange	Auf diesen Beitrag antworten »
Das Thema ist nun schon ziemlich alt, aber ich hatte vor kurzem ein ähnliches Problem. Bei stackexchange hab ich was dazu gefunden...zumindest für den Fall, wenn 2 Kongruenzen vorliegen: $\begin{eqnarray} \begin{cases}x \equiv a \pmod{m}\\x \equiv b \pmod{n}\end{cases} \end{eqnarray}$ Eine Lösung existiert hierfür, wenn gilt $\begin{eqnarray} \gcd(m, n) \mid a - b \end{eqnarray}$ . Mit dem Erweiterten Euklidischen Algorithmus findet man u und v, so dass $\begin{eqnarray} m u + n v = \gcd(m, n) \end{eqnarray}$ gilt. Als nächstes berechnet man $\begin{eqnarray} \lambda = \frac{a - b}{\gcd(m, n)} \end{eqnarray}$ und erhält $\begin{eqnarray} m (u \lambda) + n (\lambda v) = a - b \end{eqnarray}$ . Die Lösung ist nun $\begin{eqnarray} x = a - m (u \lambda) = b + n (\lambda v) = \sigma \end{eqnarray}$ und alle Lösungen sind $\begin{eqnarray} x \equiv \sigma \pmod{lcm(m, n)} \end{eqnarray}$ . Hat man mehrere Kongruenzen, löst man damit die ersten beiden und setzt dann mit der Lösung und der dritten fort. Und so weiter. Das war eine lose Übersetzung des Posts hps(Doppelpunkt-Slash-Slash)math(Punkt)stackexchange(Punkt)com(Slash)a(Slash)1644698 Hierbei steht gcd() für den Größten Gemeinsamen Teiler und lcm()** für das Kleinste Gemeinsame Vielfache. Ich habe das für das Beispiel $\begin{eqnarray} \begin{cases} x \equiv 2 \pmod{4}\\ x \equiv 4 \pmod{6}\\ \end{cases} \end{eqnarray}$ probiert und erhalte richtigerweise 10. Vielleicht kann das jemand aus dem Board bestätigen
21.03.2018, 20:05	Hosenschlange	Auf diesen Beitrag antworten »
Ich hab das Beispiel von Alex13 mit diesem Lösungsweg durchgerechnet und erhalte als richtiges Ergebnis 37
Anzeige

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »