quadratischer Rest

bwigosch · Junior Member Anmeldungsdatum: 10.10.2009 Beiträge: 82

Hallo!

Ich muss folgendes beweisen:
Sei p eine Primzahl und c quadratischer Rest mod p. Zu Zeigen ist, dass es zwei verschiedene p-adische Zahlen gibt, deren Quadrate gleich c sind.

Meine Idee bisher:
x^2 = c (mod p) ("=" entspricht dem kongruent-Zeichen).

c ist quadratischer Rest, d.h. das Legendre-Symbol (c "über" p) = 1.

Jetzt muss ich irgendwie das x herausfinden, wobei x aus der Menge der p-adischen Zahlen ist und x^2 = c sein muss. Aber dazu fehlen mir die Ideen, wie ich das angehen könnte.

Hat jemand einen Tipp für mich?

Vielen Dank!

cyrix42 · Verfasst am: 08 Jul 2012 - 20:51:13 Titel:

Hallo!

Versuche rekursiv aus einer Lösung modulo p^k eine moduo p^(k+1) zu konstruieren. (Die zweite Lösung ist dann einfach die negative.)

Hensels Lemma lässt grüßen. Wink

Cyrix
_________________
Die Wurzel
--

bwigosch · Junior Member Anmeldungsdatum: 10.10.2009 Beiträge: 82

Hallo!

Vielen Dank für den Hinweis! Nur leider kann ich nicht viel damit anfangen. Wieso muss ich aus einer Lösung modulo p^k eine Lösung modulo p^(k+1) bestimmen, wenn ja die Kongruenz modulo p ist?? Und wie kann ich das Hensel-Lemma ins Spiel bringen??

Vielen Dank für die Hilfe schon im Voraus!

cyrix42 · Verfasst am: 10 Jul 2012 - 11:55:54 Titel:

Hallo!

Man kann sich p-adische Zahlen vorstellen als Zahlen im System zur Basis p mit "unendlich vielen Vorkomma-Stellen". Denn eine p-adische Zahl x ist der projektive Limes einer Folge (x_n) ganzer Zahlen, wobei gilt, dass x_{k+1} == x_k (mod p^k) für alle k >= 1 ist.

Anschaulich betrachtet: Das x_k gibt die letzten k Stellen der p-adischen Zahl an und die Bedingung sichert nur, dass diese dann auch in allen späteren Folgengliedern die gleichen sind.

Was heißt dies für unser Vorgehen? Nun, wir nehmen an, wir kennen die letzten k Stellen (also das x_k) und müssen uns daraus eine Lösung für die k+1-ste Stelle basteln. Damit erhalten wir induktiv dann die gesamte p-adische Zahl.

In deinem konkreten Fall willst du eine p-adische Zahl x finden, sodass x^2 = c ist. Es genügt also eine Folge (x_n) zu finden, die x_k ^2 == c (mod p_k) erfüllt (und obige Kongruenzbedingung zwischen den x_k).

Die Aussage, dass c quadratischer Rest modulo p ist, liefert dir die Existenz eines x_1 mit x_1^2 == c (mod p). Dies ist unser "Induktionsanfang".

Nun zum "Induktionsschritt": Sei also x_k eine ganze Zahl mit x_k^2 == c (mod p^k). Betrachte nun die Zahlen (x_k + l * p^k), wobei l die ganzen Zahlen von 0 bis p-1 durchläuft. (Das l ist also nun die nächste Stelle von unserem x, die wir aus den k vorhergehenden bestimmen wollen.)

Können wir nun so ein l finden, sodass (x_k + l * p^k)^2 == c (mod p^(k+1)) ist, sind wir fertig. Mach mal! Smile

@Hensels Lemma: Das ist eine verallgemeinerte Aussage von dem, was du hier beweisen sollst: Du suchst die Nullstelle des Polynoms f(x)=x^2 - c. Die Aussage Hensels ist, dass dies allgemein nach oben beschriebenen Verfahren geht, wenn die Nullstelle nur einfach ist; d.h. die Lösbarkeit modulo p ist äquivalent zur Lösbarkeit in den p-adischen Zahlen.

Cyrix
_________________
Die Wurzel
--