Die Mathe-Redaktion - 26.05.2019 09:56 - Registrieren/Login
Auswahl
ListenpunktHome
ListenpunktAktuell und Interessant ai
ListenpunktArtikelübersicht/-suche
ListenpunktAlle Links / Mathe-Links
ListenpunktFach- & Sachbücher
ListenpunktMitglieder / Karte / Top 15
ListenpunktRegistrieren/Login
ListenpunktArbeitsgruppen
ListenpunktSchwätz
ListenpunktWerde Mathe-Millionär!
ListenpunktAnmeldung MPCT Sept.
ListenpunktFormeleditor fedgeo
Schwarzes Brett
Aktion im Forum
Suche
Stichwortsuche in Artikeln und Links von Matheplanet
Suchen im Forum
Suchtipps

Bücher
Englische Bücher
Software
Suchbegriffe:
Mathematik bei amazon
Naturwissenschaft & Technik
In Partnerschaft mit Amazon.de
Kontakt
Mail an Matroid
[Keine Übungsaufgaben!]
Impressum

Bitte beachten Sie unsere Nutzungsbedingungen, die Distanzierung, unsere Datenschutzerklärung und
die Forumregeln.

Sie können Mitglied werden. Mitglieder können den Matheplanet-Newsletter bestellen, der etwa alle 2 Monate erscheint.

Der Newsletter Okt. 2017

Für Mitglieder
Mathematisch für Anfänger
Wer ist Online
Aktuell sind 338 Gäste und 15 Mitglieder online.

Sie können Mitglied werden:
Klick hier.

Über Matheplanet
 
Zum letzten Themenfilter: Themenfilter:
Matroids Matheplanet Forum Index
Moderiert von Wauzi
Zahlentheorie » Primzahltests » Solovay-Strassen-Primzahltest Beweis
Druckversion
Druckversion
Antworten
Antworten
Autor
Universität/Hochschule Solovay-Strassen-Primzahltest Beweis
Kimberly
Wenig Aktiv Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 18.05.2015
Mitteilungen: 74
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Themenstart: 2019-02-22


fed-Code einblenden



  Profil  Quote  Link auf diesen Beitrag Link
Folgende Antworten hat der Fragesteller vermutlich noch nicht gesehen.
Er/sie war noch nicht wieder auf dem Matheplaneten
xiao_shi_tou_
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 12.08.2014
Mitteilungen: 752
Aus: Bonn
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.1, eingetragen 2019-02-23

\(\begingroup\)\(\DeclareMathOperator{\Aut}{Aut} \DeclareMathOperator{\mod}{mod} \DeclareMathOperator{\codim}{codim} \DeclareMathOperator{\log}{log} \DeclareMathOperator{\coker}{coker} \DeclareMathOperator{\Ob}{Ob} \DeclareMathOperator{\Emb}{Emb} \DeclareMathOperator{\Tr}{Tr} \DeclareMathOperator{\scale}{scale} \DeclareMathOperator{\Sper}{Sper} \DeclareMathOperator{\vol}{vol} \DeclareMathOperator{\Cl}{Cl} \DeclareMathOperator{\lcm}{lcm} \DeclareMathOperator{\ord}{ord} \DeclareMathOperator{\End}{End} \DeclareMathOperator{\supp}{supp} \DeclareMathOperator{\rad}{rad} \DeclareMathOperator{\char}{char} \DeclareMathOperator{\Proj}{Proj} \DeclareMathOperator{\length}{length} \DeclareMathOperator{\locArt}{locArt} \DeclareMathOperator{\Ass}{Ass} \DeclareMathOperator{\id}{id} \DeclareMathOperator{\im}{im} \DeclareMathOperator{\Pic}{Pic} \DeclareMathOperator{\Spec}{Spec} \DeclareMathOperator{\Gal}{Gal} \DeclareMathOperator{\Hom}{Hom} \newcommand{\tfae}{\textbf{T.F.A.E.}} \newcommand{\ndownlong}[2]{#1\ -\!\!\!\rightharpoonup\!\leftharpoondown\!\to\! #2} \newcommand{\shso}{\udl{\text{Sheaves on}}} \newcommand{\shs}{\udl{\text{Sheaves}}} \newcommand{\GG}{\c{G}} \newcommand{\ush}[1]{\udl{\text{Sheaf}}(#1)} \newcommand{\sh}{\udl{\text{Sheaf}}} \newcommand{\rr}{/\!\!/} \newcommand{\proof}{\udl{\mathscr{P}\mathscr{r}\mathscr{o}\mathscr{o}\mathscr{f}:}} \newcommand{\defeq}{\overset{\mathscr{D}\mathscr{e}\mathscr{f}.}{=\!=}} \newcommand{\set}[2]{\{#1\mid #2\}} \newcommand{\SS}{\mathscr{S}} \newcommand{\noem}{\not=\emptyset} \newcommand{\DD}{\c{D}} \newcommand{\BB}{\c{B}} \newcommand{\Pr}{\ff{P}} \newcommand{\exact}[3]{0\to #1\to #2\to#3\to 0} \newcommand{\qed}{\ff{Q}.\ff{E}.\ff{D}.} \newcommand{\wt}[1]{\widetilde{#1}} \newcommand{\spr}[1]{\Sper(#1)} \newcommand{\nuplong}[2]{#1\ -\!\!\!\rightharpoondown\!\leftharpoonup\!\to\! #2} \newcommand{\ndownloong}[2]{#1 -\!\!\!-\!\!\!\rightharpoonup\!\leftharpoondown\!\!\!\longrightarrow \!#2} \newcommand{\bop}{\bigoplus} \newcommand{\eps}{\epsilon} \newcommand{\K}{\mathbb{K}} \newcommand{\ip}{\langle -,- \rangle} \newcommand{\ipr}[2]{\langle #1,#2 \rangle} \newcommand{\vth}{\vartheta} \newcommand{\pprod}{\prod_{v\in\ff{M}_\K}} \newcommand{\pfam}[1]{(#1)_{v\in\ff{M}_\K}} \newcommand{\finfam}[1]{(#1)_{i=1}^n} \newcommand{\fam}[1]{(#1)_{i\in I}} \newcommand{\jfam}[1]{(#1)_{j\in J}} \newcommand{\kfam}[1]{(#1)_{k\in K}} \newcommand{\nfam}[1]{(#1)_{n\in \N}} \newcommand{\udl}[1]{\underline{#1}} \newcommand{\Uij}{U_i\cap U_j} \newcommand{\vpi}{\varphi_i} \newcommand{\vpj}{\varphi_j} \newcommand{\psij}{\psi_{i,j}} \newcommand{\CC}{\c{C}} \newcommand{\nsum}{\sum_{n\in\N}} \newcommand{\twist}[1]{\c{O}_{\mathbb{P}_k^n}(#1)} \newcommand{\prj}[1]{\Proj (#1)} \newcommand{\part}[2]{\frac{\partial #1}{\partial #2}} \newcommand{\kxn}{k[x_0,\pts,x_n]} \newcommand{\ka}{\kappa} \newcommand{\pr}{\mathfrak{p}} \newcommand{\abs}[1]{\left| #1\right|} \newcommand{\ab}{\left|-\right|} \newcommand{\eps}{\epsilon} \newcommand{\N}{\mathbb{N}} \newcommand{\KX}{K[X]} \newcommand{\cov}{\c{U}} \newcommand{\ff}[1]{\mathfrak{#1}} \newcommand{\legendre}[2]{\left(\frac{#1}{#2}\right)} \newcommand{\ANF}{K/\Q} \newcommand{\GFF}{F/{\F_p(t)}} \newcommand{\Os}{\mathcal{O}_{S,s}} \newcommand{\lineb}{\c{L}} \newcommand{\cyclm}{\Q(\sqrt[m]{1})} \newcommand{\cyclmK}{K(\sqrt[m]{1})} \newcommand{\LX}{L[X]} \newcommand{\OS}{\mathcal{O}_S} \newcommand{\bb}[1]{\textbf{#1}} \newcommand{\OY}{\mathcal{O}_Y} \newcommand{\glX}{\Gamma(X,\mathcal{O}_X)} \newcommand{\glY}{\Gamma(Y,\mathcal{O}_Y)} \newcommand{\finKX}{f\in K[X]} \newcommand{\ser}[1]{\sm{n=0}{\infty}{#1}} \newcommand{\sm}[3]{\underset{#1}{\overset{#2}{\sum}} #3} \newcommand{\cl}[1]{\overline{#1}} \newcommand{\sube}{\subseteq} \newcommand{\hk}{\hookrightarrow} \newcommand{\OYy}{\mathcal{O}_{Y,y}} \newcommand{\supe}{\supseteq} \newcommand{\resy}{\kappa(y)} \newcommand{\LK}{L/K} \newcommand{\iso}{\overset{\sim}{\to}} \newcommand{\isom}[3]{#1\overset{#2}{\iso}#3} \newcommand{\kn}{k^n} \newcommand{\kvec}{\textbf{vect}(k)} \newcommand{\fkvec}{\textbf{vect}_{<\infty}(k)} \newcommand{\fz}{f(X)=0} \newcommand{\KIsom}{L\underset{K}{\overset{\sim}{\to}} L} \newcommand{\Q}{\mathbb{Q}} \newcommand{\R}{\mathbb{R}} \newcommand{\L}{\mathbb{L}} \newcommand{\C}{\mathbb{C}} \newcommand{\F}{\mathbb{F}} \newcommand{\A}{\mathbb{A}} \newcommand{\P}{\mathbb{P}} \newcommand{\Z}{\mathbb{Z}} \newcommand{\Zp}{\mathbb{Z}_p} \newcommand{\Qp}{\mathbb{Q}_p} \newcommand{\Qq}{\mathbb{Q}_q} \newcommand{\Fp}{\mathbb{F}_p} \newcommand{\I}{[0,1]} \newcommand{\In}{[0,1]^n} \newcommand{\Fpn}{\mathbb{F}_{p^n}} \newcommand{\Fpm}{\mathbb{F}_{p^m}} \newcommand{\Zn}{\mathbb{Z}/{n\mathbb{Z}}} \newcommand{\Zx}[1]{\mathbb{Z}/{#1\mathbb{Z}}} \newcommand{\md}[3]{#1\equiv #2\pmod{#3}} \newcommand{\ga}{\Gal(L/K)} \newcommand{\aga}[1]{\Gal(\overline{#1}/#1)} \newcommand{\sga}[1]{\Gal(#1^{sep}/{#1})} \newcommand{\gal}[2]{\Gal(#1/{#2})} \newcommand{\c}[1]{\mathcal{#1}} \newcommand{\limes}[1]{\underset{i\in I}{\varprojlim{#1_i}}} \newcommand{\Co}[2]{H^p(#1,#2)} \newcommand{\OK}{\mathcal{O}_K} \newcommand{\OL}{\mathcal{O}_L} \newcommand{\res}[1]{\kappa(#1)} \newcommand{\resx}{\kappa(x)} \newcommand{\Te}{[T]} \newcommand{\Tee}{[T_1,T_2]} \newcommand{\Teee}{[T_1,T_2,T_3]} \newcommand{\Ten}{[T_1\cos T_n]} \newcommand{\Tem}{[T_1\cos T_m]} \newcommand{\pts}{\cdots} \newcommand{\pt}{\cdot} \newcommand{\hm}[3]{\Hom_{#1}(#2,#3)} \newcommand{\hom}[2]{\Hom(#1,#2)} \newcommand{\dash}{\dashrightarrow} \newcommand{\schemes}{\bb{(Sch)}} \newcommand{\tx}[1]{\text{ #1 }} \newcommand{\mm}{\ff{m}} \newcommand{\arr}[3]{#1\overset{#2}{\to} #3} \newcommand{\nrm}[1]{\left\|#1\right\|} \newcommand{\nr}{\nrm{-}} \newcommand{\ext}[2]{#1/{#2}} \newcommand{\lam}{\lambda} \newcommand{\a}{\alpha} \newcommand{\be}{\beta} \newcommand{\g}{\gamma} \newcommand{\de}{\delta} \newcommand{\vp}{\varphi} \newcommand{\p}{\phi} \newcommand{\bul}{\bullet} \newcommand{\t}{\tau} \newcommand{\s}{\sigma} \newcommand{\ze}{\zeta} \newcommand{\tm}{\times} \newcommand{\tms}{\times\pts\times} \newcommand{\ot}{\otimes} \newcommand{\ots}{\otimes\pts\otimes} \newcommand{\pls}{+\pts +} \newcommand{\cos}{,\pts,} \newcommand{\op}{\oplus} \newcommand{\ops}{\oplus\pts\oplus} \newcommand{\cr}{\circ} \newcommand{\crs}{\circ\pts\circ} \)
Hallo Kimberly.

Ich kenne mich in der Thematik nicht aus (weird weiß bestimmt mehr dazu :P).

Ich wollte eigentlich nur kurz auf deine Fragen eingehen, aber dann hat der von dir skizzierte Beweis nich nicht mehr losgelassen..

Hier ist meine Ausarbeitung des Beweises:

(Ich habe versucht detailiert zu sein)

Beweis:
Sei \(n\) eine zusammengesetzte natürliche Zahl und \(G(n):=(\Zn)^\times\).
Sei \(U:=\{a\in G(n)\colon \md{a^{\frac{n-1}{2}}}{\leg{a}{n}}{n}\}\).
Angenommen \(U\) ist echte Untergruppe von \(G\), dann haben wir \((G\colon U)\geq 2\), also \(\mid G\mid\geq 2\mid U\mid\), also \(\mid G\mid\pt\frac{1}{2}\geq \mid U\mid\), was wir zeigen wollen. (\(\mid U\mid\) ist die Anzahl der Euler Lügner, und der Satz besagt, dass diese höchstens die Hälfte von \(\mid G\mid\)) ist.

Es genügt also zu zeigen, dass \(U\) echte Untergruppe von \(G\) ist.

Angenommen \(U=G\). Dann gilt \(\md{a^{\frac{n-1}{2}}}{\leg{a}{n}}{n}\) für alle \(a\in G(n)\). Quadrieren ergibt \(\md{a^{n-1}}{1}{n}\) für alle \(a\) welche koprim zu \(n\) sind. Also ist \(n\) eine Carmichael Zahl.

Korselt (1895)
Sei \(n>0\) eine zusammengesetzte Zahl. Dann ist \(n\) eine Carmichael Zahl genau dann wenn \(n\) quadrat-frei ist und \(p-1\mid n-1\) für jeden Primfaktoren gilt.

Nehmen wir mal an das ist wahr.

Das bedeutet, dass \(n=p_1\pts p_m; m\geq 2\).
(Ich verstehe nicht wie du hier auf \(m>2\) kommst. Übersehe ich etwas? Das braucht man aber auch nicht.)

Behauptung \(0\)
Es gibt \(a\in G(n)\) mit \(\leg{a}{p_1}=-1\) und \(\leg{a}{p_j}=1\forall p_j\neq p_1\).

Sehen wir erstmal ein wie aus der Behauptung der Rest des Beweises folgt:


Behauptung 1
\(\md{a^{\frac{n-1}{2}}}{-1}{n}\) gilt nicht.

Beweis hierzu
Aus dem Euler-Kriterium folgt:
\(\md{a^{\frac{p_j-1}{2}}}{1}{p_j},\forall p_j\neq p_1\).

(\(\md{a^{\frac{p_1-1}{2}}}{-1}{p_1}\) brauchst du für den Beweis nicht.)

Hierraus folgt wegen \(p_j-1\mid n-1\) \(\md{a^{\frac{n-1}{2}}}{1}{p_j}\)

Angenommen es gelte \(\md{a^{\frac{n-1}{2}}}{-1}{n}\). Da  \(p_j\mid n\) folgte \(\md{a^{\frac{n-1}{2}}}{-1}{p_j}\), Widerpsruch!

Behauptung 2
\(\leg{a}{n}=-1\)

Beweis hierzu
Es folgt aus der Multiplikativität des Jacobi-Symbols:

\(\leg{a}{n}=\leg{a}{p_1}\leg{a}{p_2}\pts\leg{a}{p_m}=(-1)\pt 1\pts 1=-1\).

Widerspruch
Behauptung \(1\) \(+\) Behauptung \(2 =\) Widerpsruch!


Jetzt noch der Beweis der Behauptung \(0\):
Aus dem Chinesische Restsatz folgt, dass es einen Ring isomorphismus
\(\Zn\cong \Zx{p_1}\times\pts\times\Zx{p_m}\) gibt, welcher uns zu einem Gruppenisomorphismus \((\Zn)^\times\cong (\Zx{p_1})^\times\times\pts\times(\Zx{p_m})^\times\) führt.
Nun wissen wir, dass es in jeder Gruppe quadratische Reste und nicht-quadratische Reste gibt.
Sei \(a_1\in \Zx{p_1}\) ein nicht-quadratischer Rest und seien \(a_j\in\Zx{p_j}\) quadratische Reste. Dann entpricht \((a_1,a_2,\pts,a_m)\) unter dem obigen Isomorphismus einem Element \(a\in (\Zn)^\times\)
mit den gewünschten Eigenschaften.

 




-----------------
"Jedes Gehirn kann Fragen beantworten. Es geht darum die richtigen Fragen zu finden."
\(\endgroup\)


  Profil  Quote  Link auf diesen Beitrag Link
weird
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 16.10.2009
Mitteilungen: 4709
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.2, eingetragen 2019-02-23


Was ich an der ganzen Sache nicht verstehe ist, dass man hier Carmichaelzahlen (und damit zusammenhängend deren Charakterisierung mithilfe des durchaus nichttrivialen Satzes von Korselt) überhaupt braucht. Mir kommt es nämlich so vor, als würde hier nur die Quadratfreiheit von Carmichaelzahlen gebraucht. Das kann man aber viel "billiger" haben.

Ist nämlich $n=p^2k$ mit $p\in\mathbb P$ und $k\in \mathbb{N}^*$, so hat man ja dann in $a:=1+kp$ sofort einen Zeugen für den Solovay-Strassen-Test. Einerseits gilt nämlich

$a^{\frac{n-1}2}=(1+kp)^{\frac{n-1}2}\equiv 1+\frac{n-1}2 kp\not \equiv 1 \mod n$

andererseits aber

$\left(\frac an\right)=\left(\frac{1+kp}{kp^2}\right)=\left(\frac{1+kp}p\right)^2\left(\frac{1+kp}k\right)=1\cdot 1=1$

Ist aber $n$ ungerade, zusammengesetzt und quadratfrei, dann braucht man Carmichaelzahlen überhaupt nicht mehr. Ist nämlich $p$ ein Primteiler von $n$ und $g$ eine Primitivwurzel mod $p$, so ist dann wegen ggT$(n,\frac np)=1$ das Kongruenzensystem

$x\equiv g \mod p,\quad x\equiv 1 \mod \frac np$

nach dem Chinesischen Restsatz lösbar. Ist $a$ eine Lösung davon, so gilt einerseits

$a^{\frac{n-1}2}\equiv 1 \not \equiv -1 \mod \frac np$

andererseits jedoch

$\left(\frac an\right)=\left(\frac a{p\,\cdot\frac np}\right)=\left(\frac gp\right)\left(\frac 1{\frac np}\right)=(-1)\cdot 1=-1$

Das ist für mich die "Essenz" des ganzen Beweises hier, so wie ich ihn jetzt machen würde.  wink



  Profil  Quote  Link auf diesen Beitrag Link
xiao_shi_tou_
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 12.08.2014
Mitteilungen: 752
Aus: Bonn
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.3, eingetragen 2019-02-23

\(\begingroup\)\(\DeclareMathOperator{\Aut}{Aut} \DeclareMathOperator{\mod}{mod} \DeclareMathOperator{\codim}{codim} \DeclareMathOperator{\log}{log} \DeclareMathOperator{\coker}{coker} \DeclareMathOperator{\Ob}{Ob} \DeclareMathOperator{\Emb}{Emb} \DeclareMathOperator{\Tr}{Tr} \DeclareMathOperator{\scale}{scale} \DeclareMathOperator{\Sper}{Sper} \DeclareMathOperator{\vol}{vol} \DeclareMathOperator{\Cl}{Cl} \DeclareMathOperator{\lcm}{lcm} \DeclareMathOperator{\ord}{ord} \DeclareMathOperator{\End}{End} \DeclareMathOperator{\supp}{supp} \DeclareMathOperator{\rad}{rad} \DeclareMathOperator{\char}{char} \DeclareMathOperator{\Proj}{Proj} \DeclareMathOperator{\length}{length} \DeclareMathOperator{\locArt}{locArt} \DeclareMathOperator{\Ass}{Ass} \DeclareMathOperator{\id}{id} \DeclareMathOperator{\im}{im} \DeclareMathOperator{\Pic}{Pic} \DeclareMathOperator{\Spec}{Spec} \DeclareMathOperator{\Gal}{Gal} \DeclareMathOperator{\Hom}{Hom} \newcommand{\tfae}{\textbf{T.F.A.E.}} \newcommand{\ndownlong}[2]{#1\ -\!\!\!\rightharpoonup\!\leftharpoondown\!\to\! #2} \newcommand{\shso}{\udl{\text{Sheaves on}}} \newcommand{\shs}{\udl{\text{Sheaves}}} \newcommand{\GG}{\c{G}} \newcommand{\ush}[1]{\udl{\text{Sheaf}}(#1)} \newcommand{\sh}{\udl{\text{Sheaf}}} \newcommand{\rr}{/\!\!/} \newcommand{\proof}{\udl{\mathscr{P}\mathscr{r}\mathscr{o}\mathscr{o}\mathscr{f}:}} \newcommand{\defeq}{\overset{\mathscr{D}\mathscr{e}\mathscr{f}.}{=\!=}} \newcommand{\set}[2]{\{#1\mid #2\}} \newcommand{\SS}{\mathscr{S}} \newcommand{\noem}{\not=\emptyset} \newcommand{\DD}{\c{D}} \newcommand{\BB}{\c{B}} \newcommand{\Pr}{\ff{P}} \newcommand{\exact}[3]{0\to #1\to #2\to#3\to 0} \newcommand{\qed}{\ff{Q}.\ff{E}.\ff{D}.} \newcommand{\wt}[1]{\widetilde{#1}} \newcommand{\spr}[1]{\Sper(#1)} \newcommand{\nuplong}[2]{#1\ -\!\!\!\rightharpoondown\!\leftharpoonup\!\to\! #2} \newcommand{\ndownloong}[2]{#1 -\!\!\!-\!\!\!\rightharpoonup\!\leftharpoondown\!\!\!\longrightarrow \!#2} \newcommand{\bop}{\bigoplus} \newcommand{\eps}{\epsilon} \newcommand{\K}{\mathbb{K}} \newcommand{\ip}{\langle -,- \rangle} \newcommand{\ipr}[2]{\langle #1,#2 \rangle} \newcommand{\vth}{\vartheta} \newcommand{\pprod}{\prod_{v\in\ff{M}_\K}} \newcommand{\pfam}[1]{(#1)_{v\in\ff{M}_\K}} \newcommand{\finfam}[1]{(#1)_{i=1}^n} \newcommand{\fam}[1]{(#1)_{i\in I}} \newcommand{\jfam}[1]{(#1)_{j\in J}} \newcommand{\kfam}[1]{(#1)_{k\in K}} \newcommand{\nfam}[1]{(#1)_{n\in \N}} \newcommand{\udl}[1]{\underline{#1}} \newcommand{\Uij}{U_i\cap U_j} \newcommand{\vpi}{\varphi_i} \newcommand{\vpj}{\varphi_j} \newcommand{\psij}{\psi_{i,j}} \newcommand{\CC}{\c{C}} \newcommand{\nsum}{\sum_{n\in\N}} \newcommand{\twist}[1]{\c{O}_{\mathbb{P}_k^n}(#1)} \newcommand{\prj}[1]{\Proj (#1)} \newcommand{\part}[2]{\frac{\partial #1}{\partial #2}} \newcommand{\kxn}{k[x_0,\pts,x_n]} \newcommand{\ka}{\kappa} \newcommand{\pr}{\mathfrak{p}} \newcommand{\abs}[1]{\left| #1\right|} \newcommand{\ab}{\left|-\right|} \newcommand{\eps}{\epsilon} \newcommand{\N}{\mathbb{N}} \newcommand{\KX}{K[X]} \newcommand{\cov}{\c{U}} \newcommand{\ff}[1]{\mathfrak{#1}} \newcommand{\legendre}[2]{\left(\frac{#1}{#2}\right)} \newcommand{\ANF}{K/\Q} \newcommand{\GFF}{F/{\F_p(t)}} \newcommand{\Os}{\mathcal{O}_{S,s}} \newcommand{\lineb}{\c{L}} \newcommand{\cyclm}{\Q(\sqrt[m]{1})} \newcommand{\cyclmK}{K(\sqrt[m]{1})} \newcommand{\LX}{L[X]} \newcommand{\OS}{\mathcal{O}_S} \newcommand{\bb}[1]{\textbf{#1}} \newcommand{\OY}{\mathcal{O}_Y} \newcommand{\glX}{\Gamma(X,\mathcal{O}_X)} \newcommand{\glY}{\Gamma(Y,\mathcal{O}_Y)} \newcommand{\finKX}{f\in K[X]} \newcommand{\ser}[1]{\sm{n=0}{\infty}{#1}} \newcommand{\sm}[3]{\underset{#1}{\overset{#2}{\sum}} #3} \newcommand{\cl}[1]{\overline{#1}} \newcommand{\sube}{\subseteq} \newcommand{\hk}{\hookrightarrow} \newcommand{\OYy}{\mathcal{O}_{Y,y}} \newcommand{\supe}{\supseteq} \newcommand{\resy}{\kappa(y)} \newcommand{\LK}{L/K} \newcommand{\iso}{\overset{\sim}{\to}} \newcommand{\isom}[3]{#1\overset{#2}{\iso}#3} \newcommand{\kn}{k^n} \newcommand{\kvec}{\textbf{vect}(k)} \newcommand{\fkvec}{\textbf{vect}_{<\infty}(k)} \newcommand{\fz}{f(X)=0} \newcommand{\KIsom}{L\underset{K}{\overset{\sim}{\to}} L} \newcommand{\Q}{\mathbb{Q}} \newcommand{\R}{\mathbb{R}} \newcommand{\L}{\mathbb{L}} \newcommand{\C}{\mathbb{C}} \newcommand{\F}{\mathbb{F}} \newcommand{\A}{\mathbb{A}} \newcommand{\P}{\mathbb{P}} \newcommand{\Z}{\mathbb{Z}} \newcommand{\Zp}{\mathbb{Z}_p} \newcommand{\Qp}{\mathbb{Q}_p} \newcommand{\Qq}{\mathbb{Q}_q} \newcommand{\Fp}{\mathbb{F}_p} \newcommand{\I}{[0,1]} \newcommand{\In}{[0,1]^n} \newcommand{\Fpn}{\mathbb{F}_{p^n}} \newcommand{\Fpm}{\mathbb{F}_{p^m}} \newcommand{\Zn}{\mathbb{Z}/{n\mathbb{Z}}} \newcommand{\Zx}[1]{\mathbb{Z}/{#1\mathbb{Z}}} \newcommand{\md}[3]{#1\equiv #2\pmod{#3}} \newcommand{\ga}{\Gal(L/K)} \newcommand{\aga}[1]{\Gal(\overline{#1}/#1)} \newcommand{\sga}[1]{\Gal(#1^{sep}/{#1})} \newcommand{\gal}[2]{\Gal(#1/{#2})} \newcommand{\c}[1]{\mathcal{#1}} \newcommand{\limes}[1]{\underset{i\in I}{\varprojlim{#1_i}}} \newcommand{\Co}[2]{H^p(#1,#2)} \newcommand{\OK}{\mathcal{O}_K} \newcommand{\OL}{\mathcal{O}_L} \newcommand{\res}[1]{\kappa(#1)} \newcommand{\resx}{\kappa(x)} \newcommand{\Te}{[T]} \newcommand{\Tee}{[T_1,T_2]} \newcommand{\Teee}{[T_1,T_2,T_3]} \newcommand{\Ten}{[T_1\cos T_n]} \newcommand{\Tem}{[T_1\cos T_m]} \newcommand{\pts}{\cdots} \newcommand{\pt}{\cdot} \newcommand{\hm}[3]{\Hom_{#1}(#2,#3)} \newcommand{\hom}[2]{\Hom(#1,#2)} \newcommand{\dash}{\dashrightarrow} \newcommand{\schemes}{\bb{(Sch)}} \newcommand{\tx}[1]{\text{ #1 }} \newcommand{\mm}{\ff{m}} \newcommand{\arr}[3]{#1\overset{#2}{\to} #3} \newcommand{\nrm}[1]{\left\|#1\right\|} \newcommand{\nr}{\nrm{-}} \newcommand{\ext}[2]{#1/{#2}} \newcommand{\lam}{\lambda} \newcommand{\a}{\alpha} \newcommand{\be}{\beta} \newcommand{\g}{\gamma} \newcommand{\de}{\delta} \newcommand{\vp}{\varphi} \newcommand{\p}{\phi} \newcommand{\bul}{\bullet} \newcommand{\t}{\tau} \newcommand{\s}{\sigma} \newcommand{\ze}{\zeta} \newcommand{\tm}{\times} \newcommand{\tms}{\times\pts\times} \newcommand{\ot}{\otimes} \newcommand{\ots}{\otimes\pts\otimes} \newcommand{\pls}{+\pts +} \newcommand{\cos}{,\pts,} \newcommand{\op}{\oplus} \newcommand{\ops}{\oplus\pts\oplus} \newcommand{\cr}{\circ} \newcommand{\crs}{\circ\pts\circ} \)
2019-02-23 10:38 - weird in Beitrag No. 2 schreibt:
Was ich an der ganzen Sache nicht verstehe ist, dass man hier Carmichaelzahlen (und damit zusammenhängend deren Charakterisierung mithilfe des durchaus nichttrivialen Satzes von Korselt) überhaupt braucht. Mir kommt es nämlich so vor, als würde hier nur die Quadratfreiheit von Carmichaelzahlen gebraucht. Das kann man aber viel "billiger" haben.

Ist nämlich $n=p^2k$ mit $p\in\mathbb P$ und $k\in \mathbb{N}^*$, so hat man ja dann in $a:=1+kp$ sofort einen Zeugen für den Solovay-Strassen-Test. Einerseits gilt nämlich

$a^{\frac{n-1}2}=(1+kp)^{\frac{n-1}2}\equiv 1+\frac{n-1}2 kp\not \equiv 1 \mod n$

andererseits aber

$\left(\frac an\right)=\left(\frac{1+kp}{kp^2}\right)=\left(\frac{1+kp}p\right)^2\left(\frac{1+kp}k\right)=1$

Ist aber $n$ ungerade, zusammengesetzt und quadratfrei, dann braucht man Carmichaelzahlen überhaupt nicht mehr. Ist nämlich $p$ ein Primteiler von $n$ und $g$ eine Primitivwurzel mod $p$, so ist dann wegen ggT$(n,\frac np)=$ das Kongruenzensystem

$x\equiv g \mod p,\quad x\equiv 1 \mod \frac np$

lösbar. Ist $a$ eine Lösung davon, so gilt einerseits

$a^{\frac{n-1}2}\equiv 1 \not \equiv -1 \mod \frac np$

andererseits jedoch

$\left(\frac an\right)=\left(\frac a{p\,\cdot\frac np}\right)=\left(\frac gp\right)\left(\frac 1{\frac np}\right)=(-1)\cdot 1=-1$

Das ist für mich die "Essenz" des ganzen Beweises hier, so wie ich ihn jetzt machen würde.  wink

Es ist immer schön jemanden zu haben der sich wirklich auskennt ;P.
Ich fand es komisch, dass der Satz von Korselt gar nicht erwähnt wird, sondern implizit verwendet wird.
\(\endgroup\)


  Profil  Quote  Link auf diesen Beitrag Link
weird
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 16.10.2009
Mitteilungen: 4709
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.4, eingetragen 2019-02-23

\(\begingroup\)\( \newcommand{\N}{\mathbb{N}} \newcommand{\units}[1]{(\Zx{#1})^\times} \newcommand{\KX}{K[X]} \newcommand{\leg}[2]{\left(\frac{#1}{#2}\right)} \newcommand{\ANF}{K/\Q} \newcommand{\lineb}{\c{L}} \newcommand{\cyclm}{\Q(\sqrt[m]{1})} \newcommand{\cyclmK}{K(\sqrt[m]{1})} \newcommand{\clKX}{\overline{K}[X]} \newcommand{\LX}{L[X]} \newcommand{\gfib}[2]{#1_{\cl{#2}}} \newcommand{\OS}{\mathcal{O}_S} \newcommand{\bb}[1]{\textbf{#1}} \newcommand{\OY}{\mathcal{O}_Y} \newcommand{\glX}{\Gamma(X,\mathcal{O}_X)} \newcommand{\glY}{\Gamma(Y,\mathcal{O}_Y)} \newcommand{\finKX}{f\in K[X]} \newcommand{\ser}[1]{\sm{n=0}{\infty}{#1}} \newcommand{\sm}[3]{\underset{#1}{\overset{#2}{\sum}} #3} \newcommand{\cl}[1]{\overline{#1}} \newcommand{\sube}{\subseteq} \newcommand{\prou}{\text{ primitive }m \text{-th root of unity }} \newcommand{\hk}{\hookrightarrow} \newcommand{\OYy}{\mathcal{O}_{Y,y}} \newcommand{\supe}{\supseteq} \newcommand{\resy}{\kappa(y)} \newcommand{\LK}{L/K} \newcommand{\iso}{\overset{\sim}{\to}} \newcommand{\kn}{k^n} \newcommand{\kvec}{\textbf{vect}(k)} \newcommand{\fkvec}{\textbf{vect}_{<\infty}(k)} \newcommand{\fz}{f(X)=0} \newcommand{\KIsom}{L\underset{K}{\overset{\sim}{\to}} L} \newcommand{\simple}{\text{Let }K'=K(\alpha)\text{ be a simple extension of  }K \text{ with minimal polynomial }\finKX} \newcommand{\Q}{\mathbb{Q}} \renewcommand{\S}{\mathbb{S}} \newcommand{\R}{\mathbb{R}} \newcommand{\C}{\mathbb{C}} \newcommand{\F}{\mathbb{F}} \newcommand{\A}{\mathbb{A}} \newcommand{\P}{\mathbb{P}} \newcommand{\Z}{\mathbb{Z}} \newcommand{\Zp}{\mathbb{Z}_p} \newcommand{\Qp}{\mathbb{Q}_p} \newcommand{\Qq}{\mathbb{Q}_q} \newcommand{\Fp}{\mathbb{F}_p} \newcommand{\I}{[0,1]} \newcommand{\In}{[0,1]^n} \newcommand{\Fpn}{\mathbb{F}_{p^n}} \newcommand{\Fpm}{\mathbb{F}_{p^m}} \newcommand{\Zn}{\mathbb{Z}/{n\mathbb{Z}}} \newcommand{\Zx}[1]{\mathbb{Z}/{#1\mathbb{Z}}} \newcommand{\md}[3]{#1\equiv #2\pmod{#3}} \newcommand{\ga}{Gal(L/K)} \newcommand{\aga}[1][k]{Gal(\overline{#1}/#1)} \newcommand{\gal}[2]{Gal(#1/{#2})} \newcommand{\c}[1]{\mathcal{#1}} \newcommand{\lim}[1]{\underset{i\in I}{\varprojlim{#1_i}}} \newcommand{\prp}{\text{ proper }} \newcommand{\lnss}{\text{ locally noetherian Schemes}} \newcommand{\lns}{\text{ locally noetherian Scheme }} \newcommand{\ffe}{\text{ finite field extension }} \newcommand{\fge}{\text{ finite Galois extension }} \newcommand{\fne}{\text{ finite normal extension }} \newcommand{\fse}{\text{ finite separable extension }} \newcommand{\fure}{\text{ finite unramified extension }} \newcommand{\frae}{\text{ finite ramified extension }} \newcommand{\ure}{\text{ unramified extension }} \newcommand{\rae}{\text{ ramified extension }} \newcommand{\tarae}{\text{ tamely ramified extension }} \newcommand{\rain}{\text{ ramification index }} \newcommand{\indeg}{\text{ inertia index }} \newcommand{\SS}[2]{E_2^{p,q}=#1\Longrightarrow #2} \newcommand{\Co}[2]{H^p(#1,#2)} \newcommand{\qcqs}{\text{ quasi-compact quasi-separated }} \newcommand{\oft}{\text{ of finite type }} \newcommand{\loft}{\text{ locally of finite type }} \newcommand{\ofp}{\text{ of finite presentation }} \newcommand{\SqcOX}{\text{ Let }\mathcal{M}\text{ be a quasi-coherent} \mathcal{O}_X-\text{module}} \newcommand{\OX}{\mathcal{O}_X} \newcommand{\OC}{\mathcal{O}_C} \newcommand{\Ox}{\mathcal{O}_{X,x}} \newcommand{\OCx}{\mathcal{O}_{C,x}} \newcommand{\OYx}{\mathcal{O}_{Y,y}} \newcommand{\OK}{\mathcal{O}_K} \newcommand{\OL}{\mathcal{O}_L} \newcommand{\res}[1]{\kappa_#1} \newcommand{\resx}{\kappa(x)} \newcommand{\pln}{\text{Let } X\overset{f}{\to} Y \text{ be a proper morphism between locally noetherian schemes. }  } \newcommand{\mor}[5]{\text{ Let } #1\overset{#2}{\to} #3 \text{ be a }#4 \text{morphism of }#5} \newcommand{\let}[3]{\text{ Let } #1 \text{ be a } #2 \text{ of } #3} \newcommand{\sk}{\{\tau\}} \newcommand{\Te}{[T]} \newcommand{\Tee}{[T_1,T_2]} \newcommand{\Teee}{[T_1,T_2,T_3]} \newcommand{\Ten}{[T_1,\cdots,T_n]} \newcommand{\Tem}{[T_1,\cdots,T_m]} \newcommand{\pts}{\cdots} \newcommand{\pt}{\cdot} \newcommand{\hm}[3]{Hom_{#1}(#2,#3)} \newcommand{\hom}[2]{Hom(#1,#2)} \newcommand{\Is}{\overset{\sim}{\to}} \newcommand{\oIs}[1]{\overset{#1}{\overset{\sim}{\to}}} \newcommand{\tx}[1]{\text{ #1 }} \newcommand{\sp}[1]{Spec(#1)} \newcommand{\prj}[1]{Proj(#1)} \newcommand{\wlog}{\text{ without losing generality }} \newcommand{\ffoc}{\text{ \text{Let } f\colon C\to S \text{ be a flat family of curves of genus } g}} \newcommand{\arr}[3]{#1\overset{#2}{\to} #3} \newcommand{\isom}[3]{#1\overset{#2}{\overset{\sim}{\to}}#3} \newcommand{\nrm}[1]{\left\|#1\right\|} \newcommand{\letgal}{\text{ Let } \ga \text{ be a finite Galois-Extension of degree }[L\colon K]} \newcommand{\ext}[2]{#1/{#2}} \newcommand{\a}{\alpha} \newcommand{\be}{\beta} \newcommand{\g}{\gamma} \newcommand{\de}{\delta} \newcommand{\vp}{\varphi} \newcommand{\p}{\phi} \newcommand{\bul}{\bullet} \newcommand{\t}{\tau} \newcommand{\s}{\sigma} \newcommand{\ze}{\zeta} \newcommand{\lmb}{\lambda} \newcommand{\tm}{\times} \newcommand{\tms}{\times\pts\times} \newcommand{\ot}{\otimes} \newcommand{\ots}{\otimes\pts\otimes} \newcommand{\pls}{+\pts +} \newcommand{\kms}{,\pts,} \newcommand{\op}{\oplus} \newcommand{\ops}{\oplus\pts\oplus} \newcommand{\cr}{\circ} \newcommand{\crs}{\circ\pts\circ}\)
2019-02-23 11:14 - xiao_shi_tou_ in Beitrag No. 3 schreibt:
Ich fand es komisch, dass der Satz von Korselt gar nicht erwähnt wird, sondern implizit verwendet wird.

Ja, ich bin wie gesagt sogar der Meinung, dass man Carmichaelzahlen und diesen Satz hier auch gar nicht wirklich braucht. Darüberhinaus war derjenige, von dem der Beweis im Startposting stammt, auch sichtlich bemüht, nur ja alle Bedingungen aus dem Satz von Korselt auch wirklich zu verwenden. Statt z.B. für sein $a$ im letzten Absatz gleich zu verlangen, dass

$\left(\frac a{p_1}\right)=-1,\quad a\equiv 1 \mod p_j$ für $j=2,...,m$

gilt, also gewissermaßen "den Stier bei den Hörnern zu packen", wählt er die weit schwächere Bedingung

$\left(\frac a{p_1}\right)=-1,\quad \left(\frac a{p_j}\right)=1$ für $j=2,...,m$

womit er sich dann in der Folge auch noch ohne Not mit der Bedingung $p-1\mid n-1$ für Primteiler $p$ von $n$ aus dem Satz von Korselt "herumschlagen" muss und, wenn ich das richtig verstanden habe, war genau dieser Beweisteil auch dem TS hier noch unklar.  eek
\(\endgroup\)


  Profil  Quote  Link auf diesen Beitrag Link
Kimberly wird per Mail über neue Antworten informiert.
Neues Thema [Neues Thema] Antworten [Antworten]    Druckversion [Druckversion]

 


Wechsel in ein anderes Forum:
 Suchen    
 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2019 by Matroids Matheplanet
This web site was made with PHP-Nuke, a web portal system written in PHP. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die Nutzungsbedingungen, die Distanzierung, die Datenschutzerklärung und das Impressum.
[Seitenanfang]