matheraum.de
Raum für Mathematik
Offene Informations- und Nachhilfegemeinschaft

Für Schüler, Studenten, Lehrer, Mathematik-Interessierte.
Hallo Gast!einloggen | registrieren ]
Startseite · Forum · Wissen · Kurse · Mitglieder · Team · Impressum
Forenbaum
^ Forenbaum
Status Schulmathe
  Status Primarstufe
  Status Mathe Klassen 5-7
  Status Mathe Klassen 8-10
  Status Oberstufenmathe
    Status Schul-Analysis
    Status Lin. Algebra/Vektor
    Status Stochastik
    Status Abivorbereitung
  Status Mathe-Wettbewerbe
    Status Bundeswettb. Mathe
    Status Deutsche MO
    Status Internationale MO
    Status MO andere Länder
    Status Känguru
  Status Sonstiges

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
Weitere Fächer:

Open Source FunktionenplotterFunkyPlot: Kostenloser und quelloffener Funktionenplotter für Linux und andere Betriebssysteme
StartseiteMatheForenZahlentheoriePrimzahltest (Lucas-Folgen)
Foren für weitere Schulfächer findest Du auf www.vorhilfe.de z.B. Deutsch • Englisch • Französisch • Latein • Spanisch • Russisch • Griechisch
Forum "Zahlentheorie" - Primzahltest (Lucas-Folgen)
Primzahltest (Lucas-Folgen) < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
Ansicht: [ geschachtelt ] | ^ Forum "Zahlentheorie"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien

Primzahltest (Lucas-Folgen): Frage (reagiert)
Status: (Frage) reagiert/warte auf Reaktion Status 
Datum: 17:38 Sa 28.05.2011
Autor: booobik

Aufgabe
Test: Es sei  N>1 ungerade und [mm] N+1=\produkt_{i=1}^{s}q_i^{f_i } [/mm] . Angenommen, es existiert eine Zahl D mit  (D|N)=-1 derart, dass es für jeden Primfaktor  [mm] [i]q_i [/mm] [/i]  von  N+1 eine Lucas-Folge [mm] (U_n^{(i)})_{n\ge0} [/mm]   mit Diskriminante [mm] D=P_i^2-4Q_i [/mm]  und [mm] ggT(P_i,Q_i)=1 [/mm] oder  [mm] ggT(N,Q_i)=1 [/mm]  gibt, wobei ferner [mm] N|U_{N+1}^{(i) } [/mm] und [mm] N$\hspace{-0.4em}\not\hspace{0.025em}|\$U_{(N+1)/q_i}^{(i)} [/mm] gilt. Dann ist  N eine Primzahl.

Beweis: Nach (V.3) und (V.4),  [mm] N|U_{\Phi_D (N)}^{(i)} [/mm] für jedes i=1,…,s. Es sei [mm] \rho^{(i)} [/mm] (N) die kleinste Zahl r mit [mm] N|U_{r}^{(i)}. [/mm] Nach (IV.29) oder (IV.22) und der Annahme folgt [mm] \rho^{(i)}(N)|(N+1), \rho^{(i)}(N)$\hspace{-0.4em}\not\hspace{0.025em}|\$(N+1)/q_i [/mm]  und [mm] \rho^{(i)} (N)|\Phi_D(N). [/mm] Daher [mm] q_i^{f_i}|\rho^{(i)}(N) [/mm] für jedes i = 1,...,s. Somit [mm] (N+1)|\Phi_D(N) [/mm] und nach (V.2) ist N prim.
wobei
[mm] N=\produkt_{i=1}^{s}p_i^e_i [/mm]
[mm] \Phi_D(N)=1/{2^{s-1}}\produkt_{i=1}^{s}p_i^{e_i-1}(p_i-(\bruch{D}{p_i})) [/mm]
[mm] (\bruch{D}{p_i}) [/mm] ist Jacobi-Symbol
[mm] U_r^{(i)} [/mm] ist die Lucas-Folge mit [mm] U_r^{(i)}=\bruch{x_1^{r^{(i)}}-x_2^{r^{(i)}}}{x_1-x_2} [/mm]
D ist die Diskriminante = [mm] (x_1-x_2)^2 [/mm]
[mm] x_1,x_2 [/mm] sind wurzel von [mm] x^2-Px+Q=0 [/mm]

Hallo erst mal an alle!

Der Test und Beweis sind aus dem Buch "Die Welt der Primzahlen" von Ribenboim, Seite 66

Ich verstehe den Beweis nicht ganz.
Warum [mm] \rho^{(i)}(N)|(N+1), \rho^{(i)}(N)$\hspace{-0.4em}\not\hspace{0.025em}|\$(N+1)/q_i [/mm]  und [mm] \rho^{(i)} (N)|\Phi_D(N) [/mm] gilt, ist mir klar, deswegen sind Formeln, die ich hier nicht geschrieben habe, (V.3,V.4,IV.29...) nicht relevant. Beweise von diesen Formeln sind mir auch klar.

Ich gleube, dass [mm] \rho^{(i)}(N)|(N+1) [/mm] und [mm] \rho^{(i)}(N)$\hspace{-0.4em}\not\hspace{0.025em}|\$(N+1)/q_i [/mm] für den Beweis genügt, dass [mm] q_i^{f_i}|\rho^{(i)}(N) [/mm] gilt.
Vereinfacht a|b*c, a$ [mm] \hspace{-0.4em}\not\hspace{0.025em}|\ [/mm] $b, wobei c-prim [mm] \Rightarrow [/mm] c|a, klingt logisch, ich kanns aber nicht beweisen. Oder liege ich da falsch?

Warum [mm] (N+1)|\Phi_D(N) [/mm] gilt, verstehe ich auch nicht.  (wenn N-prim, dann sind die beiden Seiten gleich, wir wollen aber erst beweisen, dass N prim ist...)

Der letzte Schritt (mit V.2) ist dann wieder verständlich.

Bitte um Tipps zum Beweis

Beste Grüße
P.S: ich hoffe ich habe gegen keine Regel verstoßen, schreibe zum ersten mal im Forum:)

(Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.)

        
Bezug
Primzahltest (Lucas-Folgen): Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 16:36 Do 02.06.2011
Autor: booobik

Guten Tag!
ich verstehe dass der ganze Satz mit Beweis etwas "zu lang" ist, vielleicht kann mir jemand eine kurze Frage zum Beweis beantworten oder einen Tip geben

$ [mm] N=\produkt_{i=1}^{s}q_i^{f_i } [/mm] $ - Primfaktorzerlegung, [mm] q_i [/mm] - prim
a|N und [mm] a$\hspace{-0.4em}\not\hspace{0.025em}|\$\bruch{N}{q_i} \Rightarrow [/mm] $ [mm] q_i^{f_i}|a [/mm] $

Stimmt diese Aussage? wenn ja, wie kann ich siebeweisen

Bezug
                
Bezug
Primzahltest (Lucas-Folgen): Antwort
Status: (Antwort) fertig Status 
Datum: 17:06 Do 02.06.2011
Autor: Lippel

Hallo,

>  ich verstehe dass der ganze Satz mit Beweis etwas "zu
> lang" ist, vielleicht kann mir jemand eine kurze Frage zum
> Beweis beantworten oder einen Tip geben
>  
> [mm]N=\produkt_{i=1}^{s}q_i^{f_i }[/mm] - Primfaktorzerlegung, [mm]q_i[/mm] -
> prim
>  a|N und a[mm]\hspace{-0.4em}\not\hspace{0.025em}|\[/mm][mm] \bruch{N}{q_i} \Rightarrow[/mm]
>  [mm]q_i^{f_i}|a[/mm]
>  
> Stimmt diese Aussage? wenn ja, wie kann ich siebeweisen

Sie stimmt:
Aus [mm] $a\;|\; [/mm] N$ folgt [mm] $a=N=\produkt_{i=1}^{s}q_i^{g_i }$ [/mm] mit [mm] $g_i \leq f_i \;\;\forall [/mm] i$
Angenommen [mm] $q_i^{f_i} \not|\; [/mm] a [mm] \Rightarrow g_i [/mm] < [mm] f_i$ [/mm] (beachte, dass hier nun echt kleiner steht) [mm] $\Rightarrow [/mm] a [mm] \;|\; \frac{N}{q_i}$, [/mm] denn [mm] $q_i$ [/mm] kommt in a in einer echt kleineren Potenz vor als in N. Dies ist ein Widerspruch zur Voraussetzung, also muss [mm] $q_i^{f_i} \;|\; [/mm] a$ gelten.

LG Lippel


Bezug
        
Bezug
Primzahltest (Lucas-Folgen): Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 12:40 Sa 04.06.2011
Autor: booobik

Vielen DANK!

ich habe jetzt den ganzen Beweis gecheckt:)

Grüße!

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


^ Seitenanfang ^
www.schulmatheforum.de
[ Startseite | Forum | Wissen | Kurse | Mitglieder | Team | Impressum ]