Quadratischer Rest 10

bwigosch · Full Member Anmeldungsdatum: 10.10.2009 Beiträge: 71

Hallo!

Ich muss alle Primzahlen ermitteln, für die 10 ein quadratischer Rest ist, d.h. ich soll die Kongruenz:
-- x^2 == 10 mod p -- nach p auflösen.
10 ist quadratischer Rest, d.h. das Legendre-Symbol (10/p) = 1 muss gelten.
Es folgt: (10/p) = (2/p) * (5/p) = 1 nach den Rechenregeln. Also muss gelten, dass entweder (2/p) und (5/p) beide gleich 1 oder beide gleich -1 sein müssen, damit (10/p) = 1 gilt.
Nun stehe ich aber an. Ich weiß nicht, wie ich weitermachen soll bzw. welche Überlegungen ich nun anstellen muss.
Es wäre nett, wenn mir jemand weiterhelfen könnte.

Vielen Dank!

cyrix42 · God of Posting Anmeldungsdatum: 14.08.2006 Beiträge: 21523

Halklo!

Na das klingt doch sehr nach dem quadratischen Reziprozitätsgesetz. Wink

Cyrix
_________________
Die Wurzel
--

bwigosch · Full Member Anmeldungsdatum: 10.10.2009 Beiträge: 71

Ja, das denke ich mir auch, aber ich steh da voll an...
Es gibt ja 2 Fälle: (2/p) und (5/p) sind beide 1 oder beide -1.

Fall 1: (2/p) und (5/p) sind beide 1

Wenn (2/p) = 1 ist, dann muss p kongruent +-1 mod 8 sein (laut Wikipedia), d.h. p = 8k +- 1 mit k aus Z.
Es ist auch (5/p) = 1. Es gilt: (5/p) = (p/5). Jetzt muss ich p mod 5 rechnen. Ergebnis kann sein: 0,1,2,3, oder 4.
Wenn p mod 5 = 0 --> nicht möglich, da p ein Vielfaches von 5 wäre.
Wenn p mod 5 = 1 --> (1/5) = 1 und es passt.
Wenn p mod 5 = 2 --> (2/5) = -1 und es passt nicht.
Wenn p mod 5 = 3 --> (3/5) = -1 und es passt nicht.
Wenn p mod 5 = 4 --> (4/5) = (2/5) * (2/5) = (-1) * (-1) = 1 und es passt.
Also kann p mod 5 nur 1 oder 4 sein.
Und welche Primzahlen sind das jetzt alles???? Wie kann ich aus p = 8k +- 1 und p mod 5 = 1 oder 4 nun auf alle p schließen????

Fall 2: (2/p) und (5/p) sind beide -1
Aus (2/p) = -1 folgt: p kongruent +- 3 mod 8. (laut Wikipedia)
Aus (5/p) = (p/5) = -1 folgt: p mod 5 muss entweder 2 oder 3 sein, da dann gilt: (2/5) = (3/5) = -1.
Aber wie komme ich nun auf konkrete Primzahlen p????

Vielen Dank für die Hilfe schon im Voraus!!

cyrix42 · God of Posting Anmeldungsdatum: 14.08.2006 Beiträge: 21523

zu Fall 1:

Nuja, das sind dann eben alle Primzahlen, die kongruent +-1 oder +-9 modulo 40 sind. Genauer kannst du es nicht angeben.

Auch wirst du ein ähnliches Ergebnis in Fall 2 erhalten.

Cyrix
_________________
Die Wurzel
--

bwigosch · Full Member Anmeldungsdatum: 10.10.2009 Beiträge: 71

Okay, also kann man da keine konkreten Primzahlen p angeben, da es unendlich viele gibt, für die 10 quadratischer Rest ist.
Aber wie kommt man auf +-1 oder +-9 modulo 40???? Das verstehe ich nicht!! Und wie kommt man überhaupt auf 40????

Vielen Dank für die Hilfe!

cyrix42 · God of Posting Anmeldungsdatum: 14.08.2006 Beiträge: 21523

Chinesischer Restsatz

Cyrix
_________________
Die Wurzel
--

bwigosch · Full Member Anmeldungsdatum: 10.10.2009 Beiträge: 71

Okay, bei Fall 1 habe ich jetzt folgendes:

p kongruent +- 1 mod 8 --und-- p kongruent +-1 mod 5.
8 und 5 sind teilferfremd, des wegen kann ich die beiden linearen Kongruenzen zu einer zusammenfassen: p kongruent +-1 mod 40, wobei 40 das kgv(8,5) ist (laut Wikipedia Chinesischer Restsatz). Aber wie soll ich bei Fall 1 auf p kongruent +-9 mod 40 kommen???? Das ist mir ein absolutes Rätsel!!

Vielen Dank für die Hilfe!