Primzahlen < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 12:38 Sa 27.12.2008 | | Autor: | Murx |
| Aufgabe | | Zeige: Es existieren unendlich viele Primzahlen der Form n²+n+1. |
Hallo zusammen,
ich weiß nicht so recht, wie ich diese Aufgabe lösen soll.
Kann man das mit Induktion machen? Sieht ein wenig danach aus.
Ich hab das bisher so gemacht:
I.Anfang: n=1: 1+1+1=3 = primzahl
I.Voraussetzung: Sei die Beh. gezeigt für ein festes n [mm] \in \IN. [/mm]
I. Schritt: n [mm] \mapsto [/mm] n+1:
(n+1)² + n+1 + 1 = n² + 2n + 1 + n + 2 = (n² + n + 1) + 2n+2
Und dann ist ja der Term in der Klammer n. Ind.Vor. wieder ne Primzahl. Aber was mach ich mit 2n +2? Kann das ja höchstens noch als 2(n+1) schreiben. Da seh ich aber nun nicht mehr wie es weitergeht, denn 2(n+1) ergibt ja nicht immer ne Primzahle (vgl. n=3). Zudem ergibt ja auch die Summe von zwei Primzahlen nicht wieder eine Primzahl (denn 3+7=10 und 10 ist keine Primzahl)...
Kann mir da vielleicht jemand weiterhelfen? Danke schonmal.
|
|
| |
|
Hallo Murx,
sollte es Dir gelingen, diese Aufgabe per vollständiger Induktion zu lösen, wäre Dir die Fields-Medaille (sozusagen der Nobelpreis für Mathematik) nahezu sicher.
Du hättest dann nämlich eine Formel bewiesen, mit der man verlässlich Primzahlen erzeugen kann! Das wäre besser als jeder Primzahltest...
Mit anderen Worten: so kannst du nicht vorgehen.
Du sollst zeigen, dass in der unendlichen Folge von Zahlen, die Deine Formel erzeugt, unendlich viele Primzahlen enthalten sind, es also nicht eine größte Primzahl in der Folge gibt, nach der dann nur noch zusammengesetzte Zahlen kommen.
Die ersten Glieder der Folge [mm] a_n=n^2+n+1 [/mm] sind ja 3, 7, 13, 21, 31, 43, 57, 73, 91, 111, 133, 157 ...
Kennst Du den Beweis, warum es unendlich viele Primzahlen gibt? Vielleicht bringt der Dich ja auf eine Idee?
Grüße,
reverend
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 13:09 Sa 27.12.2008 | | Autor: | Murx |
Hallo reverend,
gut, dann werd ich das wohl ohne Induktion machen müssen...
Den Beweis dazu, das es unendlich viele Primzahlen gibt, kenne ich. Leider sehe ich da dennoch keinen Ansatz für meine Aufgabe.
Kannst du mir da vielleicht einen kleinen Denkanstoß geben?
Grüße Murx
|
|
|
| |
|
Um ehrlich zu sein, sehe ich im Moment auch noch keinen Lösungsansatz, der zum Erfolg führt. Mir ging es erst einmal nur um die Beweistechnik. Da bin ich sicher, dass Du irgendwie aus der Annahme, es gebe eine größte Primzahl der Form [mm] n^2+n+1, [/mm] einen Widerspruch konstruieren musst. Darum der Hinweis auf den Beweis, dass es keine größte Primzahl geben kann.
Es ist leicht zu zeigen, dass für [mm] n\equiv 1\mod{3} [/mm] das Ergebnis nicht prim sein kann. Das hilft aber leider an dieser Stelle gar nicht weiter.
Auch der "kleine Fermat" scheint nicht weiterzuhelfen, sonst auch immer ein mächtiges Werkzeug bei Beweisen zum Thema Primzahlen. Selbst eine Verbindung zum (unbewiesenen) "Riemann" sehe ich nicht.
Wenn mir stattdessen mal was Hilfreiches einfällt, melde ich mich aber natürlich wieder.
Einstweilen: viel Erfolg!
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 02:08 So 28.12.2008 | | Autor: | reverend |
Ich bin noch kein Stück weiter.
Beiliegend eine ![[a]](/images/paperclip.gif "Dateianhänge") Excel-Tabelle für [mm] 1\le n\le100.
[/mm]
Es sieht nicht nach Zufall aus: außer der 3 haben alle Primteiler die Form [mm] \a{}6k+1. [/mm] Gibt es dafür einen Grund? Oder tauchen Primzahlen der Form [mm] \a{}6k\red{-}1 [/mm] einfach erst später auf, warum auch immer? Sind sie seltener?
Dass [mm] n^2+n+1=(n+1)^2-n [/mm] ist, hat mir leider bisher auch nicht weitergeholfen.
Dateianhänge:
Anhang Nr. 1 (Typ: xls) [nicht öffentlich]
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 19:59 So 28.12.2008 | | Autor: | Dath |
Ich bin mir auch nicht sicher, aber man kann ja an sich jede Zahl in sog. Primfaktoren zerlegen. Wenn man zeigen kann, dass das hier nicht gilt, dann wäre man doch ein Stück weiter, oder?
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 20:08 So 28.12.2008 | | Autor: | reverend |
Ja, das wäre man. Die Zahlentheorie wäre einen großen Schritt weiter, wenn sie das allgemein zeigen könnte.
Selbst bei dem hier schon erwähnten euklidschen Beweis, dass die Menge der Primzahlen unendlich ist, wird für die im wesentlichen Beweisschritt untersuchte Zahl nicht gezeigt, dass sie prim ist, sondern nur, dass sie keine schon bekannten Primfaktoren haben kann, obwohl die Voraussetzung doch war, dass bis zur angenommenen größten Primzahl alle Primzahlen (und damit alle insgesamt) bekannt seien. Also ist die Voraussetzung falsch.
Man kann für diesen Primzahlgenerator zeigen, dass jeder Teiler, der einmal auftritt, mit vorhersagbarer Regelmäßigkeit wieder auftritt. Man kann daher zeigen, dass die Funktion unendlich viele zusammengesetzte Zahlen erzeugt. Allerdings erlaubt die Abbildung nicht, die Regelmäßigkeit so auf die natürlichen Zahlen zu übertragen, dass man die dort bekannten Sätze (wie eben die Unendlichkeit der Primzahlen) anwenden könnte.
Selbst schöne Funde wie der kleine Fermat oder der Satz von Dirichlet sind hier nicht hilfreich.
Ich schließe mich daher erst einmal der Frage von FelixF an: in welchem Kontext wurde diese Aufgabe denn gestellt?
Meine Vermutung ist ja, dass das eine typische Übungsaufgabe eines etwas überarbeiteten Assis ist, dem noch nicht aufgefallen ist, in welche Falle er mit seiner Musterlösung tappt. Das passiert jedem mal, aber es kommen dann eben so Aufgaben heraus, an denen Studenten verzweifeln müssen. Dies ist wohl so eine.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 09:02 So 28.12.2008 | | Autor: | Karl_Pech |
Hallo Murx,
Als ich diese Aufgabe gesehen habe, fiel mir wage der Begriff "Primzahlgenerator" ein. Eine Google-Suche mit "Primzahlgenerator Polynom" liefert dann z.B. folgenden ![[]](/images/popup.gif) Treffer. Hilft das irgendwie?
Viele Grüße
Karl
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 09:34 So 28.12.2008 | | Autor: | reverend |
Toller Fund, Karl_Pech!
Ich sehe noch nicht, inwiefern er die vorliegende Aufgabe lösen hilft, aber er stärkt doch die Hoffnung, dass es eine Lösung gibt.
"So liegen zum Beispiel nur die Primzahlen der Form 6*k+1 auf dem Polynom [mm] f(x)=x^2+x+1."
[/mm]
Alle Primzahlen dieser Form? Es scheint so, aber ich kann es bisher nicht beweisen. Mit dem Beweis ware ja zugleich die Aufgabe gelöst.
edit: Nein, das ist ein Denkfehler. Es könnten ja alle solchen Primzahlen nur in Zusammensetzungen vorkommen. Schade.
Liebe Grüße,
reverend
|
|
|
| |
|
Hallo zusammen,
Also ich hab mir mal das mit dem Siebverfahren ordentlich durchgelesen, und sehe nicht so recht, dass das bei dieser Aufgabe so viel weiterhilft!
Es zeigt "nur", wie viele und welche Teiler(!!!) der Funktionswerte einer Funktion f prim sind.
D.h. z.B. bei f(7)=57=19*f(1). So wie ich die Aufgabe aber verstanden hab geht es darum z.z., dass unendlich viele Primzahlen durch die Funkion [mm] f(n)=n^{2}+n+1 [/mm] einer bstimmten Menge (z.B. [mm] \IN) [/mm] zugeordnet werden.
Ich such auch schon ne Weile, weil ich die Aufgabe sehr schön finde, komme aber auch nicht recht weiter...
Ich freu mich auch schon auf die Lösung!
lg Kai
Ps.: Wünsche allen einen guten Rutsch!
|
|
|
| |
|
Nach einer Menge Recherche (finde das Problem so spannend...) lässt sich nahezu sicher sagen, dass bisher niemand diese Aufgabe gelöst hat. Sie ist Teil einiger der harten und großen Probleme der Zahlentheorie.
"Können irreduzible Polynome vom Grade [mm] \ge [/mm] 2 unendlich viele Primzahlen darstellen?
[Diese Frage ist o ffen, selbst für [mm] \blue{f(n)=n^2+1} [/mm] ]"
aus: Wolfgang Schwarz, Aus der Geschichte der Zahlentheorie, S. 47
Genauer: die Frage ist noch für kein einziges Polynom gelöst!
Siehe auch diese Dissertation von Markus Köcher und suche nach dem Namen Bouniakowsky.
Liebe Grüße,
reverend
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 17:04 So 28.12.2008 | | Autor: | Murx |
Hallo,
erstmal Danke für die ganzen Bemühungen zu dieser Aufgabe!
Verstehe ich das richtig, das ich diese Aufgabe also momentan gar nicht lösen kann, selbst wenn ich wollte?
Aber irgendeine Lösung muss es doch geben. Warum sonst wird mir eine solche Aufgabe gestellt? Was ist der Sinn dahinter?
Hat nicht irgendeiner ne Idee, was man sonst mit dieser Aufgabe anfangen kann?
Grüße, Murx
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 19:08 So 28.12.2008 | | Autor: | felixf |
Hallo
> erstmal Danke für die ganzen Bemühungen zu dieser Aufgabe!
>
> Verstehe ich das richtig, das ich diese Aufgabe also
> momentan gar nicht lösen kann, selbst wenn ich wollte?
>
> Aber irgendeine Lösung muss es doch geben. Warum sonst wird
> mir eine solche Aufgabe gestellt? Was ist der Sinn
> dahinter?
Nun, wo und in welchem Kontext wurde die Aufgabe denn gestellt?
Vielleicht hilft das etwas weiter...
LG Felix
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 20:59 So 28.12.2008 | | Autor: | Murx |
Hallo,
also die Aufgabe wurde mir in der VL Zahlentheorie gestellt. Zurzeit behandeln wir pellsche Gleichungen und Kettenbrüche (auch periodische).
Ich bezweifle allerdings, das man die Aufgabe damit lösen kann.
Mir hilft das leider zur Zeit nicht viel weiter...
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 21:38 So 28.12.2008 | | Autor: | felixf |
Hallo
> also die Aufgabe wurde mir in der VL Zahlentheorie
> gestellt. Zurzeit behandeln wir pellsche Gleichungen und
> Kettenbrüche (auch periodische).
>
> Ich bezweifle allerdings, das man die Aufgabe damit lösen
> kann.
Ja...
Falls wir hier keine Loesung herausbekommen, so schreib doch bitte hier die in den Uebungen besprochende Loesung hin; ich denke das wuerd einige der Leute hier ziemlich interessieren -- mich eingeschlossen :)
Anyway, viel Glueck/Erfolg noch... Wenn mir noch was einfaellt melde ich mich.
LG Felix
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 23:54 So 28.12.2008 | | Autor: | reverend |
Oh ja, bitte. Die Aufgabe ist schön und die Lösung wohl noch fern: ich bin auch interessiert.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 14:28 Mo 29.12.2008 | | Autor: | Murx |
Hallo zusammen,
gern schreib ich die besprochene Lösung hier ins Forum. Ich bin auch schon gespannt wie sie aussehen wird. Dies wird aber noch was dauern. Wir besprechen die Lösung erst Ende nächster Woche.
Grüße, Murx
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 19:50 Do 08.01.2009 | | Autor: | Murx |
Hallo zusammen,
ich wollte euch die Besprechung der Aufgabe schreiben, da sich ja mehrere dafür interessiert hatten. Aber leider gibt es keine. Wir haben die Aufgabe in der Übung nicht besprochen und sie wurde aus der Bewertung rausgenommen.
Das Problem ist, dass man eingesehen hat, das die Aufgabe so nicht für uns lösbar ist.
Gesucht war eigentlich der Beweis zu folgender Aussage:
In der Folge 6k+1 gibt es unendlich viele Primzahlen (oder so ähnlich). Das soll wohl angeblich mit n²+n+1 lösbar sein.
Ich versteh leider nicht, wie man die gewünschte Fragestellung fälschlicherweise so komplett in eine andere Richtung gehend formulieren kann.
Ich hätte mich auch über eine Lösung gefreut. Sorry.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 19:56 Do 08.01.2009 | | Autor: | reverend |
Hallo Murx,
das ist eine nette Formulierung: "so nicht für uns lösbar ist". 
> Gesucht war eigentlich der Beweis zu folgender Aussage:
> In der Folge 6k+1 gibt es unendlich viele Primzahlen (oder
> so ähnlich). Das soll wohl angeblich mit n²+n+1 lösbar
> sein.
Noch besser ohne [mm] n^2+n+1 [/mm] ...
Danke jedenfalls für die Mitteilung.
lg,
reverend
|
|
|
| |
|
Hallo leute,
ich habs doch nicht!
Ich wollte die Aussage so beweisen:
Ich setzte voraus, dass man weis, dass es unendlich viele Primzahlen geben muss:
Jetzt nehme ich an, dass [mm] \exists [/mm] größte Primzahl p der Form [mm] p=n^{2}+n+1 [/mm] und möchte dass zum Widerspruch führen, indem ich zeige, dass es dann noch eine größere Primzahl p' gibt, mit [mm] p'=t^{2}+t+1 [/mm] und p'>p.
Und das möchte ich so erzeugen:
p sei also die größte Primzahl in der gewünschten Form, d.h. es existiert keine größere Primzahl der Form [mm] n^{2}+n+1 [/mm] wie p, aber da es ja unendlich viele Primzahlen gibt, muss eine andere Primzahl q geben, die größer ist.
Ich interessiere mich nur für die kleinste Primzahl die größer ist (aber es geht auch mit jeder die größer ist allgemein), diese sei o.B.d.A. die Zahl q und sei o.E. die m-te Primzahl, wenn ich die Primzahlen der Reihe nach sortiert hätte. (d.h. a,b,c,...,p,q seien alle Primzahlen kleiner/gleich q, der größe nach sortiert)
Jetzt möchte ich die Zahl [mm] p'=(a*b*c*...*p*q)^{2}+a*b*c*...*p*q+1 [/mm] betrachten.
Ich kann kein a,b,c...,q vollständig ausklammern und somit nie ohne Rest durch a,b,c,...,q teilen. Damit muss p' doch eine Primzahl sein?!
---> Muss nicht, und da hängt der Beweis!!! <---
Nun muss ich nur noch zeigen, dass p'>p, aber das ist ja eig logisch, denn Primzahlen können nie negativ sein, und auch nie kleiner 2, damit muss p'>p!
Jetzt substituiere ich (a*b*c*...*p*q)=t und habe eine größere Primzahl als p in der Form [mm] p'=t^{2}+t+1.
[/mm]
lg Kai
Ps.: Wünsche euch ein gesundes neues Jahr!
|
|
|
| |
|
| Status: |
(Korrektur) fundamentaler Fehler  | | Datum: | 17:48 Do 01.01.2009 | | Autor: | pelzig |
> Jetzt möchte ich die Zahl
> [mm]p'=(a*b*c*...*p*q)^{2}+a*b*c*...*p*q+1[/mm] betrachten.
>
> Ich kann kein a,b,c...,q vollständig ausklammern und somit
> nie ohne Rest durch a,b,c,...,q teilen. Damit muss p' doch
> eine Primzahl sein?!
Das ist falsch. Es stimmt zwar, dass $p'$ nicht durch $a,b,c,..,p,q$ teilbar ist, aber das genügt nicht für p' prim.
Zum Beispiel ist für $t=2*3*5*7=210$ [mm] $p'=t^2+t+1=44311=73*607$. [/mm]
Auch in Euklids Beweis, dass es unendlich viele Primzahlen gibt, (Annahme, es gibt endlich viele Primzahlen [mm] $p_1,...,p_n$) [/mm] wird die Zahl [mm] $1+\prod_{i=1}^np_i$ [/mm] konstruiert, aber die ist natürlich i.A. auch keine Primzahl. Falls sie keine Primzahl ist, so enthält sie aber einen von [mm] $p_1,...,p_n$ [/mm] verschiedenen Primteiler - dass ist der eigentliche Widerspruch.
Gruß, Robert
|
|
|
|
