Kongruenz

Neue Frage »

baba2k Auf diesen Beitrag antworten »
Kongruenz
Hallo zusammen,

ich weiß nicht so richtig, wie ich die folgenden Aufgaben lösen soll:

1. Berechnen Sie ein, das und erfüllt. Die Antwort ist zu bergründen.
Musterlösung: Erstelle eine Liste von Zahlen, die kongruent 5 modulo 9 sind: 5,14,23,32,41,... Man sieht, dass 32 eine Lösung von ist.

2. Berechnen Sie ein, das und erfüllt.
Musterlösung: Durch Raten sieht man, dass x=36 die beiden Kongruenzen erfüllt.

3. Berechnen Sie ein(K1), das und (K2) erfüllt.
Musterlösung: Die ersten positiven Lösungen von (K1) sind: 5,13,21,29,37,45,53,61,... Man sieht,d ass x=61 auch die Kongruenz (K2) erfüllt.

3. Entscheiden Sie ob es ein mit und erfüllt.
Musterlösung: Behauptun: Es gibt keins. Beweis: Nimm an, es gäbe doch ein solches x. Dann würde wegen der ersten Kongruenz x ungerade sein. Die zweite Kongruenz würde aber erzwingen, dass x gerade ist. Widerspruch.

Mein normaler Vorgang wäre (So haben wirs gelernt):
1. ggT = 1 testen
2. Beide Kongruenzen in eine Funktion umführen
3. Werte für s und t ermitteln (erweiterter euklidischer Algo.)
4. Ergebnisse anpassen
5. Lösungsmenge bilden

Aber das dauert ja viel zu lang in der Klausur. Hat jemand einen Tipp wie ich das auf anhieb sehen kann? Leider finde ich diese Aufgaben nur in den alten Klausuren, wir haben sowas nicht in der Übung gemacht.

Vielen Dank!

Gruß baba
Captain Kirk Auf diesen Beitrag antworten »
RE: Kongruenz
Hallo,

auch wenn ich Pnkt 2 nicht verstehe scheinst du hier den Standardalgo. zur Berechnung solcher sog. simultaner Kongruenzen zu verwenden.

Zitat:
Aber das dauert ja viel zu lang in der Klausur.

Das sollte in den Fällen wie oben mit etwas Übung nicht länger als 1-2 Minuten bei Aufgaben wie oben dauern.
Und das ist zu lang?

Zitat:
Hat jemand einen Tipp wie ich das auf anhieb sehen kann?

Auge entwickelt man nur durch Übung.
baba2k Auf diesen Beitrag antworten »

Es funktioniert also nur nach diesem Schema?
[attach]31330[/attach]

Was verstehst du bei Punkt zwei nicht?

Vielen Dank!

Gruß baba
Captain Kirk Auf diesen Beitrag antworten »

Bei Punkt 2 war deine Beschreibung:
Zitat:
2. Beide Kongruenzen in eine Funktion umführen

schlicht nicht annähernd aussagekräftig. Das ist nur eine Überschrift nicht mehr.

Wobei auch mit der ausführlichen Erklärung mir nicht klar ist was passieren soll.
Als Funktion von was überhaupt?
Von wo nach wo geht die Funktion/Abbildung?
g=a*s-b*t ist keine Funktion, das ist eine Gleichung oder ein Term.

Übrigens ist bei Punkt 1 die zweite Zeile falsch.
Gegenbsp.:

Zitat:
Es funktioniert also nur nach diesem Schema?

Nein. Und das habe ich auch nicht behauptet.
Man kann genausogut z.B. den ad-hoc Weg aus der Musterlösung nehmen.
Meine Erfahrung lehrt mich aber, dass für Personen die sich im Thema unsicher fühlen ein Lösungsschema besser ist, als etwas das nicht ganz schematisch abläuft.

P.S. Scheinbar hast du dir die Mühe gemacht den Anhang selber zu tippen. Warum tippst du ihn nicht hier direkt, dann könnte man das wenigstens zitieren?
baba2k Auf diesen Beitrag antworten »

Vielen Dank für die schnelle Antwort. Ich werde das morgen mal Anhand einer der Aufgaben hier im Forum mit Beschreibung durchführen, dann kann man es auch zitieren. Jetzt muss ich schnell ins Bett, damit ich langsam in den "Klausurrythmus" komme. Ja, mit einem Schema komme ich tatsächlich besser klar, ich dachte nur, dass es vllt. zu lange dauert.

Gruß baba
baba2k Auf diesen Beitrag antworten »

So ich hab es mal versucht, die Aufgabe gibt 2 von 30 Punkten in der Klausur, bin ich einfach zu ungeübt?

Aufgabe:
Berechnen Sie ein, das und erfüllt.

Schritt 1: Prüfen, ob es eine Lösung gibt (Euklidischer Algorithmus).
es gibt mindestens eine Lösung.
es gibt kein welches die beiden Kongruenzen erfüllt (Aufgabe zu Ende).






Schritt 2: Beide Kongruenzen als Gleichung umschreiben.






Schritt 3: Werte für s und t ermitteln (Erweiterter euklidischer Algorithmus).
(Erweiterter euklidischer Algorithmus: )



Rückwärtseinsetzen:







Schritt 4: Ergebnis anpassen.
Aus Schritt 2: 5 = 11s - 13t
Aus Schritt 3: 1 = 6*11 - 5*13



Schritt 5: Lösung finden.


Irgend ein x welches die Kongruenzen erfüllt: x=334

Ab hier bin ich mir unsicher:



334/143=2 Rest 48

Erstes positives x welches die Kongruenzen erfüllt: x= 48

oder




-316/143=-2 Rest -30

Erstes negatives x welches die Kongruenzen erfüllt: x=-30
 
 
watcher Auf diesen Beitrag antworten »

Hallo,

Zitat:
die Aufgabe gibt 2 von 30 Punkten in der Klausur, bin ich einfach zu ungeübt?

ich erkenne zwischen diesen beiden Sätzen keinen wirklichen Zusammenhang.
Wofür bist du zu ungeübt (für 2 Punkte?)?

Zitat:
es gibt kein welches die beiden Kongruenzen erfüllt (Aufgabe zu Ende).

Das ist falsch. Hat auch Jamesn T. Kirk mit Gegenbeispiel schon angesprochen.

Der Rest ist zu umständlich. Bei kleinen Zahlen ist ggT-Bestimmung überPrimfaktorzerlegung im Kopf schneller, insbesondere hier bei zwei Primzahlen.

Der Rest stimmt.
(wobei es genügen würde s mod b und t mod a zu betrachten, das verringert den Aufwand aber nicht wirklich.)

Zitat:
Irgend ein x welches die Kongruenzen erfüllt: x=334

Und damit bist du mit der Aufgabe fertig.
Wenn nach dem kleinsten positiven x gefragt wäre, müsstest du weiterrechnen.

Es gilt hier aber allgemein:
-30 erfüllt das nicht.
baba2k Auf diesen Beitrag antworten »

Naja weil ich viel zu lang für so eine Aufgabe brauche und die nur 2 Punkte gibt, deswegen die Frage.

Mh das hab ich total übersehen gestern nacht mit dem Gegenbeispiel von Captain Kirk, was heißt es denn dann, wenn der ggT ungleich 1 ist?

x=-30 hab ich mit der zweiten Kongruenz erreichnet, dort habe ich t eingesetzt, das ist also falsch?
watcher Auf diesen Beitrag antworten »

Zitat:
Naja weil ich viel zu lang für so eine Aufgabe brauche und die nur 2 Punkte gibt, deswegen die Frage.

Ich gehe jetzt mal von 2h Std. Klausur aus.
Dann wären das, bei linearer Zeitverteilung, 8 Minuten. Das ist für die Aufgabe schaffbar.
Ferner könnte es sein, dass die Aufgabe wenigr Punkte, da es eine reine Rechen- und keine Denkaufgabe ist

Zitat:
x=-30 hab ich mit der zweiten Kongruenz erreichnet, dort habe ich t eingesetzt, das ist also falsch?

Es ist falsch. Das erkennt man mit einer kurzen Probe sofort.
Und was du da gerechnet hast ist mir schleierhaft, da die Aussage
Zitat:

aus dem nirgendwo erscheint.

Zitat:
Mh das hab ich total übersehen gestern nacht mit dem Gegenbeispiel von Captain Kirk, was heißt es denn dann, wenn der ggT ungleich 1 ist?

Siehe z.B. hier
baba2k Auf diesen Beitrag antworten »

Mh, das mit dem chinesischen Satz, muss ich mir glaub noch ein paar mal durchlesen bis ich das verstehe. Mein Schema hat bis jetzt eigentlich immer funktioniert unglücklich

Hier zu der Lösung:






334/143=2 Rest 48

Erstes positives x welches die Kongruenzen erfüllt: x= 48


Hier war ein Fehler im Latexcode. Die Zeile wurde ohne Fehlermeldung einfach nicht angezeigt:






-316/143=-2 Rest -30

Erstes negatives x welches die Kongruenzen erfüllt: x=-30
watcher Auf diesen Beitrag antworten »

Zitat:
das mit dem chinesischen Satz,

Der heißt chinesischer Restsatz und ist einer der wichtigsten Sätze der (elementaren) Zahlentheorie. Ein gewisses Verständnis dafür wäre also ganz nützlich.
Genauso wie sauberes Arbeiten, Schreiben und Bezeichnen von Objekten - eine der grundlegenden Fähigkeiten in der Mathematik.

Zitat:
Schritt 4: Ergebnis anpassen.
Aus Schritt 2: 5 = 11s - 13t
Aus Schritt 3: 1 = 6*11 - 5*13

Es ist t=25 nicht t=-25, da in der ersten Zeile -13t steht.
baba2k Auf diesen Beitrag antworten »

Ah super, vielen Dank, das ist genau das selbe Problem, was ich im anderen Thread hatte. Jetzt hab ich zumindest das schonmal verstanden.

Ich bin absolut unbegabt in Mathe, es ist zum Glück auch mein letztes Fach über die Mathematik. Ich muss da jetzt noch irgendwie durchkommen. Ich schau mir das jetzt nochmal in Ruhe an.

Gruß baba
watcher Auf diesen Beitrag antworten »

Zitat:
Ich bin absolut unbegabt in Mathe,

Wenn man es sich oft genug sagt stimmts auch. Nennt sich selbsterfüllende Prophezeiung.
Mal ganz abgesehen davon, dass das Ausführen von Algorithmen mit Begabung imho nicht viel zu tun hat.
baba2k Auf diesen Beitrag antworten »

Naja wenn ich wüsste was ich genau machen muss dann wäre es nicht so schwierig. Ich habe eben mit einem Komilitonen gesprochen, der machts anscheinend auch so wie ich. Er rechnet nur bei ggT=1 weiter und sagt bei , dass es keine Lösung gibt.

Ich werde aus dem Wikipedia-Artikel nicht schlau. Habe mir jetzt noch einige andere Webseiten darüber angeschaut, aber irgendwie hat das alles nichts mit meiner Aufgabe zu tun. Kann ich den Schritt einfach weglassen in der Klausur?

Vllt hat jemand noch einen Tipp für mich, was für mich bedeutet.

Vielen Dank!

Gruß baba
watcher Auf diesen Beitrag antworten »

Ein Zitat aus dem verlinkten Wikipedia-Artikel:
Zitat:
Auch im Fall, dass die Moduln nicht teilerfremd sind, existiert manchmal eine Lösung. Die genaue Bedingung lautet: Eine Lösung der simultanen Kongruenz existiert genau dann, wenn für alle i \neq j gilt: a_i \equiv a_j \mod{} ggT(m_i, m_j). Alle Lösungen sind dann kongruent modulo dem kgV der m_i.

Ist daran irgendwas unklar?

Zitat:
Ich habe eben mit einem Komilitonen gesprochen, der machts anscheinend auch so wie ich. Er rechnet nur bei ggT=1 weiter und sagt bei , dass es keine Lösung gibt.

traurig Und was willst du damit aussagen, dass er es genauso falsch macht.
Die Aussage ist schlicht falsch, ein Gegenbeispiel steht hier im Thread.
baba2k Auf diesen Beitrag antworten »

Also d.h. wenn ggT=1 sind die Zahlen teilerfremd und wenn /not=1 sind sie nicht teilerfremd, ich muss aber in jedenfall alle Schritte ausführen um das x zu errechnen?

Danke!

Gruß baba
watcher Auf diesen Beitrag antworten »

Zitat:
d.h. wenn ggT=1 sind die Zahlen teilerfremd u

Welche Zahlen?


Zitat:
ich muss aber in jedenfall alle Schritte ausführen um das x zu errechnen?

Naturlich kannst du dann nicht genauso verfahren wie im Fall teilerfremder Moduln.
Du kannst z.B. das Verfahren aus dem Wikipediaartikel verwenden ("Direktes Lösen simultaner Kongruenzen").
Das ist eine leichte Modifikation deines Verfahrens.
baba2k Auf diesen Beitrag antworten »

Ich meine die ggT(a,b)=1 => a ist teilerfremd zu b

Okay danke, schaue mir das nochmal an.
Neue Frage »
Antworten »



Verwandte Themen

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