www.vorhilfe.de
Vorhilfe

Kostenlose Kommunikationsplattform für gegenseitige Hilfestellungen.
Hallo Gast!einloggen | registrieren ]
Startseite · Forum · Wissen · Kurse · Mitglieder · Team · Impressum
Forenbaum
^ Forenbaum
Status Vorhilfe
  Status Geisteswiss.
    Status Erdkunde
    Status Geschichte
    Status Jura
    Status Musik/Kunst
    Status Pädagogik
    Status Philosophie
    Status Politik/Wirtschaft
    Status Psychologie
    Status Religion
    Status Sozialwissenschaften
  Status Informatik
    Status Schule
    Status Hochschule
    Status Info-Training
    Status Wettbewerbe
    Status Praxis
    Status Internes IR
  Status Ingenieurwiss.
    Status Bauingenieurwesen
    Status Elektrotechnik
    Status Maschinenbau
    Status Materialwissenschaft
    Status Regelungstechnik
    Status Signaltheorie
    Status Sonstiges
    Status Technik
  Status Mathe
    Status Schulmathe
    Status Hochschulmathe
    Status Mathe-Vorkurse
    Status Mathe-Software
  Status Naturwiss.
    Status Astronomie
    Status Biologie
    Status Chemie
    Status Geowissenschaften
    Status Medizin
    Status Physik
    Status Sport
  Status Sonstiges / Diverses
  Status Sprachen
    Status Deutsch
    Status Englisch
    Status Französisch
    Status Griechisch
    Status Latein
    Status Russisch
    Status Spanisch
    Status Vorkurse
    Status Sonstiges (Sprachen)
  Status Neuerdings
  Status Internes VH
    Status Café VH
    Status Verbesserungen
    Status Benutzerbetreuung
    Status Plenum
    Status Datenbank-Forum
    Status Test-Forum
    Status Fragwürdige Inhalte
    Status VH e.V.

Gezeigt werden alle Foren bis zur Tiefe 2

Navigation
 Startseite...
 Neuerdings beta neu
 Forum...
 vorwissen...
 vorkurse...
 Werkzeuge...
 Nachhilfevermittlung beta...
 Online-Spiele beta
 Suchen
 Verein...
 Impressum
Das Projekt
Server und Internetanbindung werden durch Spenden finanziert.
Organisiert wird das Projekt von unserem Koordinatorenteam.
Hunderte Mitglieder helfen ehrenamtlich in unseren moderierten Foren.
Anbieter der Seite ist der gemeinnützige Verein "Vorhilfe.de e.V.".
Partnerseiten
Dt. Schulen im Ausland: Mathe-Seiten:

Open Source FunktionenplotterFunkyPlot: Kostenloser und quelloffener Funktionenplotter für Linux und andere Betriebssysteme
Forum "Zahlentheorie" - Primzahlen
Primzahlen < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
Ansicht: [ geschachtelt ] | ^ Forum "Zahlentheorie"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien

Primzahlen: Frage (beantwortet)
Status: (Frage) beantwortet Status 
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.

        
Bezug
Primzahlen: Antwort
Status: (Antwort) fertig Status 
Datum: 12:53 Sa 27.12.2008
Autor: reverend

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

Bezug
                
Bezug
Primzahlen: Frage (beantwortet)
Status: (Frage) beantwortet Status 
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

Bezug
                        
Bezug
Primzahlen: Antwort
Status: (Antwort) fertig Status 
Datum: 13:21 Sa 27.12.2008
Autor: reverend

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!



Bezug
                                
Bezug
Primzahlen: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 02:08 So 28.12.2008
Autor: reverend

Ich bin noch kein Stück weiter.

Beiliegend eine [a]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]
Bezug
                                        
Bezug
Primzahlen: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
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?

Bezug
                                                
Bezug
Primzahlen: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
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.

Bezug
                        
Bezug
Primzahlen: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
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 []Treffer. Hilft das irgendwie?



Viele Grüße
Karl




Bezug
                                
Bezug
Primzahlen: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
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

Bezug
                                        
Bezug
Primzahlen: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 17:46 Mo 29.12.2008
Autor: kuemmelsche

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!

Bezug
                        
Bezug
Primzahlen: unbewiesen!
Status: (Antwort) fertig Status 
Datum: 11:47 So 28.12.2008
Autor: reverend

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

Bezug
                                
Bezug
Primzahlen: Frage (beantwortet)
Status: (Frage) beantwortet Status 
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

Bezug
                                        
Bezug
Primzahlen: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
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


Bezug
                                                
Bezug
Primzahlen: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
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...

Bezug
                                                        
Bezug
Primzahlen: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
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


Bezug
                                                                
Bezug
Primzahlen: unterstützt
Status: (Mitteilung) Reaktion unnötig Status 
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.

Bezug
                                                                        
Bezug
Primzahlen: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
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

Bezug
                                                                        
Bezug
Primzahlen: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
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.

Bezug
                                                                                
Bezug
Primzahlen: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
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

Bezug
                                        
Bezug
Primzahlen: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 03:42 Do 01.01.2009
Autor: kuemmelsche

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!



Bezug
                                                
Bezug
Primzahlen: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 17:33 Do 01.01.2009
Autor: kuemmelsche

Hat sich erledigt...
Bezug
                                                
Bezug
Primzahlen: Korrekturmitteilung
Status: (Korrektur) fundamentaler Fehler Status 
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

Bezug
Ansicht: [ geschachtelt ] | ^ Forum "Zahlentheorie"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien


^ Seitenanfang ^
www.vorhilfe.de