Primzahltest (Lucas-Folgen) < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) reagiert/warte auf Reaktion  | | 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.)
|
|
| |
|
| Status: |
(Frage) beantwortet  | | 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
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | 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
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 12:40 Sa 04.06.2011 | | Autor: | booobik |
Vielen DANK!
ich habe jetzt den ganzen Beweis gecheckt:)
Grüße!
|
|
|
|
