Primzahlaufgabe

Neue Frage »

Juli86 Auf diesen Beitrag antworten »
Primzahlaufgabe
Hallo, ich habe folgende Aufgabe zu lösen und komme noch nicht so wirklich weiter, weiß jemand einen Tipp für mich:

Sei M eine Teilmenge von P mit der folgenden Eigenschaft: x,y Element von M mit x*y+4 ebenfalls Element von M. Bestimme die Elemente dieser Menge M. Bemerkung: Mit P ist die Menge der Primzahlen gemeint.
Juli86 Auf diesen Beitrag antworten »
RE: Primzahlaufgabe
Ach so meine bisherige Überlegung ist:

Die Zahl 2 kann nicht Element der Menge M sein, da das Ergebnis immer eine gerade Zahl wäre, welche dann keine Primzahl sein kann.
AD Auf diesen Beitrag antworten »

Das Ergebnis dieser Aufgabe kann nur sein, dass leer ist. Ansonsten hätte man einen prima Algorithmus gefunden, um neue größere Primzahlen zu finden. Augenzwinkern

Beim Beweis muss man eben nach und nach durch Widerspruch ausschließen, dass auch nur irgendeine Primzahl enthalten kann. Mit 2 hast du das schon mal gut angefangen, natürlich musst du das in der Folge etwas systematischer machen, etwas durch Betrachtung gewisser Restklassen.
Tipp: Versuch's mal mit Modul 7
Übrigens eine sehr schöne Aufgabe, die muss ich mir merken. Freude
WebFritzi Auf diesen Beitrag antworten »

So wie ich das sehe, kann man auch "x² + 4 in M" statt "xy + 4 in M" schreiben. Keine Ahnung, ob es das leichter macht.
AD Auf diesen Beitrag antworten »

Leichter auf gar keinen Fall, denn jeder Beweis für "x²+4" funktioniert auch bei "xy+4".

Ich würde sagen: Schwerer, denn mein Kurzbeweis funktioniert dann nicht mehr. Augenzwinkern
WebFritzi Auf diesen Beitrag antworten »

Ah, ok. Wusste ich nicht. Hab ja keine Ahnung, wie man das beweisen könnte. Bin halt ne Null in Algebra. Vielleicht auch sonst, aber in Algebra auf jeden Fall. Augenzwinkern
 
 
AD Auf diesen Beitrag antworten »

Du hast mich aber nochmal zum "Nachsitzen" gebracht: Auch das schwierigere Problem mit x²+4 ist mit derselben Methode knackbar - wenn auch unter Einsatz eines anderen Moduls. Augenzwinkern nämlich Modul 13
WebFritzi Auf diesen Beitrag antworten »

Ich hab nichts anderes von dir erwartet! Dann lass mal Juli die Module knacken. Augenzwinkern
Juli86 Auf diesen Beitrag antworten »

Jo, das werde ich tun! Bzw. versuchen
Juli86 Auf diesen Beitrag antworten »

Ich habe noch einmal eine Frage zu dem Problem. Du meintest ja, dass man gewisse Restklassen betrachten muss. Meinst du damit die Restklassen von dem Ergebnis der Aufgabe, wenn man Zahlen einsetzen würde?

Bisher habe ich nämlich nur folgende Überlegung: Das Produkt zweier Primzahlen ist eine ungerade nicht-Primzahl. Würde man dazu nun die Zahl 1 oder 3 addieren, so hätte man eine gerade Zahl, also wieder keine Primzahl. Würde man 2 oder 4 dazu addieren so würde die Zahl jedoch ungerade sein. Nur weiß ich nicht, wie man nun zeigt, dass es keine Primzahl sein kann, die in die Menge M gehört.

Kannst du mir da noch mal weiterhelfen?
AD Auf diesen Beitrag antworten »

Naja, ich hab's oben ja schon verraten, allerdings versteckt (blaue Schrift auf blauem Untergrund Big Laugh ):

Betrachte die Reste modulo 13 - in dem Fall eine Glückszahl. Dann stellt sich nämlich heraus, dass die iterierte Kette irgendwann immer bei , also bei einer durch 13 teilbaren Zahl landet. Diese Zahl ist dann (sofern größer als 13) natürlich keine Primzahl, womit der Ausgangspunkt dieser Kette nicht in liegen darf.

Wenn man also diese Kette für alle möglichen Reste derart untersucht, ist man am Ziel: ist leer.
Juli86 Auf diesen Beitrag antworten »

Irgendwie stehe ich noch ein bisschen auf dem Schlauch,

erst einmal, was meinst du mit einer iterierten Kette? Ich kenne eine Iteration nur im Zusammenhang mit Selbstabbildungen. Und die Reste wovon sind gemeint? Ich glaube, ich brauche noch ein paar Informationen, damit ich diese Aufgabe verstehe.
Juli86 Auf diesen Beitrag antworten »

Wenn ich z.B. annehme, dass 5 Element M ist, erhalte ich: 5²+4=29 (Primzahl), dann 29²+4=845, dies ist durch 5 teilbar, somit keine Primzahl. Aber ich dachte, da müssten nun immer Vielfache von 13 herauskommen, oder habe ich das falsch verstanden?
AD Auf diesen Beitrag antworten »

Zum einen ist 845 auch durch 13 teilbar. Augenzwinkern

Und zum anderen habe ich nicht behauptet, dass gleich die erste Nicht-Primzahl in der durch erzeugten Kette durch 13 teilbar ist - sondern nur, dass irgendwann eine durch 13 teilbare Zahl auftaucht!!! Das "irgenwann" heißt sogar konkret nach maximal 6 Schritten. Also bitte genau nachdenken.
Juli86 Auf diesen Beitrag antworten »

Also, wenn ich das jetzt richtig verstehe, dann muss spätestens bei der Gleichung eine durch 13 teilbare Zahl herauskommen, oder? Irgendwie fehlt mir aber noch der Zusammenhang zu dieser Zahl, warum ist das denn gerade die Zahl 13?
AD Auf diesen Beitrag antworten »

Zitat:
Original von Juli86
warum ist das denn gerade die Zahl 13?

Weil es da eben so klappt. Glaub bloß nicht, dass 13 der erste Modul war, den ich probiert habe, da kamen 3, 5, 7, 11 vorher dran!
Juli86 Auf diesen Beitrag antworten »

Ach so, also bist du mit den kleinsten Primzahlen angefangen. Aber was genau meinst du immer mit Modul? Modulo kenne ich nur als Rest und 13 ist ja nicht der Rest sondern ein Teiler der Zahl, oder?
AD Auf diesen Beitrag antworten »

Herrje... Ich rede von Modul 13, weil ich hier mit Restklassen modulo 13 gerechnet habe. Ich dachte, da wäre jetzt endlich mal klar. Forum Kloppe
Juli86 Auf diesen Beitrag antworten »

Sorry, dass ich gerade etwas schwer von Begriff bin. Ich versuche jetzt mal zu erklären, wie ich das nun verstehe:

Du hast die Aufgabe also gelöst, indem du Restklassen betrachtet hast, die den Rest 3, 5, 7, 11, 13 lassen (z.B. 0 modulo 3). Es gab dann aber nur bei Modul 13 eine Lösung. Hast du da denn irgendwelche Zahlen eingesetzt oder das ganz allgemein behandelt um es zu beweisen? Ach so, noch einmal zum Verständnis: Die Restklassen beziehen sich doch immer auf das , oder? Also auf die Lösung?
AD Auf diesen Beitrag antworten »

Ich hab den Kerngedanken der Lösung eigentlich vollständig skizzierst, aber aus irgendwelchen Gründen hast du keine Lust, die Einzelschritte durchzuführen. verwirrt

Dann mach ich es halt, die Aufgabe ist zu schön, um sie von dir zerreden zu lassen. Als erstes stellt man mal eine Tabelle auf:




Daraus kann man jetzt folgend Kette ablesen:

, entspricht 6 Schritten (*)

Die meisten anderen (außer die mit beginnende) Ketten sind davon lediglich Teilketten. Ich führe sie trotzdem mal auf:

, entspricht 3 Schritten

, entspricht 3 Schritten

, entspricht 1 Schritt

, entspricht 5 Schritten

, entspricht 2 Schritten

, entspricht 4 Schritten


Damit ist nachgewiesen, dass man für jede natürliche Zahl nach spätestens 6 Schritten auf eine durch 13 teilbare Zahl stößt - damit kann M keine Elemente enthalten, qed.


Anmerkung:

Die mit 0 beginnende Kette ist notwendig wegen der Zahl 13 selbst: Die ist ja Primzahl, womit für sie selbst die Teilbarkeit durch 13 nicht als "Nicht-Primzahl-Kriterium ausreicht. Aber Kette (*) sichert, dass man auch von 13 beginnend nach genau 6 Schritten wieder bei einer größeren durch 13 teilbaren Zahl anlangt, die dann garantiert keine Primzahl ist. Augenzwinkern
Juli86 Auf diesen Beitrag antworten »

Vielen Dank für die Lösung, jetzt habe ich auch endlich verstanden, was du mit den Restklassen und Modul usw. meintest. Das war mir vorher wirklich sehr schleierhaft, da ich bisher noch nie eine Aufgabe so gelöst habe, soweit ich mich erinnere.

Trotzdem habe ich noch einmal eine Frage: Du hast jetzt ja immer den Fall betrachtet, dass x=y ist. Wenn x und y jedoch verschiedene Primzahlen sind, welche Restklassen muss ich denn dann betrachten. Ich hoffe meine Frage wird am folgenden Beispiel deutlich: muss ich da nun die Restklasse von 3 oder von 5 betrachten oder von deren Produkt also von 15? (Also im oberen Teil deiner Tabelle sozusagen, dann entweder bei 3, 5 oder 2(=>15-2=13)?)
Kann man dort dann auch mit Modul 13 arbeiten? Oder muss ich dann wie du vorher mal meintest Modul 7 nehmen?
AD Auf diesen Beitrag antworten »

Zitat:
Original von Juli86
Wenn x und y jedoch verschiedene Primzahlen sind, welche Restklassen muss ich denn dann betrachten.

Soll das jetzt heißen, du willst die Originalaufgabe abändern? Ansonsten wüsste ich nicht, welchen Sinn die Betrachtung von haben soll, wenn bereits die Betrachtung von zu einem Widerspruch (d.h. leerer Menge M) führt. Es scheint mir, als hast du die Beweisstruktur immer noch nicht begriffen: unglücklich

Es handelt sich bei meinem Vorgehen um einen indirekten Beweis: Die Annahme. dass ein existiert, wird zum Widerspruch geführt, weil nach spätestens 6 Schritten unter Einsatz der Regel

,

(jeweils speziell nur für y=x angewandt, warum nicht?) eine Nichtprimzahl zu gehören muss, was nach Voraussetzung unzulässig ist.


Es sei denn du änderst die Aufgabe ab, etwa so:

Zitat:
Sei eine Teilmenge der Menge aller Primzahlen mit der folgenden Eigenschaft:

Für mit gilt .

Bestimme die Elemente dieser Menge .

In dem Fall stimmt die Lösung auch gar nicht mehr: Es gibt dann wenigstens die Einermengen-Lösungen mit , wenn nicht noch mehr. Was ich allerdings nicht glaube, es bliebe allerdings zu untersuchen, wenn denn die Aufgabenstellung so geändert würde...
Juli86 Auf diesen Beitrag antworten »

Ok, ich war mir nur nicht sicher, ob man nicht alle möglichen Fälle betrachten muss. Dann bin ich so jetzt zufrieden. Vielen, vielen Dank, da wäre ich alleine nie darauf gekommen.
Juli86 Auf diesen Beitrag antworten »

Ich habe nochmal eine Frage zu der Lösung der Aufgabe und zwar muss ich die Aufgabe ja auch mit Defintionen oder Sätzen erklären. Zu dem Restklassenbegriff habe ich aber bisher nur die Defintion gefunden, dass es alle Zahlen kleiner als die Restklasse sind. In diesem Falll also von 0 bis 12. Nun hast du ja die Zahlen 7 bis 12 unter -6 bis -1 zusammengefasst. Ich habe aber noch keine Definition oder keinen Satz gefunden, der dazu passt. Denn eigentlich sagt ein Satz über die Reste ja auch aus, dass sie immer positiv sein müssen (oder liege ich da jetzt falsch?)
AD Auf diesen Beitrag antworten »

Tja, das tut mir jetzt leid - ich hatte angenommen, du kennst die Grundlagen der Restklassenrechnung. Wenn du dir die anschaust, dann wirst du sehen, dass beispielsweise die Restklasse -5 und 8 modulo 13 identisch sind, usw. ... es ist hier wirklich nicht der Platz, das alles zu erklären, dafür gibt es gewiss bessere Quellen.
Juli86 Auf diesen Beitrag antworten »

Ich wollte auch gar nicht, dass du mir das alles erklärst. Leider finde ich nur schwer Literatur zu dem Thema Restklassen. Gibt es denn noch einen anderen Begriff dazu bzw. was genau ist denn das Oberthema dazu? (ich wüsste nur dass es zur arithmetik oder algebra gehört). Vielleicht würde mir das ja bei der Literatursuche helfen.
Juli86 Auf diesen Beitrag antworten »

Ich habe die Aufgabe versucht nun noch einmal anders zu lösen, da mir gesagt wurde, dass das mit dem Modul 13 kein allgemeiner Beweis ist.

Ich bin nun so vorgegangen: p Element M mit p²+4 Element M. Spinnt man das nun weiter entstehen folgende Gleichungen: p*(p²+4)+4 Element M, p*(p³+4p+4)+4 Element M???? Irgendwie müsste ich hier ja nun auf einen Widerspruch kommen, das heißt, dass p*(p³+4p+4)+4 keine Primzahl sein kann. Ich finde ihn nur noch nicht. Aber vielleicht findet ihn ja jemand von euch?
sqrt4 Auf diesen Beitrag antworten »

Zitat:
Original von Juli86
[...], da mir gesagt wurde, dass das mit dem Modul 13 kein allgemeiner Beweis ist.


Hoffentlich sieht das der Arthur nicht Augenzwinkern Der Beweis is schon einwandfrei. Und wenn das dein Lehrer gesagt hat, kannst du ihn ja eines besseren belehren. Augenzwinkern

Mir scheint, du hast das Vorgehen mit den Restklassen noch nicht ganz verstanden, oder?

Angenommen es gäbe in der Menge eine Primzahl p. Diese Zahl p lässt beim teilen durch 13 einen Rest aus der Menge Du kannst p also schreiben als


Wenden wir nun die Regel an. x,y sind da als beliebig aus der Menge vorausgesetzt, du kannst also insbesondere x=y=p wählen.
Das ergibt


Die ersten beiden Summanden sind schon mal sicher durch 13 teilbar. Wenn jetzt auch durch 13 teilbar ist, sind wir fertig.
Das ist zum zum Beispiel bei r=3 oder r=10 der Fall. Das heißt eine Primzahl die beim teilen durch 13 den Rest 3 oder 10 lässt kann schon mal sicher nicht in M liegen.

Ist das nicht der Fall, dann können wir aber schreiben als
Das heißt als eine Zahl die beim teilen durch 13 den Rest (r^2+4) lässt. setzen wir und Dann hat p^2+4 die Form


Jetzt beginnt das Spiel von vorne, aber mit dem Rest
In diesem 2. Schritt stellt man jetzt fest, dass wenn der urpsrüngliche Rest r=5 oder r=8 war, dann ist die Zahl durch 13 teilbar.

Und so geht es weiter bis man alle Reste durchhat (wie Arthur bereits gesagt hat is nach 6 Runden schluss)
Neue Frage »
Antworten »



Verwandte Themen

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