Legendre-Symbol

13.08.2017, 16:36

helplessandclueless

Legendre-Symbol

Meine Frage:
Zeigen Sie, dass eine Primzahl $\begin{eqnarray*} p \end{eqnarray*}$ genau dann in der Form $\begin{eqnarray*} p=x2 +3y^2 \end{eqnarray*}$ mit $\begin{eqnarray*} x,y \in \mathbb Z \end{eqnarray*}$ darstellbar ist,wenn $\begin{eqnarray*} p=3 \end{eqnarray*}$ oder $\begin{eqnarray*} p \equiv 1 (mod 3) \end{eqnarray*}$ .

Hinweis:Betrachten Sie für $\begin{eqnarray*} p \equiv 1 (mod 3) \end{eqnarray*}$ das Legendre-Symbol $\begin{eqnarray*} (\frac{-3}{p}) \end{eqnarray*}$

Meine Ideen:
Hallo, ich hab die musterlösung zu dieser aufgabe aus der Übung,jedoch verstehe ich sie nicht so ganz

Die Lsg.:

Für $\begin{eqnarray*} p=3 \end{eqnarray*}$ gilt $\begin{eqnarray*} 3=0^2+3*1^2 \end{eqnarray*}$ // wieso reicht das schon für $\begin{eqnarray*} p=3? \end{eqnarray*}$ //
wäre $\begin{eqnarray*} p \equiv 1 (mod 3) \end{eqnarray*}$ in der Form $\begin{eqnarray*} x^2+3y^2 \end{eqnarray*}$ darstellbar,so folgt mit dem Legnrende-Symbol $\begin{eqnarray*} -1 = (\frac{p}{3})=(\frac{x^2+3y^2}{3})=(\frac{x^2}{3}) = 1 \end{eqnarray*}$ // wieso wird aus $\begin{eqnarray*} (\frac{x^2+3y^2}{3})=(\frac{x^2}{3}) \end{eqnarray*}$ //

Dies ist ein Widerspruch und damit kann $\begin{eqnarray*} p \equiv -1 (mod 3) \end{eqnarray*}$ nicht in dieser Form geschrieben werden.

// ab hier versteh ich leider nichts mehr..:/ //

Sei also $\begin{eqnarray*} p \equiv 1 (mod 3) \end{eqnarray*}$ . Man erhält $\begin{eqnarray*} p \equiv 1 (mod 12) \end{eqnarray*}$ oder $\begin{eqnarray*} p \equiv 7 (mod 12) \end{eqnarray*}$ . Man erhält $\begin{eqnarray*} (\frac{-3}{p})=1 \end{eqnarray*}$
Nun wählt man ein $\begin{eqnarray*} r\in \mathbb Z \end{eqnarray*}$ mit $\begin{eqnarray*} r^2\equiv -3 (mod p) \end{eqnarray*}$ und $\begin{eqnarray*} a\in \mathbb N \end{eqnarray*}$ minimal mit $\begin{eqnarray*} a<p$ \end{eqnarray*}$ und $\begin{eqnarray*} p<a^2 \end{eqnarray*}$ .Wir wenden das lemma von Thue an und erhalten $\begin{eqnarray*} x,y \end{eqnarray*}$ mit $\begin{eqnarray*} rx\equiv y(mod p) \end{eqnarray*}$ oder $\begin{eqnarray*} rx\equiv-y (mod p) \end{eqnarray*}$ und $\begin{eqnarray*} 0<x,y<a \end{eqnarray*}$ .Es folgt $\begin{eqnarray*} y^3+3x^2\equiv 0 (mod p) \end{eqnarray*}$ mit $\begin{eqnarray*} x^2,y^2\le(a-1)^2<p \end{eqnarray*}$ wegen der Minimalität von $\begin{eqnarray*} a \end{eqnarray*}$ .

Damit erhalten wir ein $\begin{eqnarray*} s\in \mathbb N \end{eqnarray*}$ mit $\begin{eqnarray*} ps=y^2+3x^2\le(a-1)^2+3(a-1)^2<4p \end{eqnarray*}$

$\begin{eqnarray*} \Rightarrow s\in\{1,2,3 \} \end{eqnarray*}$

Sei $\begin{eqnarray*} s=3 \end{eqnarray*}$ , dann ist $\begin{eqnarray*} 3 \end{eqnarray*}$ ein Teiler von $\begin{eqnarray*} y \end{eqnarray*}$ und man erhält $\begin{eqnarray*} x^2=3(\frac{y}{3})^2=p \end{eqnarray*}$ .

Sei $\begin{eqnarray*} s=2. \end{eqnarray*}$ Dann sind $\begin{eqnarray*} x,y \end{eqnarray*}$ beide ungerade,wenn man modulo $\begin{eqnarray*} 2 \end{eqnarray*}$ rechnet.
$\begin{eqnarray*} (2p=y^2+3x^2 \Rightarrow y^2+3x^2 \equiv 0(mod 2) \end{eqnarray*}$ aber danach ungerade)

Wegen $\begin{eqnarray*} y^2+3x^2 \equiv y^2-x^2\equiv 0 (mod 4) \end{eqnarray*}$ Das steht aber im Widerspruch zu $\begin{eqnarray*} 2p \equiv 2 (mod 4). \end{eqnarray*}$
Also verbleibt $\begin{eqnarray*} S=1. \end{eqnarray*}$

ich wäre sehr dankbar für denk anstöße oder hilfe in irgendeiner weise..:/

13.08.2017, 16:59

HAL 9000

Auf diesen Beitrag antworten »

Mit $\begin{align*} p=x2+3y^2 \end{align*}$ meinst du sicher $\begin{align*} p=x^2+3y^2 \end{align*}$ , oder? verwirrt

Zitat:

Original von helplessandclueless
Für $\begin{eqnarray*} p=3 \end{eqnarray*}$ gilt $\begin{eqnarray*} 3=0^2+3*1^2 \end{eqnarray*}$ // wieso reicht das schon für $\begin{eqnarray*} p=3? \end{eqnarray*}$ //

Na es wird eine Darstellung von $\begin{align*} 3=x^2+3y^2 \end{align*}$ konkret angegeben, nämlich x=0,y=1 , was willst du mehr?

Zitat:

Original von helplessandclueless
// wieso wird aus $\begin{eqnarray*} (\frac{x^2+3y^2}{3})=(\frac{x^2}{3}) \end{eqnarray*}$ //

Vielleicht beschäftigst du dich mal ein wenig mit der inhaltlichen Bedeutung des Legendre-Symbols und daraus folgenden einfachen Eigenschaften. Eine davon ist

$\begin{align*} p_1\equiv p_2\bmod q \quad\Rightarrow\quad \left(\frac{p_1}{q}\right) = \left(\frac{p_2}{q}\right) \end{align*}$ ,

und genau die greift hier.

13.08.2017, 19:14

helplessandclueless1

Auf diesen Beitrag antworten »

Hi habs nachgeschaut und verstanden ,also die def. Von legrende symbol,wieso ist bzw. Wieso erhaelt man jetzt aus $\begin{eqnarray*} p \equiv 1 mod 3 \end{eqnarray*}$ , $\begin{eqnarray*} p \equiv 1 mod 12 \end{eqnarray*}$ oder $\begin{eqnarray*} p \equiv 7 mod 12 \end{eqnarray*}$

13.08.2017, 19:50

HAL 9000

Auf diesen Beitrag antworten »

$\begin{align*} p\equiv 1\bmod 3 \end{align*}$ bedeutet auf Modul 12 "aufgeblasen" die vier Möglichkeiten $\begin{align*} p\equiv 1,4,7,10\bmod 12 \end{align*}$ . Nun ist $\begin{align*} p \end{align*}$ aber auch noch Primzahl, damit scheiden $\begin{align*} p\equiv 4,10\bmod 12 \end{align*}$ aus (teilbar durch 2).

13.08.2017, 20:05

helplessandclueless1

Auf diesen Beitrag antworten »

danke fuer deine antwort. Wieso bedeutet es auf 4 möglichkeiten? Wie kommt man auf diese 4 moeglichkeiten. Ich kann ja $\begin{eqnarray*} p \equiv 1 mod 3 \end{eqnarray*}$ auf $\begin{eqnarray*} mod 12 \end{eqnarray*}$ erweitern ,aber die 1 ist ja im legendre symbol so definiert ,dass a quadratischer rest mod p sein muss ,damit aus (a/p)=1. Jedoch ist 10 und 7 kein quadratischer rest.

13.08.2017, 22:31

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von helplessandclueless1
Hi smile

danke fuer deine antwort. Wieso bedeutet es auf 4 möglichkeiten? Wie kommt man auf diese 4 moeglichkeiten.

Vielleicht bearbeitest du erstmal Aufgaben drei Stufen leichter, wenn du so banale Sachen nachfragen musst. unglücklich

$\begin{align*} p\equiv 1\bmod 3 \end{align*}$ bedeutet $\begin{align*} p=3k+1 \end{align*}$ für irgendeine ganze Zahl $\begin{align*} k \end{align*}$ . Nun ist modulo 4 betrachtet entweder $\begin{align*} k=4m \end{align*}$ , $\begin{align*} k=4m+1 \end{align*}$ , $\begin{align*} k=4m+2 \end{align*}$ oder $\begin{align*} k=4m+3 \end{align*}$ , was eingesetzt dann $\begin{align*} p=12m+1 \end{align*}$ , $\begin{align*} p=12m+4 \end{align*}$ , $\begin{align*} p=12m+7 \end{align*}$ oder $\begin{align*} p=12m+10 \end{align*}$ bedeutet - und $\begin{align*} p=12m+4 \end{align*}$ sowie $\begin{align*} p=12m+10 \end{align*}$ sind keine Primzahlen.

14.08.2017, 01:12

helplessandclueless1

Auf diesen Beitrag antworten »

fuck Hal.. ich stehe einfach völlig auf dem Schlauch sorry Big Laugh

"Dann erhält man $\begin{eqnarray*} (\frac{-3}{p})=1 \end{eqnarray*}$ "

ich hab überhaupt keine idee,wie ich dort vorgehen soll?

14.08.2017, 09:16

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von helplessandclueless1
"Dann erhält man $\begin{eqnarray*} (\frac{-3}{p})=1 \end{eqnarray*}$ "

ich hab überhaupt keine idee,wie ich dort vorgehen soll?

Das ist auch nichttrivial, hier wurden vermutlich das Quadratische Reziprozitätsgesetz plus 1.Ergänzungssatz angewandt: Es ist

$\begin{align*} \left( \frac{-3}{p} \right) = \left( \frac{-1}{p} \right)\cdot \left( \frac{3}{p} \right)\qquad (*) \end{align*}$ .

Nach 1.Ergänzungssatz gilt $\begin{align*} \left( \frac{-1}{p} \right) = (-1)^{\frac{p-1}{2}} \end{align*}$ . Und das eigentliche Reziprozitätsgesetz liefert für Primzahlen $\begin{align*} p>3 \end{align*}$ dann

$\begin{align*} \left( \frac{3}{p} \right) = \left( \frac{p}{3} \right)\cdot (-1)^{\frac{3-1}{2}\cdot \frac{p-1}{2}} \end{align*}$ .

Das ergibt in (*) eingesetzt dann $\begin{align*} \left( \frac{-3}{p} \right) = \left( \frac{p}{3} \right)\cdot (-1)^{p-1} = \left( \frac{p}{3} \right) = 1 \end{align*}$ ,

letzteres, weil wir ja hier nur über $\begin{align*} p\equiv 1\bmod 3 \end{align*}$ reden.

14.08.2017, 10:43

helplessandclueless1

Auf diesen Beitrag antworten »

Danke hal

wieso benutzt man jetzt das lemma von thue?:/

14.08.2017, 11:18

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von helplessandclueless1
wieso benutzt man jetzt das lemma von thue?:/

Zunächst: Mir war dieses Lemma bisher unbekannt. Aber dass die Anwendung den Beweis voranbringt, geht doch aus den Ausführungen hervor. Man muss sich eben auch mal reinhängen und versuchen die Schritte zu verstehen, statt bei der ersten Erwähnung des Lemmas sofort "wieso?" zu schreien. unglücklich

Nur grundsätzlich: Aus $\begin{align*} \left( \frac{-3}{p} \right)=1 \end{align*}$ geht hervor, dass die Modulgleichung $\begin{align*} x^2+3y^2\equiv 0\bmod p \end{align*}$ Lösungen besitzt, d.h., es gibt ganze Zahlen $\begin{align*} s \end{align*}$ mit $\begin{align*} x^2+3y^2=sp \end{align*}$ . Wir wollen aber mehr, nämlich dass das auch sogar für $\begin{align*} s=1 \end{align*}$ klappt. Und für solche "möglichst kleine" $\begin{align*} s \end{align*}$ ist eben das Lemma von Thue hilfreich.

Ich muss an der Stelle mal bemängeln, dass du sehr viele Schreibfehler in deiner Beweiswiedergabe oben eingebaut hast, die leider z.T. das Verständnis des geschriebenen erschweren - eine Auswahl:

Zitat:

Original von helplessandclueless
wäre $\begin{eqnarray*} p \equiv 1 (mod 3) \end{eqnarray*}$ in der Form $\begin{eqnarray*} x^2+3y^2 \end{eqnarray*}$ darstellbar,so folgt mit dem Legnrende-Symbol [..]

Hier ging es aber um $\begin{eqnarray*} p \equiv~ {\color{red}-}1 \bmod 3 \end{eqnarray*}$ .

Zitat:

Original von helplessandclueless
Es folgt $\begin{eqnarray*} y^3+3x^2\equiv 0 (mod p) \end{eqnarray*}$ mit $\begin{eqnarray*} x^2,y^2\le(a-1)^2<p \end{eqnarray*}$ wegen der Minimalität von $\begin{eqnarray*} a \end{eqnarray*}$ .

Sicher meinst du hier $\begin{eqnarray*} y^{{\color{red}2}}+3x^2\equiv 0 \bmod p \end{eqnarray*}$ . Und auch da muss man leicht die Stirn runzeln, da oben ja eher noch von $\begin{align*} x^2+3y^2 \end{align*}$ die Rede war. Diese Vertauschung der Symbole ist jetzt keine Katastrophe - aber muss das sein, solche zusätzlichen Stolpersteine in einen ohnehin nicht ganz einfachen Beweis einzubauen? verwirrt

Neue Frage »

Antworten »

Legendre-Symbol

Verwandte Themen