Quadratische Reste bei Primzahlmoduln

22.05.2015, 15:17

pansox

Quadratische Reste bei Primzahlmoduln

Hallo zusammen,

ich versuche gerade einen Beweis zu machen, wobei ich unter anderem auf die folgende Komponente gestoßen bin.

Wikipedia sagt zum Thema "Quadratische Reste bei Primzahlmoduln" bezüglich der quadratischen Reste:

Legendre $\begin{eqnarray*} \begin{pmatrix}\frac{a}{p}\end{pmatrix} = x^{\frac{(p-1)}{2} } mod\ p \equiv 1 \end{eqnarray*}$

Gut. Weiter steht dort:

Daraus lässt sich herleiten, dass es bei einem Primzahlmodul genau $\begin{eqnarray*} \frac{p-1}{2} \end{eqnarray*}$ quadratische Reste und ebensoviele quadratische Nichtreste gibt.

Und da komme ich nicht hin.

Kann ich das irgendwie über die Ordnung herleiten? Dass die Lösungsmenge alle x enthält, die die Ordnung $\begin{eqnarray*} \frac{p-1}{2} \end{eqnarray*}$ haben? Aber wie komme ich genau auf die Menge?

Ich wäre für einen kleinen gedanklichen Anstoß sehr dankbar!

Viele Grüße

22.05.2015, 15:22

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von pansox
Dass die Lösungsmenge alle x enthält, die die Ordnung $\begin{eqnarray*} \frac{p-1}{2} \end{eqnarray*}$ haben?

Vorsicht: $\begin{align*} x^{\frac{p-1}{2}} \equiv 1\bmod p \end{align*}$ heißt nicht, dass $\begin{align*} x \end{align*}$ die Ordnung $\begin{align*} \frac{p-1}{2} \end{align*}$ hat, sondern nur, dass die Ordnung von $\begin{align*} x \end{align*}$ ein Teiler von $\begin{align*} \frac{p-1}{2} \end{align*}$ ist.

22.05.2015, 15:56

pansox

Auf diesen Beitrag antworten »

Korrekt, stimmt. Sorry.

In meinem Fall ist $\begin{eqnarray*} \frac{(p-1)}{2} \end{eqnarray*}$ jedoch sogar per Definition eine Primzahl, was damit ja der Ordnung gleich käme. Aber ich vermute, dass das nicht unbedingt hilft, denn auch wenn $\begin{eqnarray*} \frac{(p-1)}{2} \end{eqnarray*}$ keine Primzahl wäre, scheint ja die Aussage nach Wikipedia zu gelten.

Aber Danke für den Hinweis!

22.05.2015, 16:05

RavenOnJ

Auf diesen Beitrag antworten »

RE: Quadratische Reste bei Primzahlmoduln
Man kann zeigen, dass a quadratischer Rest genau dann wenn $\begin{align*} a=g^r \end{align*}$ mit einer Primitivwurzel g und r gerade. Da es genau $\begin{align*} \frac{p-1}2 \end{align*}$ Zahlen im Primzahlmodul gibt, deren Exponent zu g gerade ist, gibt es auch genauso viel quadratische Reste.

22.05.2015, 16:11

pansox

Auf diesen Beitrag antworten »

RE: Quadratische Reste bei Primzahlmoduln

Zitat:

Original von RavenOnJ
Man kann zeigen, dass a quadratischer Rest genau dann wenn $\begin{align*} a=g^r \end{align*}$ mit einer Primitivwurzel g und r gerade. Da es genau $\begin{align*} \frac{p-1}2 \end{align*}$ Zahlen im Primzahlmodul gibt, deren Exponent zu g gerade ist, gibt es auch genauso viel quadratische Reste.

Danke RavonOnJ. Der Begriff bzw. die Verwendung von Primitivwurzeln ist mir leider (noch) nicht bekannt, aber ich lese mich da mal ein, danke für den Hinweis! Bin natürlich immer noch gerne für weitere Ideen offen.

Nochmals Danke!
pan

22.05.2015, 16:12

HAL 9000

Auf diesen Beitrag antworten »

Alternative:

Man kann leicht nachweisen, dass für eine ungerade Primzahl $\begin{align*} p \end{align*}$ die $\begin{align*} \frac{p-1}{2} \end{align*}$ Reste

$\begin{align*} 1^2,\; 2^2, \ldots, \left(\frac{p-1}{2}\right)^2 \end{align*}$

modulo $\begin{align*} p \end{align*}$ sämtlich verschieden sind.

22.05.2015, 16:15

pansox

Auf diesen Beitrag antworten »

Danke HAL, das hört sich gut an, ist eigentlich genau das, was ich zeigen will, aber du hast es auf den Punkt formuliert. Dann versuche ich mal zu zeigen, dass das genau so ist :-)

Melde mich.

pan

22.05.2015, 16:30

pansox

Auf diesen Beitrag antworten »

Habe schonmal eine erste Erkenntnis:

Beispiel p = 11

1 * 1 = 1
2 * 2 = 4
3 * 3 = 9
4 * 4 = 16
5 * 5 = 25
---------------
6*6 = 5*5 + 1*11
7*7 = 4*4 + 3*11
8*8 = 3*3 + 5*11
9*9 = 2*2 + 7*11
10*10 = 1*1 + 9*11

Vermute, damit lässt sich was anfangen :-) Jetzt muss ich nur noch herausfinden, warum der liebe Herr das genau so gemacht hat ....

22.05.2015, 16:36

HAL 9000

Auf diesen Beitrag antworten »

Hmm, du betrachtest nun die Reste $\begin{align*} x^2 \end{align*}$ nicht nur für $\begin{align*} x=1,2,\ldots,\frac{p-1}{2} \end{align*}$ sondern auch noch für $\begin{align*} x=\frac{p+1}{2},\ldots,p-1 \end{align*}$ ? Dort passiert nicht interessantes mehr, es tauchen dieselben Reste nochmal in umgekehrter Reihenfolge auf, was sofort aus $\begin{align*} x^2 = (-x)^2 \equiv (p-x)^2\bmod p \end{align*}$ folgt.

25.05.2015, 14:56

pansox

Auf diesen Beitrag antworten »

Hallo HAL,

entschuldige die späte Antwort, mit kam Pfingsten "dazwischen" :-)

Danke für deine letzte Antwort. Das hat mir sehr geholfen!!

Viele Grüße und frohe Pfingsten!
pan

Neue Frage »

Antworten »

Quadratische Reste bei Primzahlmoduln

Verwandte Themen