quadratische reste < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 11:37 Mi 16.01.2013 | | Autor: | paula_88 |
| Aufgabe | Sei a [mm] \in \IN [/mm] kein Quadrat.
Dann existieren unendlich viele Primzahlen p, sodass [mm] (\bruch{a}{p})=-1. [/mm] |
Hallo an alle,
ich habe für diese Aufgabe eine Musterlösung erhalten. Leider blicke ich das Thema immer noch nicht vollkommen. Deshalb werde ich die Lösung hier posten und alle meine dazugehörigen Fragen. Ich hoffe jemand hat die Zeit die Fragen zu beantworten 
Z.z. ist, dass für unendlich viele Primzahlen p, a quadratischer Nichtrest mod p ist.
BEWEIS
a ist von der Form [mm] a:=2^{s}\*q_{1}\*q_{2}\*...\*q_{n}, [/mm] mit s [mm] \in [/mm] {0,1} und ungeraden, paarweise verschiedenen Primteilern.
a definiert doch somit eine natürliche Zahl, die als Produkt endlich vieler Primzahlen dargestellt wird, oder? [mm] 2^{s} [/mm] für s [mm] \in [/mm] {0,1} definiert doch nur, dass a sowohl gerade als auch ungerade sein kann, oder?
(i) 1. Fall: a=2 und seien [mm] l_{1},...,l_{k} [/mm] die einzigen ungeraden Primzahlen [mm] \not= [/mm] 3, für die [mm] l_{i}=-1.
[/mm]
Wieso genau betrachtet man den Fall für a=2 extra?
[mm] \Rightarrow b:=8\*l_{1}\*...\*l_{k}+3\equiv [/mm] 3 (mod 8), also [mm] \bruch{2}{b}=-1, [/mm] mit 3 teilt nicht b und b teilt nicht [mm] l_{i}.
[/mm]
Wieso die bestimmte Progression gewählt wird verstehe ich, b ist so konstruiert, da der Ergänzungssatz zum QRG besagt, dass a=2 für unendlich viele Primzahlen quadratischer Nichtrest ist, wenn diese kongruent zu 3 mod 8 sind. Aber wieso darf 3 nicht b teilen und b nicht [mm] l_{i}?
[/mm]
[mm] \Rightarrow [/mm] es muss also einen anderen Primfaktor p von b geben, für den 2 quadratischer Nichtrest ist.
(1. Fall a=2 ist somit gezeigt)
Diese Schlussfolgerung verstehe ich nicht und auch nicht, weshalb es für a=2 jetzt schon bewiesen ist. Was für einen anderen Primfaktor p von b soll es geben und welchen hat der Beweis denn betrachtet? Soll das einen Widerspruch darstellen? Bitte erklären, wodurch hier jetzt was gezeigt wurde
(ii) 2. Fall: a sei durch die ungeraden Primzahlen [mm] q_{1},...,q_{n} [/mm] teilbar, n>0. Seien zusätzlich [mm] l_{1},...,l_{k} [/mm] andere Primzahlen, disjunkt zu [mm] q_{j}.
[/mm]
Wieso werden jetzt auf einmal die [mm] q_{i} [/mm] und die [mm] l_{i} [/mm] definiert? Wie kann ich mir diese jeweils vorstellen und warum müssen sie disjunkt zueinander sein? Ich glaube ich habe diese Ausgangssituation des Beweises noch nicht verstanden, also worauf der Beweis hinauslaufen soll, bitte erklären
Dann sind die folgenden Kongruenzen:
x [mm] \equiv [/mm] 1 mod [mm] l_{i}, [/mm] i=1,...,k
x [mm] \equiv [/mm] 1 mod 8
x [mm] \equiv [/mm] 1 mod [mm] q_{j}, [/mm] j=1,...,n-1
x [mm] \equiv [/mm] t mod [mm] q_{n}, [/mm] für ein t [mm] \in \IN [/mm] mit [mm] (\bruch{t}{q_{n}})=-1
[/mm]
Wieso genau wurden diese Kongruenzen jetzt aufgestellt? Ich weiß, dass es mithilfe des chinesischen Restsatzes geschieht, mehr verstehe ich allerdings nicht. Wieso sind sie alle kongruent zu 1, haben also einen quadratischen Rest? Soll ein Widerspruch damit eingeleitet werden? Und wieso kann man von mod [mm] l_{i} [/mm] auf mod 8 schlussfolgern genauso wie auf [mm] q_{j}? [/mm] Und wofür wird das t eingeführt?
Diese Kongruenzen sind simultan lösbar durch ein b [mm] \in \IN [/mm] mit den Eigenschaften b [mm] \equiv [/mm] 1 (mod 8)
Wie kann man diese Lösung, dass b [mm] \equiv [/mm] 1 (mod 8) ermitteln?
[mm] \Rightarrow (\bruch{2}{b})=1 [/mm] und [mm] (\bruch{q_{j}}{b})=(\bruch{b}{q_{j}}) [/mm]
Wozu schlussfolgert man dann dass [mm] (\bruch{2}{b})=1 [/mm] und wie kommt das zustanden? Und wofür benötigt man genau dass [mm] (\bruch{q_{j}}{b})=(\bruch{b}{q_{j}})? [/mm] Dass dies durch das quadratische Reziprozitätsgesetzt gestattet ist weiß ich!
[mm] \Rightarrow (\bruch{a}{b})=(\bruch{2}{b})^{s}\*(\bruch{q_{1}}{b})\*...\*(\bruch{q_{n}}{b})=(\bruch{b}{q_{1}})\*...\*(\bruch{b}{q_{n}})=-1
[/mm]
Somit existiert ein Primfakrot p von b, disjunkt von [mm] l_{i} [/mm] und [mm] q_{j}, [/mm] für den a quadratischer Nichtrest ist.
Die obere Darstellung von [mm] (\bruch{a}{b}) [/mm] verstehe ich noch nicht komplett, dass [mm] (\bruch{a}{b}) [/mm] durch [mm] (\bruch{2}{b})^{s}\*(\bruch{q_{1}}{b})\*...\*(\bruch{q_{n}}{b}) [/mm] dargestellt werden kann ist logisch. Aber wie kommt daraus [mm] (\bruch{b}{q_{1}})\*...\*(\bruch{b}{q_{n}}) [/mm] zustande und woher weiß ich, dass sich daraus ein quadratischer Nichtrest ergibt? Und welcher ist jetzt dieser Primfaktor p von b, für den a quadratischer Nichtrest ist?
So das war's jetzt auch mal. Schon mal vielen Dank an denjenigen, der sich die Zeit zum Antworten nimmt, ich hoffe dass ich den Beweis bald vollkommen verstanden habe
Liebe Grüße, Paula
|
|
| |
|
moin,
> Sei a [mm]\in \IN[/mm] kein Quadrat.
> Dann existieren unendlich viele Primzahlen p, sodass
> [mm](\bruch{a}{p})=-1.[/mm]
> Hallo an alle,
> ich habe für diese Aufgabe eine Musterlösung erhalten.
> Leider blicke ich das Thema immer noch nicht vollkommen.
> Deshalb werde ich die Lösung hier posten und alle meine
> dazugehörigen Fragen. Ich hoffe jemand hat die Zeit die
> Fragen zu beantworten
>
> Z.z. ist, dass für unendlich viele Primzahlen p, a
> quadratischer Nichtrest mod p ist.
>
> BEWEIS
>
> a ist von der Form [mm]a:=2^{s}\*q_{1}\*q_{2}\*...\*q_{n},[/mm] mit
> s [mm]\in[/mm] {0,1} und ungeraden, paarweise verschiedenen
> Primteilern.
>
> a definiert doch somit eine natürliche Zahl, die als
> Produkt endlich vieler Primzahlen dargestellt wird, oder?
> [mm]2^{s}[/mm] für s [mm]\in[/mm] {0,1} definiert doch nur, dass a sowohl
> gerade als auch ungerade sein kann, oder?
Nein, diese Zeile des Beweises sagt, dass du die Aufgabenstellung falsch abgetippt hast.
Gemeint ist (falls diese Zeile stimmt), dass $a$ nicht nur kein Quadrat ist, sondern dass $a$ quadratfrei ist, dass heißt es gibt kein $b [mm] \in \IN$ [/mm] mit [mm] $b^2 \mid [/mm] a$, oder eben: $a$ ist größer 1 und alle Primfaktoren in der Primfaktorzerlegung von $a$ treten nur mit Potenz 1 auf.
> (i) 1. Fall: a=2 und seien [mm]l_{1},...,l_{k}[/mm] die einzigen
> ungeraden Primzahlen [mm]\not=[/mm] 3, für die [mm]l_{i}=-1.[/mm]
>
> Wieso genau betrachtet man den Fall für a=2 extra?
Der Fall $a=2$ wird oft extra betrachtet, weil die 2 als einzige gerade Primzahl eine gewisse Sonderrolle spielt. Viele Beweise für Primzahlen verwenden stark, dass die behandelte Primzahl ungerade ist; weswegen die 2 - so wie auch hier - eben extra "von Hand" abgearbeitet werden muss.
Damit wir mit dem Fall $a=2$ weiter machen können, müsstest du verraten, was genau die [mm] $l_i$ [/mm] hier sein sollen.
Zum Teil $a [mm] \neq [/mm] 2$:
Die ganzen definierten Primzahlen und Kongruenzen helfen beim späteren Beweis
Am Anfang muss man sich nur erstmal davon überzeugen, dass es Primzahlen mit diesen Eigenschaften gibt und dass die Kongruenzen (mit Chinesischem Restsatz) eine gemeinsame Lösung besitzen.
Das $b$ ist kongruent zu $1$ mod $8$, da dies die zweite Gleichung diktiert. Ermitteln kann man so ein $b$ etwa mit dem Chinesischen Restsatz, aber an dieser Stelle des Beweises ist einzig relevant, dass dieses $b$ existiert, nicht wie es aussieht.
Die beiden Folgerungen daraus mit dem quadratische Reziprozitätsgesetz erlauben, die untere Gleichung umzustellen.
> [mm] $(\bruch{a}{b})=(\bruch{2}{b})^{s}*(\bruch{q_{1}}{b})*...*(\bruch{q_{n}}{b})=(\bruch{b}{q_{1}})*...*(\bruch{b}{q_{n}})=-1 [/mm] $
Das [mm] $\left(\frac{2}{b}\right)$ [/mm] kann man weglassen, da darüber fesgestellt wurde, dass es 1 ist. Dass die anderen sich umdrehen lassen, wurde auch direkt in der Zeile darüber gefolgert.
Aus der dritten der vier für $b$ aufgestellten Kongruenzen folgt, dass im hinteren Produkt alle Faktoren bis auf den letzten gleich 1 sind und aus der vierten folgt, dass der letzte gleich -1 ist; somit ist das gesamte Produkt gleich -1.
Du weißt jetzt also, dass $a$ ein quadratischer Nichtrest modulo $b$ ist; was kannst du daraus für die Primfaktoren von $b$ folgern; ist $a$ quadratischer Rest oder Nichtrest?
Da hast du sicher einen schönen Satz zu. ;)
lg
Schadow
|
|
|
| |
|
Vielen Dank für die tolle und ausführliche Antwort, ich habe schon einiges mehr verstanden.
Trotzdem bleiben kleine Fragen
> >Sei a [mm]\in \IN[/mm] kein Quadrat.
> >Dann existieren unendlich viele Primzahlen p, sodass
> >[mm](\bruch{a}{p})=-1[/mm], also a quadratischer Nichtrest mod p ist.
> > BEWEIS
> >
> > a ist von der Form [mm]a:=2^{s}\*q_{1}\*q_{2}\*...\*q_{n},[/mm] > > mit s [mm]\in[/mm] {0,1} und ungeraden, paarweise verschiedenen
> > Primteilern.
Shadowmaster hatte Recht, laut Aufgabenstellung ist a sogar quadratfrei. Was das heißt weiß ich jetzt, aber gibt es einen Grund, dass a nicht nur kein Quadrat ist sondern auch quadratfrei?
> > (i) 1. Fall: a=2 und seien [mm]l_{1},...,l_{k}[/mm] die einzigen
> > ungeraden Primzahlen [mm]\not=[/mm] 3, für die [mm]l_{i}=-1.[/mm]
> Damit wir mit dem Fall [mm]a=2[/mm] weiter machen können, müsstest
> du verraten, was genau die [mm]l_i[/mm] hier sein sollen.
Ich habe jetzt nochmal sowohl die Aufgabenstellung, als auch den 1. Fall des Beweises für a=2 überprüft und ich habe keine Informationen außer Acht gelassen. Das einzige was ich zu den [mm] l_{i} [/mm] sagen kann, ist dass sie ungerade Primzahlen, außer der 3, definieren, dessen quadratischer Rest für a=2 -1, also quadratischer Nichtrest ist.
Somit habe ich für den Anfang des Beweises immernoch die gleichen Fragen wie gestern, ich hoffe, dass mir jemand diese heute noch beantworten kann.
> Zum Teil [mm]a \neq 2[/mm]:
> Die ganzen definierten Primzahlen und
> Kongruenzen helfen beim späteren Beweis
> Am Anfang muss man sich nur erstmal davon überzeugen,
> dass es Primzahlen mit diesen Eigenschaften gibt und dass
> die Kongruenzen (mit Chinesischem Restsatz) eine gemeinsame
> Lösung besitzen.
> Das [mm]b[/mm] ist kongruent zu [mm]1[/mm] mod [mm]8[/mm], da dies die zweite
> Gleichung diktiert. Ermitteln kann man so ein [mm]b[/mm] etwa mit
> dem Chinesischen Restsatz, aber an dieser Stelle des
> Beweises ist einzig relevant, dass dieses [mm]b[/mm] existiert,
> nicht wie es aussieht.
> Die beiden Folgerungen daraus mit dem quadratische
> Reziprozitätsgesetz erlauben, die untere Gleichung
> umzustellen.
>
>
> [mm](\bruch{a}{b})=(\bruch{2}{b})^{s}*(\bruch{q_{1}}{b})*...* (\bruch{q_{n}}{b})=(\bruch{b}{q_{1}})*...*(\bruch{b}{q_{n}})=-1[/mm]
>
> Das [mm]\left(\frac{2}{b}\right)[/mm] kann man weglassen, da
> darüber fesgestellt wurde, dass es 1 ist. Dass die anderen
> sich umdrehen lassen, wurde auch direkt in der Zeile
> darüber gefolgert.
> Aus der dritten der vier für [mm]b[/mm] aufgestellten Kongruenzen
> folgt, dass im hinteren Produkt alle Faktoren bis auf den
> letzten gleich 1 sind und aus der vierten folgt, dass der
> letzte gleich -1 ist; somit ist das gesamte Produkt gleich
> -1.
Toll erklärt, jetzt verstehe ich schonmal, wie [mm](\bruch{a}{b})=(\bruch{2}{b})^{s}*(\bruch{q_{1}}{b})*...*(\bruch{q_{n}}{b})=(\bruch{b}{q_{1}})*...*(\bruch{b}{q_{n}})=-1[/mm] zustande kommt.
Jetzt habe ich nur noch Verständnisprobleme, wie genau die Kongruenzen aufgestellt wurden. So ganz scheine ich den Chinesischen Restsatz noch nicht verstanden zu haben.
Wieso beginne ich mit der Kongruenz
x [mm]\equiv[/mm] 1 mod [mm]l_{i},[/mm] i=1,...,k
und wieso darf ich dann einfach auf
x [mm]\equiv[/mm] 1 mod 8 folgern? Und wieso modulo 8?
[mm] \Rightarrow [/mm] x [mm]\equiv[/mm] 1 mod [mm]q_{j},[/mm] j=1,...,n-1 Wieso wird jetzt noch weitere Primzahlen [mm] q_{j} [/mm] zu [mm] l_{i} [/mm] eingeführt?
Dass alle dieser oberen Kongruenzen 1 ergeben sollen verstehe ich, den Rest nicht so
> Du weißt jetzt also, dass [mm]a[/mm] ein quadratischer Nichtrest
> modulo [mm]b[/mm] ist;
ja, das weiß ich jetzt
> was kannst du daraus für die Primfaktoren
> von [mm]b[/mm] folgern; ist [mm]a[/mm] quadratischer Rest oder Nichtrest?
> Da hast du sicher einen schönen Satz zu. ;)
Leider habe ich keinen im Skript gefunden, wozu ist es denn jetzt wichtig zu wissen, wie die Primfaktoren von b aussehen? :-S Es wurde doch schon gezeigt dass [mm] (\bruch{a}{b})=-1, [/mm] also dass a quadratischer Nichtrest ist.
Soo das reicht jetzt auch wieder, vielen Dank für die geduldigen Antworten.
Viele Grüße, Paula
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 05:20 Fr 18.01.2013 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
