starke Pseudoprimzahlen < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) reagiert/warte auf Reaktion  | | Datum: | 12:20 Sa 04.08.2012 | | Autor: | Frisco |
| Aufgabe | [mm] sppz(a)\subseteq [/mm] eppz(a)
wobei sppz(a) die starken Pseudoprimzahlen zur Basis a sind und eppz(a) die Zahlen die Euler-Jacobi Pseudoprimzahlen sind. |
Ich versuche gerade in der Vorlesungsfreien Zeit mich ein bisschen mit der Materie der starken Pseudoprimzahlen zu beschäftigen.
Dabei versuche ich gerade die Aufgabe von oben zu beweisen.
Es sei n [mm] \in [/mm] sppz(a). dann ist n zusammengesetzt und können [mm] N-1=2^s\cdot [/mm] d mit d ungerade schreiben. Zudem gilt [mm] a^d \equiv_n [/mm] 1 oder [mm] a^{2^i\cdot d}\equiv_n [/mm] -1für ein [mm] i\in{0,...,s-1}
[/mm]
z.z. [mm] a^{\frac{n-1}{2}}=(\frac{a}{n}) [/mm] <--- Bedingung für eppz(a)
darf ich nun wiefolgt argumentieren??
1.) Fall [mm] a^d \equiv_n [/mm] 1 :
[mm] (\frac{a}{n})\stackrel{\text{Satz von Euler}}{=}a^{\frac{n-1}{2}}=a^{\frac{2^s\cdot d}{2}}=a^{2^{s-1}\cdot d}=(a^d)^{2^{s-1}}\equiv_n [/mm] 1
und bin damit hoffentlich mit dem ersten Teil fertig?!
oder muss ich noch seperat zeigen, dass dann [mm] (\frac{a}{n})=1 [/mm] ist??
Wenn ja wie kann ich das machen und warum muss ich das überhaupt noch machen?
Danke! 
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 12:46 Sa 04.08.2012 | | Autor: | hippias |
[...]
> z.z. [mm]a^{\frac{n-1}{2}}=(\frac{a}{n})[/mm] <--- Bedingung für
> eppz(a)
> darf ich nun wiefolgt argumentieren??
> 1.) Fall [mm]a^d \equiv_n[/mm] 1 :
> [mm] $(\frac{a}{n})\stackrel{\text{Satz von Euler}}{=}a^{\frac{n-1}{2}}= [/mm] [...]$
Wenn Dein Satz Euler so funktioniert wie Du ihn benutzt, dann hast Du doch hier schon gezeigt,was Du wolltest. Jedoch kann Dir hier nicht folgen: Gilt dieser Satz von Euler nicht nur fuer Primzahlen? Oder hat diese Beziehung etwas damit zu tun, dass $n$ eine starke Pseudoprimzahl ist?
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 15:19 Sa 04.08.2012 | | Autor: | felixf |
Moin!
> [...]
> > z.z. [mm]a^{\frac{n-1}{2}}=(\frac{a}{n})[/mm] <--- Bedingung
> für
> > eppz(a)
>
> > darf ich nun wiefolgt argumentieren??
> > 1.) Fall [mm]a^d \equiv_n[/mm] 1 :
> > [mm](\frac{a}{n})\stackrel{\text{Satz von Euler}}{=}a^{\frac{n-1}{2}}= [...][/mm]
>
> Wenn Dein Satz Euler so funktioniert wie Du ihn benutzt,
> dann hast Du doch hier schon gezeigt,was Du wolltest.
> Jedoch kann Dir hier nicht folgen: Gilt dieser Satz von
> Euler nicht nur fuer Primzahlen?
Ja, das ist so.
> Oder hat diese Beziehung
> etwas damit zu tun, dass [mm]n[/mm] eine starke Pseudoprimzahl ist?
Er will zeigen: $n$ starke Pseudoprimzahl bzgl. $a$ [mm] $\Rightarrow$ [/mm] Satz von Euler gilt fuer $(a, n)$ (mit dem Jacobi-Symbol).
Fuer den Beweis darf er den Satz von Euler natuerlich nicht verwenden...
LG Felix
|
|
|
| |
|
| Status: |
(Frage) beantwortet  | | Datum: | 20:31 Sa 04.08.2012 | | Autor: | Frisco |
Okay hab ich eingesehen und ihr habt natürlich recht!!
nur warum ist (a,n) in diesem fall =1???
bzw warum ist dieses a quadratisches rest mod n??
Ich sehe das einfach noch nicht!
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 21:34 Sa 04.08.2012 | | Autor: | felixf |
Moin!
> Okay hab ich eingesehen und ihr habt natürlich recht!!
> nur warum ist (a,n) in diesem fall =1???
Was bezeichnest du mit $(a, n)$? Das Jacobi-Symbol? Oder den ggT? Ich habe damit einfach das geordnete Paar, bestehend aus $a$ und $n$, gemeint. Mehr nicht.
> bzw warum ist dieses a quadratisches rest mod n??
Ein Hinweis: nur weil das Jacobisymbol $(a/n) = 1$ ist, heisst das noch lange nicht, das $a$ ein quadratischer Rest modulo $n$ ist. Diese Implikation gilt i.A. nur, wenn $n$ eine Primzahl ist (+ ein paar weitere Spezialfaelle).
> Ich sehe das einfach noch nicht!
Du meinst, warum aus $n$ starke Pseudoprimzahl bzgl. $a$ folgt, dass $(a/n) [mm] \equiv a^{(n-1)/2} \pmod{n}$ [/mm] ist?
Sei dazu $n = [mm] \prod_{i=1}^k p_i^{e_i}$. [/mm] Nach dem chinesischen Restsatz gilt [mm] $(\IZ/n\IZ)^\ast \cong \prod_{i=1}^k (\IZ/p_i^{e_i}\IZ)^\ast$. [/mm] Sei [mm] $(a_1, \dots, a_k)$ [/mm] das Element aus dem Produkt, welches $a [mm] \in (\IZ/n\IZ)^\ast$ [/mm] entspricht.
Um die Aussage zu beweisen, arbeitest du am besten mit der Produktdarstellung. Im Fall [mm] $a^d \equiv [/mm] 1 [mm] \pmod{n}$ [/mm] zeigst du [mm] $(a_i/p_i) [/mm] = 1$ fuer alle $i$, woraus $(a/n) = 1$ folgt.
Im Fall [mm] $a^{2^k d} \equiv [/mm] 1 [mm] \pmod{n}$ [/mm] fuer minimales $k > 0$. Du kannst jetzt zeigen, dass [mm] $2^k$ [/mm] ein Teiler von [mm] $p_i [/mm] - 1$ ist, und [mm] $p_i [/mm] = [mm] 2^k b_i [/mm] + 1$ fuer ein passendes [mm] $b_i \in \IN$ [/mm] schreiben. Du kannst jetzt [mm] $(a_i/p_i) \equiv (-1)^{b_i} \pmod{p_i}$ [/mm] zeigen. Damit kannst du schliesslich [mm] $a^{(n-1)/2} \equiv \prod_{i=1}^k (a_i/p_i)^{e_i} [/mm] = (a/n) [mm] \pmod{n}$ [/mm] bekommen.
LG Felix
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 21:44 Sa 04.08.2012 | | Autor: | Frisco |
Ich habe jetzt eine Ausarbeitung gefunden, die im grunde ähnlich wie ich argumentiert bzw. argumentieren will, nur verstehe ich da leider den schritt mit dem jacobi-symbol nicht....
www.zeh-marschke.de/Pseudoprimzahlen.pdf
Seite 6 ziemlich in der Mitte (1.Fall)
Vielleicht kann mir das jemand erklären?!
Danke!
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 10:58 So 05.08.2012 | | Autor: | hippias |
Waere nett gewesen, wenn Du die fragliche Gleichung hier aufgefuehrt haettest. Wie auch immer:
$1= [mm] (\frac{1}{n})$ [/mm] folgt aus der Definition des Jac. Symb.. Weiter gilt [mm] $(\frac{a}{n})= (\frac{b}{n})$, [/mm] falls [mm] $a\equiv_{n} [/mm] b$; daher die zweite Gleichung wegen [mm] $a^{d}\equiv_{n} [/mm] 1$. Der Rest ergibt sich aus der Multiplikativitaet des Symbols.
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 11:53 So 05.08.2012 | | Autor: | Frisco |
Okay es tut mir leid, dass ich die Frage nicht klar formuliert habe... aber wie ihr sehen könnt war es auch schon ziemlich spät in der Nacht O
Was ich wissen will ist, warum macht er/sie das überhaupt so, also warum wählt er/sie [mm] a^d [/mm] anstatt z.B. nur a?? (die Rechenregeln des Jacobi-Symbol waren bzw. sind klar gewesen)
Und wie folgert er/sie daraus, dass aus [mm] (\pm 1)^d [/mm] mit d ungerade das jacobi-symbol 1 sein soll... (bei mir ist [mm] (\pm 1)^d [/mm] =-1 für d ungerade...)
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 15:08 So 05.08.2012 | | Autor: | felixf |
Moin!
> Was ich wissen will ist, warum macht er/sie das überhaupt
> so, also warum wählt er/sie [mm]a^d[/mm] anstatt z.B. nur a?? (die
> Rechenregeln des Jacobi-Symbol waren bzw. sind klar
> gewesen)
Er will $(a/n)$ berechnen. Da $d$ ungerade ist, ist [mm] $(a/n)^d [/mm] = (a/n)$. Mit den Rechenregeln gilt also $(a/n) = [mm] (a/n)^d [/mm] = [mm] (a^d/n) [/mm] = (1/n) = 1$.
> Und wie folgert er/sie daraus, dass aus [mm](\pm 1)^d[/mm] mit d
> ungerade das jacobi-symbol 1 sein soll... (bei mir ist [mm](\pm 1)^d[/mm]
> =-1 für d ungerade...)
Wieso sollte [mm] $(+1)^d [/mm] = 1$ sein?! Fuer $x [mm] \in \{ -1, +1 \}$ [/mm] gilt [mm] $x^d [/mm] = x$ fuer alle ungeraden $d$. Damit ist [mm] $(\pm 1)^d [/mm] = [mm] \pm [/mm] 1$, wobei [mm] $\pm$ [/mm] auf beiden Seiten jeweils das gleiche Vorzeichen ist.
LG Felix
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 17:41 So 05.08.2012 | | Autor: | Frisco |
Mir fallen die Schuppen von den Augen!! ![[bonk]](/images/smileys/bonk.gif "[bonk]")
Ich danke dir!
|
|
|
|
