Beweis: Legendre-Symbol kann nur Werte -1 und 1 annehmen (a=0 mod p sei ausgeschlossen)

12.01.2013, 18:07	Very	Auf diesen Beitrag antworten »
Beweis: Legendre-Symbol kann nur Werte -1 und 1 annehmen (a=0 mod p sei ausgeschlossen) Hallo, ich möchte gerne zeigen, dass das Legendre-Symbol nur die Werte -1 und 1 annehmen kann. Ich glaube ich habe dazu einen Beweis gefunden, verstehe aber die Grundfunktionsweise des Beweises noch nicht (zeigt dieser überhaupt, was ich zeigen will?) und außerdem ist mir eine Stelle unklar. zum Beweis: sei also $\begin{eqnarray} a \not\equiv 0 (mod p) \end{eqnarray}$ (Damit schließen wir gleich den Fall aus, dass a ein Vielfaches von p ist. Denn nur in diesem Fall nimmt das Legendre-Symbol nach Definition den Wert 0 an und a ist weder ein Rest noch ein Nichtrest von p.) mit dem kleinen Satz von Fermat folgt: $\begin{eqnarray} \forall a \not\equiv 0 : a^{p-1}-1 \equiv 0 (mod p) \end{eqnarray}$ . Da p ungerade ist, ist p-1 gerade (hier ist mein erstes Problem:Warum darf ich p=2 ausschließen, das ist ja die einzige ungerade Primzahl. Ist das Legendre-Symbol für p=2 nicht definiert?) kann ich p-1=2q setzen. Es folgt mit der 3. Binomischen Formel: $\begin{eqnarray} a^{2q}-1 = (a^q-1)(a^qq) \end{eqnarray}$ und daher muss gelten, dass $\begin{eqnarray} \forall a \not\equiv 0: a^q\equiv 1 \text{ v } a^q \equiv -1 (mod p) \end{eqnarray*}$ . Meine zweite Frage bezieht sich ganz allgemein auf den Beweis: Warum zeigt das, dass das Legendre-Symbol nur die Werte -1 und 1 annehmen kann? Klar, am Ende steht, dass nur -1 und 1 rauskommen können, aber wir haben am Anfang doch nicht das Legendre-Symbol verwendet... Würde mich über Hilfe freuen. lg Very
12.01.2013, 18:21	watcher	Auf diesen Beitrag antworten »
Blöde Frage zum Anfang: Was ist denn deine Def. des Legendresymbols? Meine wäre die folgende: $\begin{eqnarray} \left(\frac{a}{p}\right) = \begin{cases} \;\;\,1 \text{ falls } a \text{ a quadratischer Rest modulo}\ p \text{ and } a \not\equiv 0\pmod{p} \\ -1 \text{ falls } a \text{ quadratischer nicht-Rest modulo}\ p\\ \;\;\,0 \text{ if } a \equiv 0 \pmod{p}. \end{cases} \end{eqnarray}$
12.01.2013, 18:36	Very	Auf diesen Beitrag antworten »
Meine (im Skript) ist die folgende: Sei p eine Primzahl und $\begin{eqnarray} a \in \frac{\mathbb{Z}}{p\mathbb{Z}} \end{eqnarray}$ . Wir definieren das Legendre-Symbol von a nach p durch $\begin{eqnarray} (\frac{a}{p}):=\begin{cases}<br /> 1, & \text{wenn }a\text{ ist quadratischer Rest mod p,}\\<br /> -1, & \text{wenn }a\text{ ist quadratischer Nichtrest mod p.}<br /> \end{cases} \end{eqnarray}$ Jetzt weiß ich aber auch noch, dass es die Möglichkeit gibt, dass das Legendre-symbol gleich 0 wird, nämlich wenn a ein Vielfaches von p ist. Deshalb habe ich das einfach mal ausgeschlossen..
12.01.2013, 18:49	watcher	Auf diesen Beitrag antworten »
Da du die selbe Definition wie ich verwendest ist er Beweis des Threadtitels komplett trivial: Es steht so explizit in der Defintion.
12.01.2013, 18:55	Very	Auf diesen Beitrag antworten »
hmm... stimmt, er steht ja direkt in der Definition... Also wäre der Titel auf jeden Fall schonmal geklärt. Siehst du zufällig noch, was in den Zeilen meines ersten Beitrags (von denen ich dachte dass es der Beweis wäre und mich wohl getäuscht habe) bewiesen wird? - das steht nämlich im Skript direkt unter der Definition und ich sehe den Zusammenhang zum Legendre-Symbol immer noch nicht... das wird darin ja gar nicht verwendet, soweit ich das richtig erkenne..
12.01.2013, 19:00	watcher	Auf diesen Beitrag antworten »
Es gibt eine alternative Definition: $\begin{eqnarray} \left(\frac{a}{p}\right) \equiv a^{(p-1)/2}\ \mod p \end{eqnarray}$ Der Beweis zeigt, dass die rechte Seite nur 1 oder -1 sein kann. Der Fall p=2 kann zu Fuß erledigt werden
Anzeige

12.01.2013, 19:14	Very	Auf diesen Beitrag antworten »
Das ist eine Definition? Ich dachte das wäre das Eulerkriterium... Aber wahrscheinlich zählt das auch als gleichwertige Definition wenn wir zeigen können (was der Beweis ja tut), dass das Eulerkriterium genau dasselbe macht wie die Definition.. hmm, ich sehe den Zusammenhang immer noch nicht: ich betrachte ja in dem Beweis nur $\begin{eqnarray} a^{p-1} \end{eqnarray}$ . Für das Eulerkriterium (oder die Definition, wenn du sagst es ist eine) bräuchte ich $\begin{eqnarray} a^{\frac{p-1}{2}} \end{eqnarray}$ . Also fehlt da jeweils noch die Wurzel davon... Irgendwie bin ich jetzt gerade ziemlich verwirrt.. Noch zum Spezialfall: für p=2 gilt ja dann $\begin{eqnarray} a^{\frac{p-1}{2}}\equiv a^{\frac{1}{2}} (mod 2) \end{eqnarray}$ Und da müsste dann ja auch 1 oder 1- rauskommen für alle ganzen Zahlen a. Da wir in modulo 2 sind, gibt es nur die Möglichkeiten a=0 oder a=1. Für a=1 folgt auch $\begin{eqnarray} a^{\frac{1}{2}}=1 \end{eqnarray}$ für a=0 folgt $\begin{eqnarray} a^{\frac{1}{2}}=0 \end{eqnarray}$ aber dieser Fall wird ja ausgeschlossen weil $\begin{eqnarray} 0 \equiv 2 (mod 2) \end{eqnarray}$ , richtig?
12.01.2013, 19:23	watcher	Auf diesen Beitrag antworten »
Sorry hab bei p=2 nicht richtig aufgepasst: Die alternative Definition geht nur für ungerade Primzahlen, da $\begin{eqnarray} a^{\frac{1}{2}} \end{eqnarray}$ kein sonderlich sinnvoller Ausdruck ist. (es geibt keine Eindeutigkeit der Wurzel mod p) Und ansonsten: Schau Dir mal ganz scharf das q im Beweis an.

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »