[Zahlentheorie] Kongruenzsysteme

Neue Frage »

loci Auf diesen Beitrag antworten »
[Zahlentheorie] Kongruenzsysteme
Hallo,

ich rechne alte Aufgaben nach für eine Klausur und komme mit den Kongruenzsystem - wenn alles Standard ist - gut zurecht. z.B. ein System mit






kann ich fehlerfrei rechnen.

Nun gibt es noch eine andere Aufgabe die wir in der Übung nicht mehr ganz geschafft haben. Es geht um das System





Dort würde die übliche Rechenweise aber nicht funktionieren, sondern man muss erst Zerlegen. In beispielsweise (so habe ich es notiert) :
und

Die Zerlegung geht ja auch recht simpel. Frage ist nur - warum! verwirrt Also "warum funktioniert hier der übliche Weg nicht"? Weil die ai's nicht so schön von 1 bis 4 (oder in unserem Fall da nur 3 x gegeben) bis 3 gehen? Wo sehe ich wann eine Zerlegung notwendig ist? Und was mache ich dann mit der Zerlegung genau? Wir haben in der Übung leider nicht mehr weiter gerechnet da keine Zeit mehr übrig war.
RavenOnJ Auf diesen Beitrag antworten »
RE: [Zahlentheorie] Kongruenzsysteme
In dem ersten System von Kongruenzen gibt es in


für x für jedes Tupel eine Lösung. Dies liegt daran, dass die Zahlen, für die modulo gerechnet wird, alle Primzahlpotenzen sind (falsch, siehe Edit). Außerdem sind auch alle y mit Lösung.

Im zweiten System ist dies nicht mehr so einfach, da . Es werden also Kongruenzen zu zusammengesetzten (Edit: und vor allem zu nicht paarweise teilerfremden) Zahlen gebildet. Gilt die Kongruenz
,
so ist dies äquivalent zu
,
also


In dem verallgemeinerten System von Kongruenzen aus deinem zweiten Beispiel


gibt es nicht zu jedem Tupel eine Lösung, da alle Kongruenzen

simultan erfüllt sein müssen. Die Kongruenzen (1a) und (1b) entsprechen dabei der Kongruenz (1) usw..

In deinem konkreten Beispiel mit a=1,b=3,c=10


gibt es für x Lösungen, da wegen gilt:

es gibt also in diesem System von Kongruenzen keine Widersprüche. Die Kongruenzen (1'a) und (1'b) entsprechen dabei der Kongruenz (1') usw.. Es gibt außerdem noch Lösungen , da .

Würde statt (1') die Kongruenz angenommen, so gäbe es für x in dem System keine Lösung, da ein Widerspruch zu anderen Kongruenzen auftreten würde.

Edit: Der Grund ist nicht, dass es sich um Primzahlpotenzen handelt, sondern dass alle vier Zahlen paarweise teilerfremd sind. Dies ist natürlich in diesem Fall trivial, weil es sich um Potenzen von vier verschiedenen Primzahlen handelt (hier alle mit Exponent 1).
mYthos Auf diesen Beitrag antworten »

Ein alternativer Lösungsweg (ich weiss allerdings nicht, ob das so erlaubt ist):

x = 6a + 1
x = 14b + 3
x = 21c + 10
-------------------
Daraus entsteht das diophantische LGS

6a - 14b = 2
6a = 21c + 9
-------------------

mit b = 2+ 3t, c = 1 + 2t und a = 5 + 7t

Damit ist x kongruent 31 mod 42

mY+
loci Auf diesen Beitrag antworten »

Danke für die Aufklärung, das macht Sinn und leuchtet mir ein.

Wenn ich das dann entsprechend umwandle (wobei mir das oben ja schon abgenommen wurde), habe ich vorhin auch auf meinem Schmierblatt nachgerechnet und bin auch aus den obigen Gleichungen auf folgendes gekommen:





Das mit den Primzahlpotenzen hat mir da etwas geholfen glaube ich.

Wenn ich nun oben meine Kongruenzen herausgefunden habe - kann ich damit einfach weiterrechnen? Ich frage so irritiert, da wir sonst bei den "einfachen" Aufgaben eher immer 4 "Teile" hatten wie in meinem ersten System von Kongruenzen. D.h. wenn ich - so haben wir es gelernt - meine Tabelle aufstelle mit ai, mi, Mi = m/mi etc. - kann ich diese normal ausfüllen und habe statt 4 dann eben nur 3 Zeilen? Ich könnte dies auch einfach mal vorrechnen wenn es nicht klar ist, was ich damit meine. (Der Grund warum ich es nicht jetzt mache ist der, dass ich mir dann merke wie ich es gemacht habe beim lernen und dann in der Klausur vor Aufregung nachher das falsche anwende - d.h. wenn ihr von vorn herein sagt dass es Quatsch ist, würde ich mich dann lieber auf den korrekten Lösungsweg beschränken).

EDIT: Nur um nochmal den Tabellenkopf und damit meinen Rechenweg zu verdeutlichen: Der Tabellenkopf sieht so aus:
,
am Ende ziehe ich aus der letzten Spalte die Summe und bilde daraus dann die Lösung mit x und k aus
RavenOnJ Auf diesen Beitrag antworten »

Zitat:
Original von loci
Das mit den Primzahlpotenzen hat mir da etwas geholfen glaube ich.


Meine Aussage war allerdings nicht ganz richtig (war ein bisschen spät Augenzwinkern ). Der Grund dafür, dass jedes Tupel (a,b,c,d) zu einer Lösung für x passt liegt nicht daran, dass nur Kongruenzen modulo zu Primzahlpotenzen dort stehen. Der Grund liegt in der paarweisen Teilerfremdheit der Zahlen zu denen modulo gerechnet wird.
loci Auf diesen Beitrag antworten »

Oh, ok. Aber irgendwie kam ich trotzdem auf das richtige verwirrt Wahrscheinlich habe ich es unterbewusst doch irgendwie richtig aufgefasst oder so. Big Laugh (hoffe ich).

Kann ich anschließend normal damit weiter rechnen? D.h. ist die Vorgehensweise, zuerst alles umzuwandeln siehe oben, und dann eben normal weiter machen mit der Tabelle? Vielleicht ist das der Grund warum wir das als letzte Aufgabe gemacht haben und dann aufgehört haben, weil es evtl. ja genau so dann weiter geht wie mit den anderen Aufgaben ohne umwandeln, wie im ersten System. verwirrt
 
 
RavenOnJ Auf diesen Beitrag antworten »

Zitat:
Original von loci
Wenn ich das dann entsprechend umwandle (wobei mir das oben ja schon abgenommen wurde), habe ich vorhin auch auf meinem Schmierblatt nachgerechnet und bin auch aus den obigen Gleichungen auf folgendes gekommen:





Das mit den Primzahlpotenzen hat mir da etwas geholfen glaube ich.

Wenn ich nun oben meine Kongruenzen herausgefunden habe - kann ich damit einfach weiterrechnen?

Ja, damit kannst du weiterrechnen.

Zitat:
Ich frage so irritiert, da wir sonst bei den "einfachen" Aufgaben eher immer 4 "Teile" hatten wie in meinem ersten System von Kongruenzen. D.h. wenn ich - so haben wir es gelernt - meine Tabelle aufstelle mit ai, mi, Mi = m/mi etc. - kann ich diese normal ausfüllen und habe statt 4 dann eben nur 3 Zeilen? Ich könnte dies auch einfach mal vorrechnen wenn es nicht klar ist, was ich damit meine.

EDIT: Nur um nochmal den Tabellenkopf und damit meinen Rechenweg zu verdeutlichen: Der Tabellenkopf sieht so aus:
,
am Ende ziehe ich aus der letzten Spalte die Summe und bilde daraus dann die Lösung mit x und k aus


Das solltest du allerdings mal genauer erläutern.
loci Auf diesen Beitrag antworten »

Gerne!

Leider weiß ich nicht, wie ich Tabellen so abtippen kann. Ich habe daher gewagt, meine Rechnung als bearbeitetes Foto (um Dateigröße gering zu halten) als Anhang hinzu zu fügen.

Ich hoffe, es ist okay und ersichtlich, wie wir das gelernt haben. Eventuell habe ich mich dort verrechnet, aber bekam beim Teilen keinen Rest und ganzzahlige Ergebnisse - habe aber für diese Aufgabe keine Musterlöung. Bei den übrigen Aufgaben, die ohne Umwandeln funktionieren, und wo ich Lösungen zu habe, komme ich mit diesem Verfahren auf das richtige Ergebnis.
RavenOnJ Auf diesen Beitrag antworten »

Deine Tabelle ist leider falsch.
1.) In der ersten Zeile muss statt vielmehr stehen. Zufälligerweise hat dies keinen Einfluss auf den Wert von .
2.) In der zweiten Zeile muss statt richtigerweise stehen.
3.) Mit den korrigierten Werten müssen bei folgende Werte stehen: In der 1. Zeile 21 und in der 2. Zeile 28. Damit wird die Summe aus der letzten Spalte 21+28+108=157 und als Ergebnis erhält man
. Es sind also alle Lösung dieses Systems aus Kongruenzen.

Vielleicht solltest du dir Gedanken darüber machen, warum man die Aufgabe auf diesem schematischen Weg lösen kann.
loci Auf diesen Beitrag antworten »

Ja, das stimmt! Flüchtigkeitsfehler. Warum dies so ist, ist mir auch gleich klar gewesen als ich es gesehen hab. 42/2 ist natürlich 21,

Absatz Entfernt.

EDIT: In der Definition steht es mit ai so wie du es erklärt hast. Wir hatten in der anderen Aufgabe einfach Glück, das ai immer um 1 angestiegen ist. Damit ist deine Aussage oben die richtige, mein Rechenweg und mein ai daher Schwachsinn, korrekt.
RavenOnJ Auf diesen Beitrag antworten »

Das ist gut bis auf einen Flüchtigkeitsfehler in dem Abschnitt ,,1. Umwandlung der Kongruenzen". Dort hätte in der zweiten Zeile auftauchen müssen.

Ist dir klar, warum du mit dieser Tabelle auf das richtige Ergebnis kommst? Insbesondere der Grund für den vorletzten Schritt, die Summation über die Spalte ?
loci Auf diesen Beitrag antworten »

Da ich noch eine Aufgabe gerechnet habe und ein Kommilitone meinte, es wäre falsch da er die Probe gerechnet hat, habe ich es wohl nicht richtig verstanden, sondern nur angewendet unglücklich (Aufgabe siehe Anhang, meine Umwandlung der ersten Kongruenz ist wohl falsch laut ihm, da sie nicht kongruent zur Ausgangskongruenz verwirrt ist).

So ist es halt definiert bei uns mit der Summation. Aber warum man das macht - ganz ehrlich, erklären könnte ich das nicht unglücklich Habe generell etwas Schwierigkeiten die Sachen aus den Definitionen ins "deutsche" zu übersetzen, da es manchmal recht kryptisch ist. Da muss ich mich etwas mehr üben.

Mein Flüchtigkeitsfehler den du oben auch noch meintest ist klar. Dort habe ich ja "mod 7" - 7*7 ist aber 49, und nicht 14! Und 3 mod 2 gibt es nicht, das wäre dann wie du meintest 1 mod 2. Ist das die korrekte Begründung? Habe das gerade gesehen und mich selbst gefragt wie ich 2x auf mod 7 komme in der zweiten Zeile... unglücklich Ich neige leider sehr zu Flüchtigkeitsfehlern, das ist auch das was mir in Klausuren die Punkte kostet...
loci Auf diesen Beitrag antworten »

Schade, kann nicht mehr editieren:

Kann es sein dass es 2 mod 2 doch gar nicht gibt, da es dann 0 mod 2 wäre? Oder bin ich jetzt völlig durcheinander? verwirrt
RavenOnJ Auf diesen Beitrag antworten »

Du hast die Tabelle falsch berechnet. Der Lapsus liegt in der 1. Zeile. Es gilt die Kongruenz

Du hast also in diesem Fall eine höhere Primzahlpotenz (Exponent >1) dort stehen und die muss auch bleiben, d.h. . Damit ändern sich einige deiner Rechenschritte, u.a. m=220 usw..

Rechne die Tabelle nochmal neu durch, danach erkläre ich dir, warum das Ganze so funktioniert wie es gemacht wird.
RavenOnJ Auf diesen Beitrag antworten »

Zitat:
Original von loci
Dort habe ich ja "mod 7" - 7*7 ist aber 49, und nicht 14! ... Habe das gerade gesehen und mich selbst gefragt wie ich 2x auf mod 7 komme in der zweiten Zeile.


Ehrlich gesagt weiiß ich gerade nicht, was du hier meinst. Wo taucht 7*7 auf? Es ging bei der vorigen Aufgabe um . Die 7 ist zweimal Faktor, einmal in 14, dann in 21.
loci Auf diesen Beitrag antworten »

Ok, ich habe es nochmal berechnet. Hoffe jetzt ohne Flüchtigkeitsfehler, bin in der Uni lernen und es ist leider grad recht laut hier...
RavenOnJ Auf diesen Beitrag antworten »

Da ist leider wieder ein Fehler drin. kann natürlich nicht 4 sein, da gelten muss.
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »